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

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

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

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

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

1.Легка

Яка часова складність бінарного пошуку у відсортованому масиві?

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

Який із цих часів виконання є поліноміальним?

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

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

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

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

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

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

  1. AКожне порівняння триває логарифмічний час
  2. BКожен елемент треба порівняти щонайменше один раз
  3. CБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
  4. DДерево рішень з n можливими результатами має глибину щонайменше log₂ n
8.Складна

Яке твердження про P і NP є правильним?

  1. AДоведено, що P ≠ NP
  2. BКожна задача з P також належить до NP
  3. CРозв'язки задач NP неможливо швидко перевірити
  4. DNP означає «неполіноміальний» (not polynomial)

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

  1. 1. C · O(log n)
  2. 2. D · O(n³)
  3. 3. C · O(n²)
  4. 4. B · O(n)
  5. 5. D · O(n log n)
  6. 6. A · O(n log n + k log n)
  7. 7. D · Дерево рішень з n можливими результатами має глибину щонайменше log₂ n
  8. 8. B · Кожна задача з P також належить до NP

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