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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

  1. AБинарное дерево
  2. BОчередь
  3. CКуча
  4. DСтек
2.Лёгкая

Что делает операция peek (или top) стека?

  1. AУдаляет верхний элемент и возвращает его
  2. BВозвращает нижний элемент стека
  3. CВозвращает верхний элемент, не удаляя его
  4. DУдаляет все элементы из стека
3.Лёгкая

Сколько рёбер в дереве с n узлами?

  1. An
  2. B2n
  3. Cn − 1
  4. Dn + 1
4.Средняя

Чему равно значение постфиксного выражения 3 4 + 2 * ?

  1. A14
  2. B24
  3. C10
  4. D11
5.Средняя

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

  1. A4 2 5 1 3
  2. B5 4 3 2 1
  3. C1 2 4 5 3
  4. D4 5 2 3 1
6.Средняя

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

  1. AO(1)
  2. BO(log V)
  3. CO(V)
  4. DO(E)
7.Сложная

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

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

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

  1. AПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
  2. BНеобходимость хранить ключи в таблице
  3. CНеобходимость в хеш-функции
  4. DСтоимость O(n) чтения значения по ключу

Ответы

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

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