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

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

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

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

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

1.Легка

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

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

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

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

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

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

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

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

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

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

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

Топологічне сортування можливе лише для:

  1. AНеорієнтованих графів
  2. BГрафів із від'ємними вагами
  3. CПовних графів
  4. DОрієнтованих ациклічних графів
8.Складна

Чому бінарний пошук не дає часу O(log n) на однозв'язному списку?

  1. AБінарному пошуку потрібно щонайменше вдвічі більше пам'яті
  2. BЩоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом
  3. CЗв'язні списки неможливо сортувати
  4. DПорівняння вузлів зв'язного списку повільніші

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

  1. 1. B · O(n)
  2. 2. C · Її час виконання не зростає з розміром вхідних даних
  3. 3. D · O(log n)
  4. 4. B · O(log n)
  5. 5. B · O(n)
  6. 6. B · O(n log n)
  7. 7. D · Орієнтованих ациклічних графів
  8. 8. B · Щоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом

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