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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

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

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

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

  1. A20
  2. B40
  3. C70
  4. D50
6.Средняя

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

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

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

  1. AВставку элементов в любую позицию
  2. BПоиск медианы за O(1)
  3. CСортировку массива и двоичный поиск
  4. DЗапросы префиксных сумм и обновления отдельного элемента
8.Сложная

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

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

Ответы

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

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