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

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

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

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

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

1.Легка

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

  1. A8 секунд
  2. B4 секунди
  3. C1 секунду
  4. D2 секунди
2.Легка

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

  1. AЧас на найменших вхідних даних
  2. BОчікуваний час на випадкових вхідних даних розміру n
  3. CМаксимальний час на всіх вхідних даних розміру n
  4. DЧас на повільному комп'ютері
3.Легка

Що описує час виконання в середньому випадку?

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

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

  1. AO(V³ × E)
  2. BO(E log V)
  3. CO(V + E)
  4. DO(V × E)
6.Середня

У відсортованому масиві ви шукаєте два елементи із заданою сумою, рухаючи по одному вказівнику з кожного кінця всередину. Яка часова складність?

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

Як співвідносяться n! і 2ⁿ для великих n?

  1. An! є O(n²)
  2. BВони зростають з однаковою швидкістю
  3. Cn! зростає швидше, ніж 2ⁿ
  4. D2ⁿ зростає швидше, ніж n!
8.Складна

Який алгоритм знаходить мінімальне кістякове дерево, багаторазово додаючи найдешевше ребро, яке не утворює циклу?

  1. AАлгоритм Флойда–Воршелла
  2. BАлгоритм Дейкстри
  3. CАлгоритм Прима, що починає з однієї вершини
  4. DАлгоритм Краскала

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

  1. 1. B · 4 секунди
  2. 2. C · Максимальний час на всіх вхідних даних розміру n
  3. 3. B · Очікуваний час за заданого розподілу вхідних даних розміру n
  4. 4. B · O(n log n)
  5. 5. D · O(V × E)
  6. 6. A · O(n)
  7. 7. C · n! зростає швидше, ніж 2ⁿ
  8. 8. D · Алгоритм Краскала

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