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

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

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

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

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

1.Легка

Що означає, що операція виконується за час O(1)?

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

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

  1. A9 секунд
  2. B3 секунди
  3. C6 секунд
  4. D12 секунд
3.Легка

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

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

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

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

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

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

Жадібний алгоритм:

  1. AПеребирає всі можливі розв'язки
  2. BВикористовує лише рекурсію
  3. CНа кожному кроці робить локально найкращий вибір
  4. DЗавжди дає оптимальний розв'язок
7.Складна

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

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

Який прийом забезпечує очікуваний час роботи O(n log n) для швидкого сортування на будь-яких вхідних даних?

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

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

  1. 1. A · Її час виконання не зростає з розміром вхідних даних
  2. 2. C · 6 секунд
  3. 3. A · O(V + E)
  4. 4. D · O(n²)
  5. 5. C · Вона викликає себе, доки не переповниться стек викликів
  6. 6. C · На кожному кроці робить локально найкращий вибір
  7. 7. A · Кожна задача з P також належить до NP
  8. 8. D · Вибір опорного елемента випадково з рівномірним розподілом

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