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

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

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

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

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

1.Легка

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

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

  1. A«Розділяй і володарюй»
  2. BДинамічне програмування
  3. CПовний перебір
  4. DЖадібний вибір
3.Легка

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

  1. AВелике O
  2. BВелике Омега
  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.Середня

Що вимірює амортизований аналіз?

  1. AОчікувану вартість на випадкових вхідних даних
  2. BВартість однієї найдорожчої операції будь-де в послідовності
  3. CВартість алгоритму на найкращих вхідних даних
  4. DСередню вартість операції на послідовності операцій у найгіршому випадку
6.Середня

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

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

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

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

Множення Карацуби задовольняє T(n) = 3T(n/2) + O(n). Який розв'язок?

  1. AΘ(n log n)
  2. BΘ(nlog₂ 3), близько n1,585
  3. CΘ(n²)
  4. DΘ(n3)

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

  1. 1. A · O(n + k)
  2. 2. A · «Розділяй і володарюй»
  3. 3. A · Велике O
  4. 4. C · O(n)
  5. 5. D · Середню вартість операції на послідовності операцій у найгіршому випадку
  6. 6. B · O(2ⁿ)
  7. 7. C · O(n log n)
  8. 8. B · Θ(nlog₂ 3), близько n1,585

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