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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое ориентированный граф?

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

Какую структуру обычно используют для реализации очереди с приоритетом?

  1. AНеупорядоченный односвязный список
  2. BСтроку
  3. CСтек
  4. DКучу
4.Средняя

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

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

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

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

  1. AДвоичного дерева поиска
  2. BХеш-функции
  3. CОбхода графа
  4. DОчереди фиксированного размера
7.Сложная

Что делает косое дерево (splay tree) после каждого обращения?

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

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

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

Ответы

  1. 1. A · Левое поддерево, затем правое поддерево, затем узел
  2. 2. B · Граф, рёбра которого направлены от одной вершины к другой
  3. 3. D · Кучу
  4. 4. A · Последний элемент перемещают в корень и опускают вниз (sift down)
  5. 5. C · n (дерево превращается в связный список)
  6. 6. D · Очереди фиксированного размера
  7. 7. C · Поворотами поднимает узел, к которому обращались, в корень
  8. 8. D · Ожидаемый поиск за O(log n) благодаря нескольким уровням указателей вперёд

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