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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое коллизия в хеш-таблице?

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

Сколько рёбер в дереве с n узлами?

  1. An + 1
  2. Bn − 1
  3. C2n
  4. Dn
3.Лёгкая

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

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

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(1), потому что индекс известен
  2. BO(n²), потому что каждый элемент сдвигается n раз
  3. CO(n), потому что последующие элементы нужно сдвинуть
  4. DO(log n) из-за двоичного поиска
5.Средняя

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

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

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

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

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

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

Какое свойство поддерживает любое B-дерево идеально сбалансированным?

  1. AУ каждого узла ровно два потомка
  2. BКаждый узел хранит один ключ
  3. CВсе листья находятся на одной глубине
  4. DКлючи хранятся только в корне

Ответы

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

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