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

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

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

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

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

1.Легка

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

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

Яка оцінка «велике O» для 3n² + 5n + 2?

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

Просторова складність вимірює:

  1. AМісце на диску, яке займає файл програми після компіляції
  2. BФізичний розмір комп'ютера
  3. CКількість рядків коду
  4. DОбсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
4.Середня

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

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

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

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

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

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

Чому алгоритм Дейкстри може давати неправильні результати, коли деякі ваги ребер від'ємні?

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

За основною теоремою (master theorem) розв'язком T(n) = 8T(n/2) + O(n²) є:

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

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

  1. 1. A · Масив має бути відсортованим
  2. 2. A · O(n²)
  3. 3. D · Обсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
  4. 4. C · O(n²)
  5. 5. C · O(2ⁿ)
  6. 6. B · Близько log₂ n
  7. 7. C · Вершину остаточно фіксують під час вилучення, але пізніше від'ємне ребро ще може дати їй коротший шлях
  8. 8. D · Θ(n³)

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