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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какую структуру обычно используют для реализации очереди с приоритетом?

  1. AНеупорядоченный односвязный список
  2. BСтроку
  3. CСтек
  4. DКучу
3.Лёгкая

Что содержит указатель next последнего узла односвязного списка?

  1. AАдрес первого узла
  2. BЧисло узлов в списке
  3. CNull (узла нет)
  4. DАдрес предыдущего узла
4.Средняя

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

  1. AЛинейное пробирование
  2. BМетод цепочек (separate chaining)
  3. CКвадратичное пробирование
  4. DДвойное хеширование
5.Средняя

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

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

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

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

Дерево отрезков (segment tree) обычно используют для:

  1. AХранения рёбер графа
  2. BОтветов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)
  3. CСортировки строк по алфавиту путём хранения каждого префикса в отдельном узле дерева
  4. DРеализации стека
8.Сложная

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

  1. A70
  2. B40
  3. C80
  4. D60

Ответы

  1. 1. A · Список соседних вершин
  2. 2. D · Кучу
  3. 3. C · Null (узла нет)
  4. 4. B · Метод цепочек (separate chaining)
  5. 5. B · Чтобы упростить код, убрав особые случаи в голове или хвосте
  6. 6. C · O(1)
  7. 7. B · Ответов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)
  8. 8. D · 60

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