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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. AОбщее число рёбер графа
  2. BСтрока из V булевых значений
  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. AO(n log n)
  2. BO(n)
  3. CO(1)
  4. DO(log n)
5.Средняя

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

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

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

  1. AОчередь с приоритетом по минимуму
  2. BМножество без упорядочения
  3. CОчередь FIFO
  4. DСтек
7.Сложная

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

  1. A60
  2. B40
  3. C70
  4. D80
8.Сложная

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

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

Ответы

  1. 1. C · Список соседних вершин
  2. 2. B · Меньше значения узла
  3. 3. A · Очередь
  4. 4. D · O(log n)
  5. 5. D · Самый левый узел его правого поддерева
  6. 6. A · Очередь с приоритетом по минимуму
  7. 7. A · 60
  8. 8. D · Она сортирует на месте за O(n log n) в худшем случае, но не является устойчивой

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