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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое коллизия в хеш-таблице?

  1. AВ таблице заканчивается память
  2. BДва одинаковых ключа хранятся дважды
  3. CКлюч вообще невозможно хешировать
  4. DДва разных ключа отображаются в один и тот же индекс
3.Лёгкая

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

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

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

  1. AЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
  2. BЧтобы упростить код, убрав особые случаи в голове или хвосте
  3. CЧтобы хранить число элементов
  4. DЧтобы список был отсортирован
5.Средняя

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

  1. A1 2 3 4 5
  2. B4 2 5 1 3
  3. C1 2 4 5 3
  4. D4 5 2 3 1
6.Средняя

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

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AДелать размер буфера степенью двойки
  2. BВсегда очищать буфер, когда front равен rear, так что состояние — пустой
  3. CХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  4. DХранить front и rear в одной переменной
8.Сложная

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

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

Ответы

  1. 1. B · Динамический массив может расти, переходя в больший блок памяти
  2. 2. D · Два разных ключа отображаются в один и тот же индекс
  3. 3. A · Список соседних вершин
  4. 4. B · Чтобы упростить код, убрав особые случаи в голове или хвосте
  5. 5. C · 1 2 4 5 3
  6. 6. A · Самый левый узел его правого поддерева
  7. 7. C · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  8. 8. B · Заменяют его in-order преемником (или предшественником) и удаляют тот узел

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