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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое корень дерева?

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

Что такое лист дерева?

  1. AУзел без потомков
  2. BУзел ровно с одним потомком
  3. CУзел без родителя
  4. DУзел с наибольшим значением
3.Лёгкая

Граф состоит из:

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

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

  1. A20
  2. B70
  3. C50
  4. D40
6.Средняя

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(1), потому что индекс известен
  2. BO(log n) из-за двоичного поиска
  3. CO(n²), потому что каждый элемент сдвигается n раз
  4. DO(n), потому что последующие элементы нужно сдвинуть
7.Сложная

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

  1. AO(1 + α), где α = n / m
  2. BO(n)
  3. CO(m)
  4. DO(log n)
8.Сложная

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

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

Ответы

  1. 1. B · Верхний узел, у которого нет родителя
  2. 2. A · Узел без потомков
  3. 3. B · Вершин (узлов), соединённых рёбрами
  4. 4. B · Списки смежности
  5. 5. A · 20
  6. 6. D · O(n), потому что последующие элементы нужно сдвинуть
  7. 7. A · O(1 + α), где α = n / m
  8. 8. B · Очередь (или любая коллекция) вершин с полустепенью захода 0

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