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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

  1. AГраф
  2. BСтек
  3. CХеш-множество
  4. DОчередь
3.Лёгкая

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

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

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

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

  1. A1
  2. B0,5
  3. C2
  4. DМаксимума нет
6.Средняя

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

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

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

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

Как определить, есть ли цикл в односвязном списке, используя O(1) дополнительной памяти?

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

Ответы

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

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