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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Сколько рёбер в дереве с n узлами?

  1. An + 1
  2. Bn − 1
  3. C2n
  4. Dn
2.Лёгкая

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

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

  1. AВремя загрузки таблицы с диска
  2. BЧисло хранимых элементов, делённое на число корзин
  3. CЧисло коллизий на данный момент
  4. DЧисло корзин, делённое на среднюю длину хранимых ключей
4.Средняя

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

  1. AСтек
  2. BОчередь с приоритетом по минимуму
  3. CОчередь FIFO
  4. DМножество без упорядочения
5.Средняя

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

  1. A2h
  2. B2h+1 − 1
  3. Ch2
  4. D2h + 1
6.Средняя

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

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

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

  1. AОтображение автоматически переносит ключ в новую корзину
  2. BНичего не меняется, потому что хеш ключа вычисляется только один раз при запуске программы
  3. CОтображение выбрасывает ошибку в момент изменения поля
  4. DПоиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
8.Сложная

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

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

Ответы

  1. 1. B · n − 1
  2. 2. C · Стек
  3. 3. B · Число хранимых элементов, делённое на число корзин
  4. 4. B · Очередь с приоритетом по минимуму
  5. 5. B · 2h+1 − 1
  6. 6. A · n (дерево превращается в связный список)
  7. 7. D · Поиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
  8. 8. A · Одиночный правый поворот в несбалансированном узле

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