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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  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.Средняя

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

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

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

  1. AСтек
  2. BТолько хеш-таблицу
  3. CОчередь
  4. DКучу
6.Средняя

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

  1. AСбалансированное двоичное дерево поиска
  2. BНеотсортированный связный список
  3. CХеш-таблица
  4. DСтек
7.Сложная

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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

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

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

Ответы

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

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