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

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

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

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

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

1.Легка

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

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

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

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

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

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

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

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

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

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

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

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

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

  1. AПроблема зупинки стала б розв'язною
  2. BКожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
  3. CУсі алгоритми з експоненційним часом негайно стали б працювати за лінійний час
  4. DЛише ця одна задача перейшла б до P
8.Складна

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

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

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

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

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