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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что определяет двоичное дерево?

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

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

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

Что содержит указатель next последнего узла односвязного списка?

  1. AАдрес предыдущего узла
  2. BЧисло узлов в списке
  3. CАдрес первого узла
  4. DNull (узла нет)
4.Средняя

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

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

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

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

  1. Ah2
  2. B2h
  3. C2h+1 − 1
  4. D2h + 1
7.Сложная

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

  1. AОдиночный правый поворот в узле
  2. BЛевый поворот в левом потомке, затем правый поворот в узле
  3. CОдиночный левый поворот в узле
  4. DПравый поворот в левом потомке, затем левый поворот в узле
8.Сложная

Какому свойству должно удовлетворять красно-чёрное дерево?

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

Ответы

  1. 1. B · У каждого узла не более двух потомков
  2. 2. C · Ключ каждого родителя больше или равен ключам его потомков
  3. 3. D · Null (узла нет)
  4. 4. D · Высоты левого и правого поддеревьев различаются не более чем на 1
  5. 5. B · Это полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
  6. 6. C · 2h+1 − 1
  7. 7. B · Левый поворот в левом потомке, затем правый поворот в узле
  8. 8. A · Каждый путь от узла до его листьев-потомков содержит одинаковое число чёрных узлов

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