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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

Какая операция медленная в массиве, но быстрая в начале связного списка?

  1. AВставка в начало
  2. BДоступ к 5-му элементу
  3. CОпределение длины массива фиксированного размера
  4. DЧтение последнего элемента по индексу
4.Средняя

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

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

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AВ порядке вставки
  2. BВ порядке возрастания (отсортированно)
  3. CПо уровням
  4. DВсегда в порядке убывания
6.Средняя

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(1), потому что индекс известен
  2. BO(log n) из-за двоичного поиска
  3. CO(n²), потому что каждый элемент сдвигается n раз
  4. DO(n), потому что последующие элементы нужно сдвинуть
7.Сложная

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AДелать размер буфера степенью двойки
  2. BХранить front и rear в одной переменной
  3. CВсегда очищать буфер, когда front равен rear, так что состояние — пустой
  4. DХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
8.Сложная

Какое свойство поддерживает любое B-дерево идеально сбалансированным?

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

Ответы

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

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