Алгоритмы и сложность: лист заданий с ответами

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Каково O большое для 3n² + 5n + 2?

  1. AO(5n)
  2. BO(n³)
  3. CO(n²)
  4. DO(3n²)
2.Лёгкая

Что такое рекурсия?

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

Что из этого растёт медленнее всего при больших n?

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

Каково время работы поразрядной сортировки LSD для n целых чисел из d цифр в системе счисления с основанием k?

  1. AO(n²)
  2. BO(dn log k)
  3. CO(d(n + k))
  4. DO(n log n)
5.Средняя

Какова временна́я сложность алгоритма Беллмана–Форда на графе с V вершинами и E рёбрами?

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

Каково решение рекуррентного соотношения T(n) = T(n/2) + O(1)?

  1. AO(n log n)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
7.Сложная

Как алгоритм Беллмана–Форда обнаруживает цикл отрицательного веса, достижимый из источника?

  1. AОн проверяет, есть ли ребро с отрицательным весом
  2. BПосле V − 1 раундов он проверяет, можно ли ещё релаксировать какое-либо ребро
  3. CОн подсчитывает циклы поиском в глубину
  4. DОн дважды запускает алгоритм Дейкстры и сравнивает два полученных результата расстояний
8.Сложная

Почему любой поиск в отсортированном массиве, основанный на сравнениях, требует в худшем случае Ω(log n) сравнений?

  1. AКаждый элемент нужно сравнить хотя бы один раз
  2. BКаждое сравнение занимает логарифмическое время
  3. CДерево решений с n возможными исходами должно иметь глубину не менее log₂ n
  4. DБинарный поиск — единственный возможный алгоритм, и ему нужно log₂ n сравнений

Ответы

  1. 1. C · O(n²)
  2. 2. D · Функция, которая вызывает саму себя для меньших входных данных
  3. 3. A · O(log n)
  4. 4. C · O(d(n + k))
  5. 5. C · O(V × E)
  6. 6. C · O(log n)
  7. 7. B · После V − 1 раундов он проверяет, можно ли ещё релаксировать какое-либо ребро
  8. 8. C · Дерево решений с n возможными исходами должно иметь глубину не менее log₂ n

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