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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что содержит указатель next последнего узла односвязного списка?

  1. AАдрес первого узла
  2. BАдрес предыдущего узла
  3. CЧисло узлов в списке
  4. DNull (узла нет)
2.Лёгкая

Как элементы массива хранятся в памяти?

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

Что такое коллизия в хеш-таблице?

  1. AДва одинаковых ключа хранятся дважды
  2. BДва разных ключа отображаются в один и тот же индекс
  3. CКлюч вообще невозможно хешировать
  4. DВ таблице заканчивается память
4.Средняя

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

  1. AОчередь
  2. BСтек
  3. CДвоичное дерево поиска
  4. DХеш-таблица
5.Средняя

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

  1. AНеотсортированный связный список
  2. BХеш-таблица
  3. CСтек
  4. DСбалансированное двоичное дерево поиска
6.Средняя

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

  1. A1 2 3 4 5
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D1 2 4 5 3
7.Сложная

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

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

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

  1. AВысота не превышает n / 2
  2. BВысота равна ровно log2 n
  3. CВысота не превышает log2 n + 1
  4. DВысота не превышает 2 log2(n + 1)

Ответы

  1. 1. D · Null (узла нет)
  2. 2. B · В одном непрерывном блоке, один за другим
  3. 3. B · Два разных ключа отображаются в один и тот же индекс
  4. 4. B · Стек
  5. 5. D · Сбалансированное двоичное дерево поиска
  6. 6. D · 1 2 4 5 3
  7. 7. B · O(1 + α), где α = n / m
  8. 8. D · Высота не превышает 2 log2(n + 1)

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