1.Легка
Як працює сортування вибором?
- AВоно багаторазово знаходить мінімум невідсортованої частини й переставляє його на початок
- BВоно вставляє кожен елемент у відсортовану частину, що зростає, зсуваючи елементи
- CВоно багаторазово переставляє сусідні елементи, що стоять у неправильному порядку
- DВоно ділить масив навпіл і зливає половини
2.Легка
Яка часова складність сортування вставками в найкращому випадку, на вже відсортованому масиві?
- AO(n log n)
- BO(1)
- CO(n)
- DO(n²)
3.Легка
Що з наведеного зростає найповільніше зі збільшенням n?
- AO(n log n)
- BO(n)
- CO(log n)
- DO(n²)
4.Середня
Який алгоритм сортування є стійким?
- AШвидке сортування (типова версія на місці)
- BСортування вибором (типова версія)
- CСортування злиттям
- DПірамідальне сортування
5.Середня
Що обчислює алгоритм Флойда–Воршелла і як швидко?
- AМінімальне кістякове дерево за O(E log V)
- BТопологічний порядок за O(V²)
- CНайкоротші шляхи між усіма парами вершин за O(V³)
- DНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
6.Середня
Яка часова складність швидкого сортування (quicksort) у найгіршому випадку?
- AO(n log n)
- BO(n²)
- CO(n)
- DO(log n)
7.Складна
Яка часова складність: for i = 1 to n: for (j = i; j ≤ n; j = j + i) виконати роботу O(1)?
- AO(n)
- BO(n √n)
- CO(n²)
- DO(n log n)
8.Складна
Який розв'язок рекурентного співвідношення T(n) = 2T(n/2) + n log n?
- AΘ(n log n)
- BΘ(n log² n)
- CΘ(n)
- DΘ(n²)
Ключ відповідей
- 1. A · Воно багаторазово знаходить мінімум невідсортованої частини й переставляє його на початок
- 2. C · O(n)
- 3. C · O(log n)
- 4. C · Сортування злиттям
- 5. C · Найкоротші шляхи між усіма парами вершин за O(V³)
- 6. B · O(n²)
- 7. D · O(n log n)
- 8. B · Θ(n log² n)
Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.