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

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

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

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

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

1.Легка

Що таке мемоізація?

  1. AЗбереження результатів викликів функції, щоб повторні виклики отримували відповідь із пам'яті
  2. BЗвільнення пам'яті після повернення з функції
  3. CНаписання коментарів біля кожного рядка коду
  4. DАвтоматичне перетворення рекурсії на рівносильний цикл, щоб стек викликів не був потрібен
2.Легка

Що бінарний пошук вимагає від вхідних даних?

  1. AМасив має бути відсортованим
  2. BДовжина масиву має бути степенем двійки
  3. CМасив має містити не більше 1000 елементів
  4. DМасив має містити лише додатні числа
3.Легка

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

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

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

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

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

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

  1. AЖадібний використовує 3 монети; оптимум — 2
  2. BЖадібний використовує 3 монети; оптимум — 3
  3. CЖадібний використовує 2 монети; оптимум — 2
  4. DЖадібний використовує 4 монети; оптимум — 3
7.Складна

Яка оцінка для log(n!) правильна?

  1. AΘ(n log n)
  2. BΘ(log n)
  3. CΘ(n)
  4. DΘ(n²)
8.Складна

Що встановила теорема Кука–Левіна?

  1. AКожну задачу з NP можна розв'язати за експоненційний час
  2. BПроблема зупинки нерозв'язна
  3. CP не дорівнює NP
  4. DЗадача виконуваності булевих формул (SAT) є NP-повною

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

  1. 1. A · Збереження результатів викликів функції, щоб повторні виклики отримували відповідь із пам'яті
  2. 2. A · Масив має бути відсортованим
  3. 3. D · O(n + k)
  4. 4. C · O(n)
  5. 5. A · O(n²)
  6. 6. A · Жадібний використовує 3 монети; оптимум — 2
  7. 7. A · Θ(n log n)
  8. 8. D · Задача виконуваності булевих формул (SAT) є NP-повною

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