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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Высота дерева обычно определяется как:

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

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

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

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

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

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

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

  1. AМаксимума нет
  2. B0,5
  3. C1
  4. D2
7.Сложная

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

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

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

  1. AУдаляют всё поддерево
  2. BПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
  3. CЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
  4. DМеняют его местами с корнем

Ответы

  1. 1. C · Число рёбер на самом длинном пути от корня до листа
  2. 2. D · Список соседних вершин
  3. 3. C · Очередь
  4. 4. D · O(V + E)
  5. 5. D · В двусвязном списке
  6. 6. C · 1
  7. 7. C · Очередь (или любая коллекция) вершин с полустепенью захода 0
  8. 8. C · Заменяют его in-order преемником (или предшественником) и удаляют тот узел

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