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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

  1. Ai + 1
  2. B(i + 1) mod n
  3. C(i − 1) mod n
  4. D2i + 1
5.Средняя

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

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

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(1), потому что индекс известен
  2. BO(n), потому что последующие элементы нужно сдвинуть
  3. CO(n²), потому что каждый элемент сдвигается n раз
  4. DO(log n) из-за двоичного поиска
7.Сложная

Какому свойству должно удовлетворять красно-чёрное дерево?

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

Почему B-деревья используются в базах данных и файловых системах?

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

Ответы

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

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