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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое узлы-братья (siblings) в дереве?

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

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

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

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

  1. AВсегда его родитель
  2. BСамый левый узел его правого поддерева
  3. CВсегда его правый потомок
  4. DСамый правый узел его левого поддерева
5.Средняя

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

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

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

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

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

  1. AТолько для чисел
  2. BС возможными ложноотрицательными, но без ложноположительных результатов
  3. CВсегда точно
  4. DС возможными ложноположительными, но без ложноотрицательных результатов
8.Сложная

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

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

Ответы

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

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