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

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

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

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

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

1.Легка

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

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

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

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

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

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

Пошук у ширину в незваженому графі знаходить:

  1. AМінімальне кістякове дерево
  2. BНайкоротші шляхи (за кількістю ребер) від початкової вершини
  3. CТопологічний порядок у будь-якому графі
  4. DНайкоротші шляхи в графах, що містять ребра з від'ємними вагами
5.Середня

Як алгоритм Прима будує мінімальне кістякове дерево?

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

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

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

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

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

Яке твердження про вибір k-го найменшого елемента невідсортованого масиву правильне?

  1. AВибір можливий лише за O(n²)
  2. BQuickselect працює за O(log n) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента
  3. CQuickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
  4. DВибір завжди потребує Ω(n log n), бо вимагає сортування

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

  1. 1. A · Сортування бульбашкою
  2. 2. A · O(n²)
  3. 3. B · Максимальний час на всіх вхідних даних розміру n
  4. 4. B · Найкоротші шляхи (за кількістю ребер) від початкової вершини
  5. 5. B · Він вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
  6. 6. D · O(n)
  7. 7. B · Ні, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено
  8. 8. C · Quickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку

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