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

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

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

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

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

1.Легка

Яка оцінка «велике O» для 3n² + 5n + 2?

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

Що таке базовий випадок рекурсивної функції?

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

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

  1. Ao (мале o)
  2. BO (велике O)
  3. CΩ (велике Омега)
  4. DΘ (велике Тета)
4.Середня

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

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

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

  1. AБлизько n / 2
  2. BБлизько log₂ n
  3. CБлизько n
  4. DБлизько √n
6.Середня

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

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

Який прийом забезпечує очікуваний час роботи O(n log n) для швидкого сортування на будь-яких вхідних даних?

  1. AВибір завжди першого елемента
  2. BСортування вхідних даних перед запуском швидкого сортування
  3. CВибір опорного елемента випадково з рівномірним розподілом
  4. DЗастосування рекурсії лише до лівої частини
8.Складна

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

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

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

  1. 1. A · O(n²)
  2. 2. A · Випадок, на який відповідають безпосередньо, без нового рекурсивного виклику
  3. 3. C · Ω (велике Омега)
  4. 4. B · O(n)
  5. 5. B · Близько log₂ n
  6. 6. B · O(log n)
  7. 7. C · Вибір опорного елемента випадково з рівномірним розподілом
  8. 8. A · 2-SAT, де кожен диз'юнкт має щонайбільше два літерали

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