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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

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

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

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

  1. AСамый правый узел его левого поддерева
  2. BВсегда его родитель
  3. CСамый левый узел его правого поддерева
  4. DВсегда его правый потомок
6.Средняя

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

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

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

  1. AВысота равна ровно log2 n
  2. BВысота не превышает log2 n + 1
  3. CВысота не превышает n / 2
  4. DВысота не превышает 2 log2(n + 1)
8.Сложная

Какое утверждение о пирамидальной сортировке (heapsort) верно?

  1. AОна работает за O(n) на любых входных данных
  2. BОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой
  3. CЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти
  4. DОна устойчива и требует O(n) дополнительной памяти

Ответы

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

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