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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое корень дерева?

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

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

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

Что такое свойство max-кучи?

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

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

  1. AДвоичное дерево поиска кадров
  2. BСтек вызовов
  3. CХеш-таблицу функций
  4. DОчередь памяти кучи
5.Средняя

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

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

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

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

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

  1. AO(α(n))
  2. BO(1)
  3. CO(n)
  4. DO(log n)
8.Сложная

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

  1. AЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
  2. BМеняют его местами с корнем
  3. CУдаляют всё поддерево
  4. DПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ

Ответы

  1. 1. B · Верхний узел, у которого нет родителя
  2. 2. C · Очередь
  3. 3. A · Ключ каждого родителя больше или равен ключам его потомков
  4. 4. B · Стек вызовов
  5. 5. B · O(V²)
  6. 6. B · Очереди фиксированного размера
  7. 7. C · O(n)
  8. 8. A · Заменяют его in-order преемником (или предшественником) и удаляют тот узел

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