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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

В чём главное отличие статического массива от динамического?

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

Высота дерева обычно определяется как:

  1. AЧисло листьев в дереве
  2. BОбщее число узлов в дереве, считая корень и каждый лист
  3. CЧисло рёбер на самом длинном пути от корня до листа
  4. DЧисло потомков корня
4.Средняя

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

  1. AO(V)
  2. BO(log V)
  3. CO(1)
  4. DO(E)
5.Средняя

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

  1. Alog₂ n
  2. B1
  3. C√n
  4. Dn (дерево превращается в связный список)
6.Средняя

Как вставляется новый элемент в двоичную кучу?

  1. AЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
  2. BЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  3. CВсю кучу перестраивают с нуля
  4. DЕго помещают в корень и опускают вниз
7.Сложная

Почему в хеш-таблице с открытой адресацией удаление часто выполняют с помощью метки «надгробие» (tombstone)?

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

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

  1. AОдин только прямой
  2. BПрямой и симметричный (preorder и inorder)
  3. CОдин только обход по уровням
  4. DПрямой и обратный (preorder и postorder)

Ответы

  1. 1. D · Число хранимых элементов, делённое на число корзин
  2. 2. B · Динамический массив может расти, переходя в больший блок памяти
  3. 3. C · Число рёбер на самом длинном пути от корня до листа
  4. 4. C · O(1)
  5. 5. D · n (дерево превращается в связный список)
  6. 6. B · Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  7. 7. A · Освобождение ячейки могло бы разорвать последовательность пробирования для других ключей
  8. 8. B · Прямой и симметричный (preorder и inorder)

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