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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое свойство max-кучи?

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

Что такое корень дерева?

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

В каком порядке обратный обход (postorder) двоичного дерева посещает узлы?

  1. AУзел, затем левое поддерево, затем правое поддерево
  2. BПравое поддерево, затем узел, затем левое поддерево
  3. CЛевое поддерево, затем узел, затем правое поддерево
  4. DЛевое поддерево, затем правое поддерево, затем узел
4.Средняя

Как работает extract-min в двоичной min-куче?

  1. AПоследний элемент перемещают в корень и опускают вниз (sift down)
  2. BИщут новый минимум среди всех листьев
  3. CУдаляют последний элемент массива
  4. DУдаляют корень и сдвигают все элементы на одну позицию влево
5.Средняя

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

  1. AЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
  2. BМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
  3. CВсе ключи в куче равны
  4. DВ кучах никогда не бывает больше 100 элементов
6.Средняя

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

  1. AДвойное хеширование
  2. BКвадратичное пробирование
  3. CМетод цепочек (separate chaining)
  4. DЛинейное пробирование
7.Сложная

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

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

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

  1. AЛевый поворот в левом потомке, затем правый поворот в узле
  2. BОдиночный правый поворот в узле
  3. CОдиночный левый поворот в узле
  4. DПравый поворот в левом потомке, затем левый поворот в узле

Ответы

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

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