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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. A2n
  2. Bn − 1
  3. Cn
  4. Dn + 1
2.Лёгкая

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

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

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

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

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

  1. A4 5 2 3 1
  2. B1 2 4 5 3
  3. C1 2 3 4 5
  4. D4 2 5 1 3
5.Средняя

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

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

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

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

Почему базы данных часто используют для индексов B+ деревья, а не обычные B-деревья?

  1. AВсе записи находятся в связанных листьях, что делает сканирование диапазонов эффективным
  2. BB+ деревья не нужно балансировать
  3. CB+ деревья хранят данные только в корне
  4. DB+ деревья используют двоичные внутренние узлы, что сокращает число чтений с диска
8.Сложная

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

  1. AСтек всех посещённых рёбер
  2. BОчередь (или любая коллекция) вершин с полустепенью захода 0
  3. CMax-куча, упорядоченная по полустепени исхода
  4. DМатрица смежности, фиксирующая, какие вершины уже удалены

Ответы

  1. 1. B · n − 1
  2. 2. D · Узел, затем левое поддерево, затем правое поддерево
  3. 3. A · Число хранимых элементов, делённое на число корзин
  4. 4. B · 1 2 4 5 3
  5. 5. D · Очередь с приоритетом по минимуму
  6. 6. D · O(V + E)
  7. 7. A · Все записи находятся в связанных листьях, что делает сканирование диапазонов эффективным
  8. 8. B · Очередь (или любая коллекция) вершин с полустепенью захода 0

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