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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое узлы-братья (siblings) в дереве?

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

Что определяет двоичное дерево?

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

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

  1. AБинарное дерево
  2. BСтек
  3. CОчередь
  4. DКуча
4.Средняя

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

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

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

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

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

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

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

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

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

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

Ответы

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

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