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

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

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

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

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

1.Легка

Яка часова складність сортування вставками в найкращому випадку, на вже відсортованому масиві?

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

Як називається зростання O(2ⁿ)?

  1. AЛінійне
  2. BПоліноміальне
  3. CЕкспоненційне
  4. DЛогарифмічне
3.Легка

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

  1. AСортування злиттям
  2. BШвидке сортування (quicksort)
  3. CСортування вставками
  4. DСортування бульбашкою
4.Середня

Що вимірює амортизований аналіз?

  1. AВартість однієї найдорожчої операції будь-де в послідовності
  2. BВартість алгоритму на найкращих вхідних даних
  3. CСередню вартість операції на послідовності операцій у найгіршому випадку
  4. DОчікувану вартість на випадкових вхідних даних
5.Середня

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

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

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

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

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

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

Які часові та просторові витрати обчислення n-го числа Фібоначчі циклом, що зберігає лише два останні значення?

  1. AO(2ⁿ) часу та O(1) пам'яті
  2. BO(log n) часу та O(n) пам'яті
  3. CO(n) часу та O(1) пам'яті
  4. DO(n) часу та O(n) пам'яті

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

  1. 1. D · O(n)
  2. 2. C · Експоненційне
  3. 3. B · Швидке сортування (quicksort)
  4. 4. C · Середню вартість операції на послідовності операцій у найгіршому випадку
  5. 5. A · O(1)
  6. 6. D · O(n log n)
  7. 7. A · Кожна задача з P також належить до NP
  8. 8. C · O(n) часу та O(1) пам'яті

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