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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

В двоичном дереве поиска значения в левом поддереве узла:

  1. AРасположены в случайном порядке
  2. BМеньше значения узла
  3. CРавны значению узла
  4. DБольше значения узла
4.Средняя

Чему равно значение постфиксного выражения 3 4 + 2 * ?

  1. A11
  2. B24
  3. C14
  4. D10
5.Средняя

Как работает extract-min в двоичной min-куче?

  1. AПоследний элемент перемещают в корень и опускают вниз (sift down)
  2. BИщут новый минимум среди всех листьев
  3. CУдаляют корень и сдвигают все элементы на одну позицию влево
  4. DУдаляют последний элемент массива
6.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

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

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

  1. AПравый поворот в левом потомке, затем левый поворот в узле
  2. BОдиночный левый поворот в узле
  3. CЛевый поворот в левом потомке, затем правый поворот в узле
  4. DОдиночный правый поворот в узле
8.Сложная

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

Ответы

  1. 1. A · Список соседних вершин
  2. 2. A · Граф, рёбра которого направлены от одной вершины к другой
  3. 3. B · Меньше значения узла
  4. 4. C · 14
  5. 5. A · Последний элемент перемещают в корень и опускают вниз (sift down)
  6. 6. B · В порядке возрастания (отсортированно)
  7. 7. C · Левый поворот в левом потомке, затем правый поворот в узле
  8. 8. D · Для проверки, соединены ли уже два конца ребра

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