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

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

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

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

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

1.Легка

Чому дорівнює log₂ 1024?

  1. A32
  2. B12
  3. C512
  4. D10
2.Легка

Доступ до елемента масиву за індексом займає:

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

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

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

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

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

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

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

  1. AO(V × E)
  2. BO(V³ × E)
  3. CO(V + E)
  4. DO(E log V)
7.Складна

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

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

Як співвідносяться n! і 2ⁿ для великих n?

  1. An! зростає швидше, ніж 2ⁿ
  2. B2ⁿ зростає швидше, ніж n!
  3. CВони зростають з однаковою швидкістю
  4. Dn! є O(n²)

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

  1. 1. D · 10
  2. 2. B · O(1)
  3. 3. A · O(n)
  4. 4. C · O(n)
  5. 5. C · O(n²)
  6. 6. A · O(V × E)
  7. 7. D · Кожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
  8. 8. A · n! зростає швидше, ніж 2ⁿ

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