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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что содержит каждый узел двусвязного списка?

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

Сколько памяти занимает матрица смежности графа с V вершинами?

  1. AO(V²)
  2. BO(V + E)
  3. CO(E)
  4. DO(log V)
5.Средняя

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

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

Как найти минимальный ключ в двоичном дереве поиска?

  1. AОбойти все листья и сравнить их
  2. BИдти от корня по правым потомкам, пока правого потомка не окажется
  3. CПосмотреть только на корень
  4. DИдти от корня по левым потомкам, пока левого потомка не окажется
7.Сложная

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

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

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

  1. AПравый поворот в левом потомке, затем левый поворот в узле
  2. BОдиночный левый поворот в узле
  3. CЛевый поворот в левом потомке, затем правый поворот в узле
  4. DОдиночный правый поворот в узле

Ответы

  1. 1. D · Узел, затем левое поддерево, затем правое поддерево
  2. 2. A · Данные, указатель на следующий узел и указатель на предыдущий узел
  3. 3. B · Число хранимых элементов, делённое на число корзин
  4. 4. A · O(V²)
  5. 5. C · Очереди фиксированного размера
  6. 6. D · Идти от корня по левым потомкам, пока левого потомка не окажется
  7. 7. D · Ответов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)
  8. 8. C · Левый поворот в левом потомке, затем правый поворот в узле

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