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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что делает хеш-функция в хеш-таблице?

  1. AШифрует значения в таблице
  2. BОтображает ключ в индекс таблицы
  3. CСортирует ключи в таблице
  4. DПодсчитывает, сколько ключей хранится
2.Лёгкая

Что хранит отображение (map, словарь)?

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

В двоичном дереве поиска значения в левом поддереве узла:

  1. AБольше значения узла
  2. BРавны значению узла
  3. CМеньше значения узла
  4. DРасположены в случайном порядке
4.Средняя

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 0
  2. BВ индексе 3
  3. CВ индексе 4
  4. DВ индексе 6
5.Средняя

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

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

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

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

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

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

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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

Ответы

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

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