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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

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

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

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

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

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

Как работает extract-min в двоичной min-куче?

  1. AУдаляют последний элемент массива
  2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
  3. CУдаляют корень и сдвигают все элементы на одну позицию влево
  4. DИщут новый минимум среди всех листьев
5.Средняя

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

  1. A70
  2. B50
  3. C20
  4. D40
6.Средняя

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

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AХранить front и rear в одной переменной
  2. BДелать размер буфера степенью двойки
  3. CВсегда очищать буфер, когда front равен rear, так что состояние — пустой
  4. DХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
8.Сложная

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

  1. AНеобходимость хранить ключи в таблице
  2. BСтоимость O(n) чтения значения по ключу
  3. CПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
  4. DНеобходимость в хеш-функции

Ответы

  1. 1. B · Узел, затем левое поддерево, затем правое поддерево
  2. 2. A · У каждого узла не более двух потомков
  3. 3. A · Пар ключ–значение, расположение которых определяет хеш-функция
  4. 4. B · Последний элемент перемещают в корень и опускают вниз (sift down)
  5. 5. C · 20
  6. 6. B · O(L), независимо от числа хранимых слов
  7. 7. D · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  8. 8. C · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек

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