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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое дек (deque, двусторонняя очередь)?

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

Хеш-таблица (hash table) хранит данные в виде:

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

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

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

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

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

Сколько памяти занимает матрица смежности графа с V вершинами?

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

Что верно для матрицы смежности неориентированного графа?

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

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

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

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

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

Ответы

  1. 1. B · Структура, допускающая вставку и удаление с обоих концов
  2. 2. C · Пар ключ–значение, расположение которых определяет хеш-функция
  3. 3. B · Левое поддерево, затем правое поддерево, затем узел
  4. 4. C · O(V + E)
  5. 5. D · O(V²)
  6. 6. B · Она симметрична относительно главной диагонали
  7. 7. C · Для проверки, соединены ли уже два конца ребра
  8. 8. C · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной

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