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

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

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

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

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

1.Легка

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

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

Що таке рекурсія?

  1. AМетод сортування
  2. BЦикл, який ніколи не закінчується
  3. CФункція, яка викликає саму себе для менших вхідних даних
  4. DТип структури даних
3.Легка

Яка нотація описує верхню межу зростання?

  1. AВелике O
  2. BВелике Омега
  3. CВелике Тета
  4. DМале омега
4.Середня

Швидке сортування завжди бере опорним перший елемент. На яких вхідних даних воно демонструє поведінку найгіршого випадку?

  1. AНа масиві, всі елементи якого різні
  2. BНа вже відсортованому масиві
  3. CНа масиві довжини 2
  4. DНа масиві у випадковому порядку
5.Середня

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

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

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

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

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

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

Яке твердження про позначення «мале o» правильне?

  1. An² = o(n)
  2. B2n = o(n), бо 2n зростає повільно
  3. Cn = o(n), бо кожна функція є «мале o» від самої себе
  4. Dn = o(n²), але n не є o(n)

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

  1. 1. C · Швидке сортування (quicksort)
  2. 2. C · Функція, яка викликає саму себе для менших вхідних даних
  3. 3. A · Велике O
  4. 4. B · На вже відсортованому масиві
  5. 5. A · O(n²)
  6. 6. D · O(2ⁿ)
  7. 7. B · O(n log n)
  8. 8. D · n = o(n²), але n не є o(n)

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