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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  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.Средняя

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

  1. AТолько хеш-таблицу
  2. BКучу
  3. CСтек
  4. DОчередь
5.Средняя

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

  1. AСтек
  2. BОчередь с приоритетом по минимуму
  3. CОчередь FIFO
  4. DМножество без упорядочения
6.Средняя

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

  1. Ai + 1
  2. B(i + 1) mod n
  3. C2i + 1
  4. D(i − 1) mod n
7.Сложная

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

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

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

  1. AMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших
  2. BОтсортированный массив всех n значений
  3. CОчередь FIFO последних k значений
  4. DMax-куча размера k, корень которой заменяется, когда приходит меньшее значение

Ответы

  1. 1. C · Узел, затем левое поддерево, затем правое поддерево
  2. 2. A · У каждого узла не более двух потомков
  3. 3. A · Отображает ключ в индекс таблицы
  4. 4. C · Стек
  5. 5. B · Очередь с приоритетом по минимуму
  6. 6. B · (i + 1) mod n
  7. 7. C · Все листья находятся на одной глубине
  8. 8. D · Max-куча размера k, корень которой заменяется, когда приходит меньшее значение

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