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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

В чём главное отличие статического массива от динамического?

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

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

  1. AЛевое поддерево, затем узел, затем правое поддерево
  2. BУзел, затем левое поддерево, затем правое поддерево
  3. CПравое поддерево, затем узел, затем левое поддерево
  4. DЛевое поддерево, затем правое поддерево, затем узел
4.Средняя

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

  1. A2i + 1 и 2i + 2
  2. Bi/2 и i/2 + 1
  3. Ci + 1 и i + 2
  4. D2i и 2i + 1
5.Средняя

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

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

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

Почему в хеш-таблице с открытой адресацией удаление часто выполняют с помощью метки «надгробие» (tombstone)?

  1. AУдалённые ключи нужно хранить вечно из соображений безопасности, поэтому ячейки нельзя использовать повторно
  2. BОсвобождение ячейки могло бы разорвать последовательность пробирования для других ключей
  3. CЭто делает таблицу отсортированной
  4. DНадгробия ускоряют хеширование
8.Сложная

Какому свойству должно удовлетворять красно-чёрное дерево?

  1. AКорень должен быть красным
  2. BКаждый путь от узла до его листьев-потомков содержит одинаковое число чёрных узлов
  3. CУ каждого красного узла должны быть красные потомки, поэтому красные узлы всегда образуют непрерывные цепочки до листьев
  4. DКаждый узел должен быть красным

Ответы

  1. 1. D · Список соседних вершин
  2. 2. B · Динамический массив может расти, переходя в больший блок памяти
  3. 3. D · Левое поддерево, затем правое поддерево, затем узел
  4. 4. A · 2i + 1 и 2i + 2
  5. 5. A · O(log n)
  6. 6. A · O(V²)
  7. 7. B · Освобождение ячейки могло бы разорвать последовательность пробирования для других ключей
  8. 8. B · Каждый путь от узла до его листьев-потомков содержит одинаковое число чёрных узлов

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