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

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

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

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

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

1.Легка

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

  1. AO (велике O)
  2. BΩ (велике Омега)
  3. CΘ (велике Тета)
  4. Do (мале o)
2.Легка

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

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

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

  1. AЧас на повільному комп'ютері
  2. BОчікуваний час на випадкових вхідних даних розміру n
  3. CЧас на найменших вхідних даних
  4. DМаксимальний час на всіх вхідних даних розміру n
4.Середня

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

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

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

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

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

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

Алгоритм динамічного програмування Гелда–Карпа точно розв'язує задачу комівояжера. Який його час виконання для n міст?

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

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

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

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

  1. 1. B · Ω (велике Омега)
  2. 2. D · O(n)
  3. 3. D · Максимальний час на всіх вхідних даних розміру n
  4. 4. B · O(n²)
  5. 5. D · O(n)
  6. 6. B · O(n²)
  7. 7. C · O(n² 2ⁿ)
  8. 8. A · Ні, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних

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