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

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

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

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

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

1.Легка

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

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

Алгоритм O(n) працює 3 секунди для n = 1 мільйон. Приблизно скільки він працюватиме для n = 2 мільйони?

  1. A3 секунди
  2. B9 секунд
  3. C6 секунд
  4. D12 секунд
3.Легка

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

  1. AСортування бульбашкою
  2. BШвидке сортування (quicksort)
  3. CСортування вставками
  4. DСортування злиттям
4.Середня

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

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

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

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

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

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

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

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

Чи належить 22n до O(2ⁿ)?

  1. AТак, бо обидві функції експоненційні
  2. BТак, бо сталі множники в показнику степеня в нотації «велике O» завжди ігноруються
  3. CНі, бо 22n зростає повільніше, ніж 2ⁿ
  4. DНі, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено

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

  1. 1. D · O(n)
  2. 2. C · 6 секунд
  3. 3. B · Швидке сортування (quicksort)
  4. 4. C · O(n)
  5. 5. C · O(n)
  6. 6. B · O(n²)
  7. 7. D · Вибір опорного елемента випадково з рівномірним розподілом
  8. 8. D · Ні, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено

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