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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Как называется операция стека, добавляющая элемент на вершину?

  1. APeek
  2. BEnqueue
  3. CPop
  4. DPush
3.Лёгкая

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

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

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

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

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

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

Чему равно значение постфиксного выражения 3 4 + 2 * ?

  1. A14
  2. B24
  3. C11
  4. D10
7.Сложная

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

  1. AЛевый поворот в потомке, затем правый поворот в узле
  2. BОдиночный правый поворот в несбалансированном узле
  3. CПерекрашивание узла и его потомка
  4. DОдиночный левый поворот в несбалансированном узле
8.Сложная

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

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

Ответы

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

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