Робочий аркуш «Алгоритми та складність» з відповідями

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

Новий робочий аркушТренуватися онлайн з підказками

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

Ім’я: ____________________   Дата: ____________

1.Легка

Яка нотація описує верхню межу зростання?

  1. AВелике Тета
  2. BВелике O
  3. CМале омега
  4. DВелике Омега
2.Легка

Яка оцінка «велике O» для 3n² + 5n + 2?

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

Як називається зростання O(2ⁿ)?

  1. AЛогарифмічне
  2. BЕкспоненційне
  3. CПоліноміальне
  4. DЛінійне
4.Середня

Який розв'язок рекурентного співвідношення T(n) = T(n − 1) + O(n)?

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

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

  1. AВона виконується за час O(1)
  2. BКомпілятор завжди перетворює її на цикл, що безпечно завершується
  3. CВона автоматично повертає 0
  4. DВона викликає себе, доки не переповниться стек викликів
6.Середня

Що означає, що задача має оптимальну підструктуру?

  1. AУсі підзадачі мають однаковий розмір
  2. BЗадачу можна розв'язати за сталий час
  3. CЗадача має рівно один оптимальний розв'язок, спільний для кожної підзадачі
  4. DОптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
7.Складна

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

  1. AΘ(n³)
  2. BΘ(nlog₂ 7), близько n2,81
  3. CΘ(n² log n)
  4. DΘ(n2)
8.Складна

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

  1. AO(V + E)
  2. BO((V + E) log V)
  3. CO(V³)
  4. DO(V × E)

Ключ відповідей

  1. 1. B · Велике O
  2. 2. C · O(n²)
  3. 3. B · Експоненційне
  4. 4. A · O(n²)
  5. 5. D · Вона викликає себе, доки не переповниться стек викликів
  6. 6. D · Оптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
  7. 7. B · Θ(nlog₂ 7), близько n2,81
  8. 8. B · O((V + E) log V)

Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.