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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Хеш-таблица (hash table) хранит данные в виде:

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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

  1. Ai + 1 и i + 2
  2. B2i и 2i + 1
  3. C2i + 1 и 2i + 2
  4. Di/2 и i/2 + 1
5.Средняя

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

  1. A70
  2. B40
  3. C50
  4. D20
6.Средняя

Префиксное дерево (trie) особенно эффективно для:

  1. AПоиска кратчайших путей
  2. BПоиска по префиксу, например автодополнения
  3. CХранения матриц
  4. DСортировки чисел
7.Сложная

Каковы затраты времени и дополнительной памяти на разворот односвязного списка на месте?

  1. AO(1) времени и O(1) дополнительной памяти
  2. BO(n) времени и O(n) дополнительной памяти
  3. CO(n log n) времени и O(1) дополнительной памяти
  4. DO(n) времени и O(1) дополнительной памяти
8.Сложная

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

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

Ответы

  1. 1. D · n − 1
  2. 2. C · Пар ключ–значение, расположение которых определяет хеш-функция
  3. 3. A · Стек
  4. 4. C · 2i + 1 и 2i + 2
  5. 5. D · 20
  6. 6. B · Поиска по префиксу, например автодополнения
  7. 7. D · O(n) времени и O(1) дополнительной памяти
  8. 8. B · Высота не превышает 2 log2(n + 1)

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