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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какую структуру обычно используют для реализации очереди с приоритетом?

  1. AСтек
  2. BНеупорядоченный односвязный список
  3. CКучу
  4. DСтроку
3.Лёгкая

Что делает операция peek (или top) стека?

  1. AВозвращает нижний элемент стека
  2. BУдаляет все элементы из стека
  3. CУдаляет верхний элемент и возвращает его
  4. DВозвращает верхний элемент, не удаляя его
4.Средняя

Как вставляется новый элемент в двоичную кучу?

  1. AЕго помещают в корень и опускают вниз
  2. BЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
  4. DВсю кучу перестраивают с нуля
5.Средняя

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

  1. AЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
  2. BЧтобы упростить код, убрав особые случаи в голове или хвосте
  3. CЧтобы список был отсортирован
  4. DЧтобы хранить число элементов
7.Сложная

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

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

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

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

Ответы

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

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