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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что хранит отображение (map, словарь)?

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

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

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

Как называется операция стека, добавляющая элемент на вершину?

  1. APeek
  2. BEnqueue
  3. CPush
  4. DPop
4.Средняя

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

  1. AХеш-таблица
  2. BДвоичное дерево поиска
  3. CСтек
  4. DОчередь
5.Средняя

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

  1. AДвоичная куча рёбер
  2. BСписки смежности
  3. CОдин отсортированный массив вершин
  4. DМатрица смежности
6.Средняя

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

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

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AВсегда очищать буфер, когда front равен rear, так что состояние — пустой
  2. BХранить front и rear в одной переменной
  3. CДелать размер буфера степенью двойки
  4. DХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной

Ответы

  1. 1. C · Пары ключ–значение с уникальными ключами
  2. 2. A · Узел, затем левое поддерево, затем правое поддерево
  3. 3. C · Push
  4. 4. C · Стек
  5. 5. B · Списки смежности
  6. 6. C · O(1)
  7. 7. A · O(V²)
  8. 8. D · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной

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