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

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

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

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

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

1.Легка

Яке позначення описує нижню межу зростання?

  1. AO (велике O)
  2. BΘ (велике Тета)
  3. CΩ (велике Омега)
  4. Do (мале o)
2.Легка

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

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

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

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

Який час виконання порозрядного сортування LSD для n цілих чисел із d цифрами в системі числення з основою k?

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

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

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

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

  1. AЛогарифмічною
  2. BЛінійною
  3. CЕкспоненційною
  4. DСталою
7.Складна

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

  1. AКожен елемент треба порівняти щонайменше один раз
  2. BДерево рішень з n можливими результатами має глибину щонайменше log₂ n
  3. CКожне порівняння триває логарифмічний час
  4. DБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
8.Складна

За основною теоремою (master theorem) розв'язком T(n) = 8T(n/2) + O(n²) є:

  1. AΘ(n²)
  2. BΘ(n² log n)
  3. CΘ(n log n)
  4. DΘ(n³)

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

  1. 1. C · Ω (велике Омега)
  2. 2. A · O(n)
  3. 3. D · O(V + E)
  4. 4. C · O(d(n + k))
  5. 5. C · O(n)
  6. 6. C · Експоненційною
  7. 7. B · Дерево рішень з n можливими результатами має глибину щонайменше log₂ n
  8. 8. D · Θ(n³)

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