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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

  1. AСтек
  2. BХеш-множество
  3. CОчередь
  4. DГраф
3.Лёгкая

Что такое корень дерева?

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

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

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

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

  1. A4 2 5 1 3
  2. B1 2 4 5 3
  3. C4 5 2 3 1
  4. D1 2 3 4 5
6.Средняя

Приложению нужен быстрый поиск, а также вывод ключей в отсортированном порядке и запросы по диапазону. Какая структура подходит лучше всего?

  1. AСтек
  2. BХеш-таблица
  3. CНеотсортированный связный список
  4. DСбалансированное двоичное дерево поиска
7.Сложная

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

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

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

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

Ответы

  1. 1. B · Оно хранит элементы без повторений
  2. 2. A · Стек
  3. 3. C · Верхний узел, у которого нет родителя
  4. 4. B · O(V + E)
  5. 5. B · 1 2 4 5 3
  6. 6. D · Сбалансированное двоичное дерево поиска
  7. 7. D · Ответов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)
  8. 8. C · Для проверки, соединены ли уже два конца ребра

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