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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что хранится для каждой вершины в представлении графа списками смежности?

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

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

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

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

  1. A4 5 2 3 1
  2. B1 2 4 5 3
  3. C4 2 5 1 3
  4. D5 4 3 2 1
5.Средняя

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

  1. AO(1)
  2. BO(n)
  3. CO(log n)
  4. DO(n²)
6.Средняя

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

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

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

  1. AO(n)
  2. BO(m)
  3. CO(1 + α), где α = n / m
  4. DO(log n)
8.Сложная

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

  1. A70
  2. B40
  3. C60
  4. D80

Ответы

  1. 1. A · Верхний узел, у которого нет родителя
  2. 2. A · Список соседних вершин
  3. 3. A · Очередь
  4. 4. A · 4 5 2 3 1
  5. 5. A · O(1)
  6. 6. A · В порядке возрастания (отсортированно)
  7. 7. C · O(1 + α), где α = n / m
  8. 8. C · 60

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