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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Каковы три шага алгоритма «разделяй и властвуй»?

  1. AРазделить, решить (властвовать), объединить
  2. BОтсортировать, найти, вернуть
  3. CПрочитать, вычислить, записать
  4. DУгадать, проверить, повторить
2.Лёгкая

Что описывает время работы алгоритма в худшем случае?

  1. AВремя на медленном компьютере
  2. BМаксимальное время по всем входам размера n
  3. CВремя на самом маленьком входе
  4. DОжидаемое время на случайном входе размера n
3.Лёгкая

Доступ к элементу массива по индексу занимает:

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

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

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

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

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

Решением рекуррентного соотношения T(n) = 2T(n/2) + O(n) является:

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

Алгоритм Штрассена умножает матрицы, используя 7 вместо 8 рекурсивных умножений блоков половинного размера. Каково время его работы?

  1. AΘ(n2)
  2. BΘ(nlog₂ 7), примерно n2,81
  3. CΘ(n² log n)
  4. DΘ(n³)
8.Сложная

Как соотносятся n! и 2ⁿ при больших n?

  1. AОни растут с одинаковой скоростью
  2. Bn! есть O(n²)
  3. Cn! растёт быстрее 2ⁿ
  4. D2ⁿ растёт быстрее n!

Ответы

  1. 1. A · Разделить, решить (властвовать), объединить
  2. 2. B · Максимальное время по всем входам размера n
  3. 3. C · O(1)
  4. 4. C · O(d(n + k))
  5. 5. B · O(log n)
  6. 6. C · O(n log n)
  7. 7. B · Θ(nlog₂ 7), примерно n2,81
  8. 8. C · n! растёт быстрее 2ⁿ

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