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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

В односвязном списке каждый узел содержит:

  1. AДанные и ссылку на следующий узел
  2. BТолько данные
  3. CДанные и ссылки на все остальные узлы
  4. DДанные и индекс
2.Лёгкая

Высота дерева обычно определяется как:

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

  1. AДоступ к элементу с индексом i
  2. BЧтение первого элемента
  3. CВставка в начало
  4. DУдаление головного элемента
4.Средняя

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

  1. AХранение ключей в порядке вставки
  2. BПоиск за константное время в любом случае
  3. CВысоту O(log n) благодаря перебалансировке
  4. DЧто ни у одного узла нет двух потомков
5.Средняя

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

  1. AЧтобы хранить число элементов
  2. BЧтобы список был отсортирован
  3. CЧтобы упростить код, убрав особые случаи в голове или хвосте
  4. DЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
6.Средняя

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

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

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

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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

Ответы

  1. 1. A · Данные и ссылку на следующий узел
  2. 2. B · Число рёбер на самом длинном пути от корня до листа
  3. 3. A · Доступ к элементу с индексом i
  4. 4. C · Высоту O(log n) благодаря перебалансировке
  5. 5. C · Чтобы упростить код, убрав особые случаи в голове или хвосте
  6. 6. D · Высоты левого и правого поддеревьев различаются не более чем на 1
  7. 7. B · O(1 + α), где α = n / m
  8. 8. D · Чтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы

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