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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какое из этих времён работы полиномиально?

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

Чему равен log₂ 1024?

  1. A12
  2. B32
  3. C10
  4. D512
4.Средняя

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

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

Верно ли утверждать, что алгоритм O(n²) также является O(n³)?

  1. AДа, но только если n меньше 100
  2. BДа, потому что O большое — верхняя граница, а n² растёт не быстрее n³
  3. CНет, потому что при больших n значение n³ меньше n²
  4. DНет, потому что O большое всегда должно указывать точную скорость роста функции
6.Средняя

Примерно сколько сравнений нужно бинарному поиску в худшем случае на отсортированном массиве из 1,000,000 элементов?

  1. AОколо 20
  2. BОколо 1,000
  3. CОколо 500,000
  4. DОколо 100
7.Сложная

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

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

Какая оценка для log(n!) верна?

  1. AΘ(log n)
  2. BΘ(n log n)
  3. CΘ(n)
  4. DΘ(n²)

Ответы

  1. 1. C · O(n²)
  2. 2. A · O(n³)
  3. 3. C · 10
  4. 4. C · O(V × E)
  5. 5. B · Да, потому что O большое — верхняя граница, а n² растёт не быстрее n³
  6. 6. A · Около 20
  7. 7. D · O(n) времени и O(1) памяти
  8. 8. B · Θ(n log n)

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