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

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

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

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

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

1.Легка

Алгоритм O(n) працює 3 секунди для n = 1 мільйон. Приблизно скільки він працюватиме для n = 2 мільйони?

  1. A3 секунди
  2. B12 секунд
  3. C9 секунд
  4. D6 секунд
2.Легка

Який клас складності зростає найшвидше для великих n?

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

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

  1. AМале омега
  2. BВелике Омега
  3. CВелике Тета
  4. DВелике O
4.Середня

Що обчислює алгоритм Флойда–Воршелла і як швидко?

  1. AНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
  2. BНайкоротші шляхи між усіма парами вершин за O(V³)
  3. CМінімальне кістякове дерево за O(E log V)
  4. DТопологічний порядок за O(V²)
5.Середня

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

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

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

  1. AO(2ⁿ)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)
7.Складна

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

  1. AТак, отже, нижня межа хибна
  2. BТак, але лише для масивів, коротших за 100
  3. CНі, бо сортування вставками не є сортуванням порівняннями
  4. DНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
8.Складна

Задача є NP-повною, якщо вона:

  1. AРозв'язна за поліноміальний час
  2. BНерозв'язна
  3. CНалежить до NP і будь-яка задача з NP зводиться до неї за поліноміальний час
  4. DЛежить поза NP, але складніша за всі задачі NP, як-от проблема зупинки

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

  1. 1. D · 6 секунд
  2. 2. C · O(2ⁿ)
  3. 3. D · Велике O
  4. 4. B · Найкоротші шляхи між усіма парами вершин за O(V³)
  5. 5. D · O(n)
  6. 6. A · O(2ⁿ)
  7. 7. D · Ні, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
  8. 8. C · Належить до NP і будь-яка задача з NP зводиться до неї за поліноміальний час

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