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

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

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

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

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

1.Легка

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

  1. A2 секунди
  2. B8 секунд
  3. C4 секунди
  4. D1 секунду
2.Легка

Що означає f(n) = Θ(g(n))?

  1. Af зростає строго швидше, ніж g
  2. Bf зростає строго повільніше, ніж g
  3. Cf завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
  4. Df зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
3.Легка

Яка часова складність пошуку в глибину на графі, збереженому у вигляді списків суміжності?

  1. AO(V²)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V + E)
4.Середня

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

  1. AВона виконується за час O(1)
  2. BВона автоматично повертає 0
  3. CВона викликає себе, доки не переповниться стек викликів
  4. DКомпілятор завжди перетворює її на цикл, що безпечно завершується
5.Середня

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

  1. AO(E log V)
  2. BO(V + E)
  3. CO(V³ × E)
  4. DO(V × E)
6.Середня

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

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

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

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

Що встановила теорема Кука–Левіна?

  1. AP не дорівнює NP
  2. BПроблема зупинки нерозв'язна
  3. CКожну задачу з NP можна розв'язати за експоненційний час
  4. DЗадача виконуваності булевих формул (SAT) є NP-повною

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

  1. 1. C · 4 секунди
  2. 2. D · f зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
  3. 3. D · O(V + E)
  4. 4. C · Вона викликає себе, доки не переповниться стек викликів
  5. 5. D · O(V × E)
  6. 6. B · O(log n)
  7. 7. A · O(n) часу та O(1) пам'яті
  8. 8. D · Задача виконуваності булевих формул (SAT) є NP-повною

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