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

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

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

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

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

1.Легка

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

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

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

  1. AВелике O
  2. BМале омега
  3. CВелике Тета
  4. DВелике Омега
3.Легка

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

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

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

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

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

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

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

  1. AВона викликає себе, доки не переповниться стек викликів
  2. BКомпілятор завжди перетворює її на цикл, що безпечно завершується
  3. CВона виконується за час O(1)
  4. DВона автоматично повертає 0
7.Складна

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

  1. AВона нерозв'язна
  2. BЦе NP-складна задача
  3. CЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
  4. DЇї завжди можна розв'язати за O(V + E)
8.Складна

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

  1. AΘ(n)
  2. BΘ(n log² n)
  3. CΘ(n log n)
  4. DΘ(n²)

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

  1. 1. D · Ω (велике Омега)
  2. 2. A · Велике O
  3. 3. D · Швидке сортування (quicksort)
  4. 4. D · Середню вартість операції на послідовності операцій у найгіршому випадку
  5. 5. A · O(n)
  6. 6. A · Вона викликає себе, доки не переповниться стек викликів
  7. 7. B · Це NP-складна задача
  8. 8. B · Θ(n log² n)

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