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

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

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

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

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

1.Легка

Яка часова складність лінійного пошуку в невідсортованому масиві з n елементів (у найгіршому випадку)?

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

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

  1. AЖадібний вибір
  2. BДинамічне програмування
  3. CПовний перебір
  4. D«Розділяй і володарюй»
3.Легка

Задачу зазвичай називають практично розв'язною (tractable), якщо:

  1. AВона не має розв'язку
  2. BЇї можна розв'язати за сталий час
  3. CЇї можна розв'язати лише перебором усіх можливостей
  4. DЇї можна розв'язати за поліноміальний час
4.Середня

У відсортованому масиві ви шукаєте два елементи із заданою сумою, рухаючи по одному вказівнику з кожного кінця всередину. Яка часова складність?

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

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

Множення Карацуби задовольняє T(n) = 3T(n/2) + O(n). Який розв'язок?

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

Яке твердження про позначення «мале o» правильне?

  1. An = o(n), бо кожна функція є «мале o» від самої себе
  2. B2n = o(n), бо 2n зростає повільно
  3. Cn = o(n²), але n не є o(n)
  4. Dn² = o(n)

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

  1. 1. B · O(n)
  2. 2. D · «Розділяй і володарюй»
  3. 3. D · Її можна розв'язати за поліноміальний час
  4. 4. C · O(n)
  5. 5. A · O(n log n)
  6. 6. D · O(n²)
  7. 7. A · Θ(nlog₂ 3), близько n1,585
  8. 8. C · n = o(n²), але n не є o(n)

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