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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Высота дерева обычно определяется как:

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

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

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

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

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

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

  1. An (дерево превращается в связный список)
  2. B√n
  3. C1
  4. Dlog₂ n
6.Средняя

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

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

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

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

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

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

Ответы

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

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