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

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

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

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

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

1.Легка

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

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

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

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

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

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

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

  1. AРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
  2. BСортування вставками має складність O(n log n) у найгіршому випадку
  3. CСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  4. DСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних
5.Середня

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

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

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

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

Як класифікують задачу комівояжера?

  1. AВона належить до P, бо її розв'язує алгоритм Дейкстри, відвідуючи кожне місто один раз
  2. BВона нерозв'язна
  3. CВерсія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною
  4. DВерсія розпізнавання належить до P, а оптимізаційна — NP-повна
8.Складна

Чому бінарний пошук не дає часу O(log n) на однозв'язному списку?

  1. AБінарному пошуку потрібно щонайменше вдвічі більше пам'яті
  2. BЗв'язні списки неможливо сортувати
  3. CПорівняння вузлів зв'язного списку повільніші
  4. DЩоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом

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

  1. 1. C · O(n log n)
  2. 2. C · Швидке сортування (quicksort)
  3. 3. A · O(log n)
  4. 4. C · Сортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  5. 5. C · O(2ⁿ)
  6. 6. D · На вже відсортованому масиві
  7. 7. C · Версія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною
  8. 8. D · Щоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом

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