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

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

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

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

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

1.Легка

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

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

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

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

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

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

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

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

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

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

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

Яка часова складність: for i = 1 to n: for (j = i; j ≤ n; j = j + i) виконати роботу O(1)?

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

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

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

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

  1. 1. A · O(log n)
  2. 2. D · «Розділяй і володарюй»
  3. 3. B · Масив має бути відсортованим
  4. 4. D · O(n²)
  5. 5. C · O(1)
  6. 6. B · O(n log n)
  7. 7. A · O(n log n)
  8. 8. C · Належить до NP і будь-яка задача з NP зводиться до неї за поліноміальний час

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