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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что хранит отображение (map, словарь)?

  1. AТолько значения в порядке вставки
  2. BЗначения, отсортированные по размеру
  3. CПары одинаковых ключей
  4. DПары ключ–значение с уникальными ключами
3.Лёгкая

Как называется операция стека, добавляющая элемент на вершину?

  1. AEnqueue
  2. BPush
  3. CPop
  4. DPeek
4.Средняя

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

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

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 0
  2. BВ индексе 4
  3. CВ индексе 6
  4. DВ индексе 3
7.Сложная

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

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

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

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

Ответы

  1. 1. A · Null (узла нет)
  2. 2. D · Пары ключ–значение с уникальными ключами
  3. 3. B · Push
  4. 4. B · Списки смежности
  5. 5. B · n (дерево превращается в связный список)
  6. 6. B · В индексе 4
  7. 7. A · O(V²)
  8. 8. C · Чтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем

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