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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое цикл в графе?

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

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

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

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 0
  2. BВ индексе 4
  3. CВ индексе 3
  4. DВ индексе 6
5.Средняя

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

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

Чему равно значение постфиксного выражения 3 4 + 2 * ?

  1. A10
  2. B24
  3. C11
  4. D14
7.Сложная

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

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

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

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

Ответы

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

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