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

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

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

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

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

1.Легка

Який клас складності зростає найшвидше для великих n?

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

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

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

Що бінарний пошук вимагає від вхідних даних?

  1. AДовжина масиву має бути степенем двійки
  2. BМасив має містити не більше 1000 елементів
  3. CМасив має містити лише додатні числа
  4. DМасив має бути відсортованим
4.Середня

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

  1. AБлизько n / 2
  2. BБлизько n
  3. CБлизько √n
  4. DБлизько log₂ n
5.Середня

Яка часова складність стандартного алгоритму динамічного програмування для найдовшої спільної підпослідовності рядків довжиною m і n?

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

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

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

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

  1. AO(V + E)
  2. BO(V³)
  3. CO(V × E)
  4. DO((V + E) log V)
8.Складна

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

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

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

  1. 1. C · O(2ⁿ)
  2. 2. B · «Розділяй і володарюй»
  3. 3. D · Масив має бути відсортованим
  4. 4. D · Близько log₂ n
  5. 5. C · O(mn)
  6. 6. B · Середню вартість операції на послідовності операцій у найгіршому випадку
  7. 7. D · O((V + E) log V)
  8. 8. C · Ні, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено

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