Структуры данных: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Структуры данных»: 8 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

Для преподавателей: можно бесплатно печатать, копировать и использовать на занятиях. Каждый новый лист содержит новые значения и собственные ответы. Будем благодарны за ссылку на ExamProblems на странице вашего курса.

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое коллизия в хеш-таблице?

  1. AКлюч вообще невозможно хешировать
  2. BДва одинаковых ключа хранятся дважды
  3. CДва разных ключа отображаются в один и тот же индекс
  4. DВ таблице заканчивается память
2.Лёгкая

Глубина узла в дереве — это:

  1. AЧисло потомков этого узла
  2. BЧисло узлов в его поддереве
  3. CЧисло рёбер от этого узла до самого глубокого листа
  4. DЧисло рёбер от корня до этого узла
3.Лёгкая

Что такое коэффициент заполнения (load factor) хеш-таблицы?

  1. AВремя загрузки таблицы с диска
  2. BЧисло хранимых элементов, делённое на число корзин
  3. CЧисло коллизий на данный момент
  4. DЧисло корзин, делённое на среднюю длину хранимых ключей
4.Средняя

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

  1. AЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
  2. BВсе ключи в куче равны
  3. CМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
  4. DВ кучах никогда не бывает больше 100 элементов
5.Средняя

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

  1. AВысоту O(log n) благодаря перебалансировке
  2. BЧто ни у одного узла нет двух потомков
  3. CПоиск за константное время в любом случае
  4. DХранение ключей в порядке вставки
6.Средняя

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

  1. An (дерево превращается в связный список)
  2. B√n
  3. C1
  4. Dlog₂ n
7.Сложная

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

  1. AДвоичное дерево поиска, перестраиваемое для каждого элемента
  2. BХеш-таблица всех элементов
  3. CСтек, хранящий элементы, ожидающие своего ответа
  4. DОчередь, хранящая каждую пару элементов
8.Сложная

Почему B-деревья используются в базах данных и файловых системах?

  1. AОни занимают меньше памяти, чем любой массив, поэтому весь индекс всегда помещается в оперативной памяти
  2. BОни хранят неотсортированные данные
  3. CВысокая степень ветвления делает дерево неглубоким и сокращает число медленных чтений с диска
  4. DИм не нужна перебалансировка

Ответы

  1. 1. C · Два разных ключа отображаются в один и тот же индекс
  2. 2. D · Число рёбер от корня до этого узла
  3. 3. B · Число хранимых элементов, делённое на число корзин
  4. 4. A · Это полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
  5. 5. A · Высоту O(log n) благодаря перебалансировке
  6. 6. A · n (дерево превращается в связный список)
  7. 7. C · Стек, хранящий элементы, ожидающие своего ответа
  8. 8. C · Высокая степень ветвления делает дерево неглубоким и сокращает число медленных чтений с диска

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.