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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Хеш-таблица (hash table) хранит данные в виде:

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

Что такое дек (deque, двусторонняя очередь)?

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

Как элементы массива хранятся в памяти?

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

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

  1. A4 2 5 1 3
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D5 4 3 2 1
5.Средняя

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

  1. A(i + 1) mod n
  2. Bi + 1
  3. C2i + 1
  4. D(i − 1) mod n
6.Средняя

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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

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

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

Ответы

  1. 1. B · Пар ключ–значение, расположение которых определяет хеш-функция
  2. 2. C · Структура, допускающая вставку и удаление с обоих концов
  3. 3. B · В одном непрерывном блоке, один за другим
  4. 4. B · 4 5 2 3 1
  5. 5. A · (i + 1) mod n
  6. 6. D · Выделяется таблица большего размера, и каждый ключ вставляется заново
  7. 7. B · Оно сливает цепочки узлов с одним потомком в одно ребро, помеченное строкой
  8. 8. D · Освобождение ячейки могло бы разорвать последовательность пробирования для других ключей

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