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

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

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

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

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

1.Легка

Який із цих часів виконання є поліноміальним?

  1. AO(n!)
  2. BO(2ⁿ)
  3. CO(nⁿ)
  4. DO(n³)
2.Легка

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

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

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

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

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

  1. AУ всіх випадках потрібен алгоритм Беллмана–Форда
  2. BАлгоритм Краскала
  3. CПошук у глибину (DFS)
  4. DАлгоритм Дейкстри
6.Середня

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

  1. AСпершу обрати найкоротшу заявку
  2. BОбрати заявку, що закінчується найраніше, а потім повторити із сумісними
  3. CОбрати заявку, що починається найраніше
  4. DСпершу обрати заявку з найменшою кількістю перекриттів, а потім повторити із сумісними
7.Складна

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

  1. A2-SAT, де кожен диз'юнкт має щонайбільше два літерали
  2. BВиконуваність схем
  3. CЗагальна SAT для формул у кон'юнктивній нормальній формі
  4. D3-SAT, де кожен диз'юнкт має рівно три літерали
8.Складна

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

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

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

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

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