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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Где находится наименьший элемент двоичной min-кучи?

  1. AВ самом левом листе
  2. BВ корне
  3. CВ последней позиции массива
  4. DВ каком-то листе, который придётся искать
2.Лёгкая

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

  1. AОчередь
  2. BКуча
  3. CБинарное дерево
  4. DСтек
3.Лёгкая

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

  1. AОчередь с приоритетом
  2. BСтек
  3. CОчередь
  4. DХеш-таблица
4.Средняя

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

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

Как найти минимальный ключ в двоичном дереве поиска?

  1. AИдти от корня по левым потомкам, пока левого потомка не окажется
  2. BИдти от корня по правым потомкам, пока правого потомка не окажется
  3. CОбойти все листья и сравнить их
  4. DПосмотреть только на корень
6.Средняя

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

  1. A4 5 2 3 1
  2. B4 2 5 1 3
  3. C1 2 4 5 3
  4. D1 2 3 4 5
7.Сложная

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

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

  1. AСтек всех посещённых рёбер
  2. BМатрица смежности, фиксирующая, какие вершины уже удалены
  3. CMax-куча, упорядоченная по полустепени исхода
  4. DОчередь (или любая коллекция) вершин с полустепенью захода 0

Ответы

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

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