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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое ориентированный граф?

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

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

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

В односвязном списке каждый узел содержит:

  1. AДанные и ссылку на следующий узел
  2. BДанные и индекс
  3. CДанные и ссылки на все остальные узлы
  4. DТолько данные
4.Средняя

Кольцевой буфер (ring buffer) обычно используют для реализации:

  1. AОчереди фиксированного размера
  2. BХеш-функции
  3. CОбхода графа
  4. DДвоичного дерева поиска
5.Средняя

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

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

Как вставляется новый элемент в двоичную кучу?

  1. AЕго помещают в корень и опускают вниз
  2. BЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
  4. DВсю кучу перестраивают с нуля
7.Сложная

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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

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

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

Ответы

  1. 1. D · Граф, рёбра которого направлены от одной вершины к другой
  2. 2. D · Список соседних вершин
  3. 3. A · Данные и ссылку на следующий узел
  4. 4. A · Очереди фиксированного размера
  5. 5. D · O(V + E)
  6. 6. B · Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  7. 7. D · Чтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
  8. 8. D · Освобождение ячейки могло бы разорвать последовательность пробирования для других ключей

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