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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое лист дерева?

  1. AУзел без потомков
  2. BУзел ровно с одним потомком
  3. CУзел без родителя
  4. DУзел с наибольшим значением
2.Лёгкая

Что такое коллизия в хеш-таблице?

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

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

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

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

  1. AO(n log n)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
5.Средняя

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

  1. AВ кучах никогда не бывает больше 100 элементов
  2. BВсе ключи в куче равны
  3. CМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
  4. DЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
6.Средняя

Что верно для матрицы смежности неориентированного графа?

  1. AВ каждой строке ровно одна 1
  2. BОна всегда верхнетреугольная
  3. CОна симметрична относительно главной диагонали
  4. DНа её главной диагонали всегда стоят единицы
7.Сложная

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

  1. AMin-куча, перестраиваемая для каждого окна
  2. BДек, хранящий индексы в порядке убывания значений
  3. CОдносвязный список элементов окна
  4. DОтсортированный массив, обновляемый сдвигами
8.Сложная

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

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

Ответы

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

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