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

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

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

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

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

1.Легка

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

  1. AВелике Омега
  2. BМале омега
  3. CВелике O
  4. DВелике Тета
2.Легка

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

  1. AБлизько log₂ n
  2. BБлизько n
  3. CБлизько n / 2
  4. DБлизько n²
3.Легка

Що таке алгоритм?

  1. AСкінченна послідовність чітко визначених кроків, що розв'язує задачу
  2. BБудь-яка комп'ютерна програма з графічним інтерфейсом
  3. CМова програмування, призначена для запису математичних формул
  4. DСтруктура даних, що зберігає числа
4.Середня

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

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

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

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

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

  1. AБлизько log₂ n
  2. BБлизько n / 2
  3. CБлизько √n
  4. DБлизько n
7.Складна

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

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

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

  1. AW — число, тому час експоненційний відносно кількості бітів, використаних для запису W
  2. BТому що він працює лише для W = 0
  3. CТому що n завжди мале
  4. DТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних

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

  1. 1. C · Велике O
  2. 2. A · Близько log₂ n
  3. 3. A · Скінченна послідовність чітко визначених кроків, що розв'язує задачу
  4. 4. C · O(n²)
  5. 5. A · O(1)
  6. 6. A · Близько log₂ n
  7. 7. B · Кожна задача з P також належить до NP
  8. 8. A · W — число, тому час експоненційний відносно кількості бітів, використаних для запису W

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