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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое ориентированный граф?

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

Как называется операция очереди, удаляющая элемент из начала?

  1. AEnqueue
  2. BDequeue
  3. CInsert
  4. DPush
3.Лёгкая

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

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

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

  1. AO(L × n)
  2. BO(log n), где n — число слов
  3. CO(n), где n — число слов
  4. DO(L), независимо от числа хранимых слов
5.Средняя

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

  1. AВ индексе ⌊(i − 1) / 2⌋
  2. BВ индексе i − 1
  3. CВ индексе 2i + 1
  4. DВ индексе ⌊i / 2⌋ + 1
7.Сложная

Каковы затраты времени и дополнительной памяти на разворот односвязного списка на месте?

  1. AO(1) времени и O(1) дополнительной памяти
  2. BO(n log n) времени и O(1) дополнительной памяти
  3. CO(n) времени и O(1) дополнительной памяти
  4. DO(n) времени и O(n) дополнительной памяти
8.Сложная

Дерево отрезков (segment tree) обычно используют для:

  1. AХранения рёбер графа
  2. BСортировки строк по алфавиту путём хранения каждого префикса в отдельном узле дерева
  3. CРеализации стека
  4. DОтветов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)

Ответы

  1. 1. A · Граф, рёбра которого направлены от одной вершины к другой
  2. 2. B · Dequeue
  3. 3. D · Левое поддерево, затем правое поддерево, затем узел
  4. 4. D · O(L), независимо от числа хранимых слов
  5. 5. B · O(1)
  6. 6. A · В индексе ⌊(i − 1) / 2⌋
  7. 7. C · O(n) времени и O(1) дополнительной памяти
  8. 8. D · Ответов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)

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