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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных используется для обхода дерева по уровням (level-order)?

  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(1)
  2. BO(E)
  3. CO(V)
  4. DO(log V)
5.Средняя

Кольцевой буфер (ring buffer) обычно используют для реализации:

  1. AОчереди фиксированного размера
  2. BОбхода графа
  3. CХеш-функции
  4. DДвоичного дерева поиска
6.Средняя

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

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

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

  1. AO(n)
  2. BO(α(n))
  3. CO(log n)
  4. DO(1)
8.Сложная

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

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

Ответы

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

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