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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

  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В индексе 3
  2. BВ индексе 4
  3. CВ индексе 0
  4. DВ индексе 6
5.Средняя

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(1)
6.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AВ порядке вставки
  2. BПо уровням
  3. CВ порядке возрастания (отсортированно)
  4. DВсегда в порядке убывания
7.Сложная

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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

Каковы затраты времени и дополнительной памяти на разворот односвязного списка на месте?

  1. AO(n) времени и O(1) дополнительной памяти
  2. BO(n log n) времени и O(1) дополнительной памяти
  3. CO(n) времени и O(n) дополнительной памяти
  4. DO(1) времени и O(1) дополнительной памяти

Ответы

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

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