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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что делает операция peek (или top) стека?

  1. AУдаляет верхний элемент и возвращает его
  2. BВозвращает нижний элемент стека
  3. CВозвращает верхний элемент, не удаляя его
  4. DУдаляет все элементы из стека
2.Лёгкая

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

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

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

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

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

  1. AТолько хеш-таблицу
  2. BОчередь
  3. CКучу
  4. DСтек
7.Сложная

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

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

Какая пара обходов всегда однозначно определяет двоичное дерево с различными ключами?

  1. AПрямой и симметричный (preorder и inorder)
  2. BОдин только прямой
  3. CПрямой и обратный (preorder и postorder)
  4. DОдин только обход по уровням

Ответы

  1. 1. C · Возвращает верхний элемент, не удаляя его
  2. 2. A · Список соседних вершин
  3. 3. C · Узел, затем левое поддерево, затем правое поддерево
  4. 4. B · Это полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
  5. 5. A · Высоты левого и правого поддеревьев различаются не более чем на 1
  6. 6. D · Стек
  7. 7. B · Чтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
  8. 8. A · Прямой и симметричный (preorder и inorder)

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