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

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

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

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

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

1.Легка

Який клас складності зростає найшвидше для великих n?

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

Що таке алгоритм повного перебору?

  1. AАлгоритм, що вгадує відповідь випадково
  2. BАлгоритм, що завжди використовує рекурсію
  3. CАлгоритм, що виконується на багатьох процесорах
  4. DАлгоритм, що перебирає всі можливі кандидати на розв'язок
3.Легка

Що з наведеного зростає найповільніше зі збільшенням n?

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

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

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

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

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

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

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

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

  1. AДля рюкзака 0/1, де предмети завжди потрібно брати цілими
  2. BДля обох варіантів
  3. CДля жодного варіанта
  4. DДля неперервного (дробового) рюкзака, де предмети можна ділити

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

  1. 1. B · O(2ⁿ)
  2. 2. D · Алгоритм, що перебирає всі можливі кандидати на розв'язок
  3. 3. A · O(log n)
  4. 4. D · O(log n)
  5. 5. A · Експоненційною
  6. 6. A · O(n)
  7. 7. B · O(n)
  8. 8. D · Для неперервного (дробового) рюкзака, де предмети можна ділити

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