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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что определяет двоичное дерево?

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

Что такое свойство max-кучи?

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

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

  1. A√n
  2. Blog₂ n
  3. Cn (дерево превращается в связный список)
  4. D1
5.Средняя

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

  1. AO(L), независимо от числа хранимых слов
  2. BO(n), где n — число слов
  3. CO(L × n)
  4. DO(log n), где n — число слов
6.Средняя

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

Почему из стандартного фильтра Блума нельзя просто удалить элементы, обнулив их биты?

  1. AБиты фильтра Блума нельзя менять после создания
  2. BФильтры Блума хранят элементы целиком, и их невозможно снова найти после хеширования
  3. CЭти биты могут принадлежать и другим элементам, что вызвало бы ложноотрицательные результаты
  4. DУдаление повысило бы долю ложноположительных результатов до 100%
8.Сложная

Дерево отрезков (segment tree) обычно используют для:

  1. AОтветов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)
  2. BРеализации стека
  3. CСортировки строк по алфавиту путём хранения каждого префикса в отдельном узле дерева
  4. DХранения рёбер графа

Ответы

  1. 1. C · Верхний узел, у которого нет родителя
  2. 2. A · У каждого узла не более двух потомков
  3. 3. C · Ключ каждого родителя больше или равен ключам его потомков
  4. 4. C · n (дерево превращается в связный список)
  5. 5. A · O(L), независимо от числа хранимых слов
  6. 6. A · Выделяется таблица большего размера, и каждый ключ вставляется заново
  7. 7. C · Эти биты могут принадлежать и другим элементам, что вызвало бы ложноотрицательные результаты
  8. 8. A · Ответов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)

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