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

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

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

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

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

1.Легка

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

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

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

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

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

  1. AАлгоритм Краскала
  2. BУ всіх випадках потрібен алгоритм Беллмана–Форда
  3. CПошук у глибину (DFS)
  4. DАлгоритм Дейкстри
5.Середня

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

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

Динамічне програмування корисне, коли задача має:

  1. AЖодних підзадач, тож її можна розв'язати за один крок
  2. BПерекривні підзадачі та оптимальну підструктуру
  3. CЛише випадкові вхідні дані
  4. DОдин цикл
7.Складна

Проблема зупинки показує, що:

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

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

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

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

  1. 1. B · O(n²)
  2. 2. D · O(2ⁿ)
  3. 3. C · O(log n)
  4. 4. D · Алгоритм Дейкстри
  5. 5. C · O(2ⁿ)
  6. 6. B · Перекривні підзадачі та оптимальну підструктуру
  7. 7. A · Жоден алгоритм не може для кожної програми та вхідних даних визначити, чи зупиниться вона
  8. 8. B · n = o(n²), але n не є o(n)

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