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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая операция медленная в массиве, но быстрая в начале связного списка?

  1. AОпределение длины массива фиксированного размера
  2. BЧтение последнего элемента по индексу
  3. CДоступ к 5-му элементу
  4. DВставка в начало
2.Лёгкая

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

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

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

  1. APeek
  2. BPush
  3. CPop
  4. DEnqueue
4.Средняя

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

  1. AМаксимума нет
  2. B1
  3. C2
  4. D0,5
5.Средняя

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

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

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

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

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

  1. AO(1)
  2. BO(log n)
  3. CO(α(n))
  4. DO(n)
8.Сложная

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

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

Ответы

  1. 1. D · Вставка в начало
  2. 2. B · Узел, затем левое поддерево, затем правое поддерево
  3. 3. B · Push
  4. 4. B · 1
  5. 5. D · O(V²)
  6. 6. D · O(1)
  7. 7. D · O(n)
  8. 8. B · Очередь (или любая коллекция) вершин с полустепенью захода 0

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