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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. AEnqueue
  2. BPeek
  3. CPush
  4. DPop
2.Лёгкая

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

  1. ADequeue
  2. BInsert
  3. CEnqueue
  4. DPush
3.Лёгкая

Сколько рёбер в дереве с n узлами?

  1. An − 1
  2. Bn
  3. C2n
  4. Dn + 1
4.Средняя

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

  1. A70
  2. B40
  3. C50
  4. D20
6.Средняя

Сколько памяти занимает матрица смежности графа с V вершинами?

  1. AO(E)
  2. BO(log V)
  3. CO(V + E)
  4. DO(V²)
7.Сложная

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

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

  1. AMax-куча, упорядоченная по полустепени исхода
  2. BМатрица смежности, фиксирующая, какие вершины уже удалены
  3. CОчередь (или любая коллекция) вершин с полустепенью захода 0
  4. DСтек всех посещённых рёбер

Ответы

  1. 1. C · Push
  2. 2. A · Dequeue
  3. 3. A · n − 1
  4. 4. C · Самый левый узел его правого поддерева
  5. 5. D · 20
  6. 6. D · O(V²)
  7. 7. B · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек
  8. 8. C · Очередь (или любая коллекция) вершин с полустепенью захода 0

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