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

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

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

Які три кроки алгоритму «розділяй і володарюй»?

1. AВідсортувати, знайти, повернути
2. BРозділити, підкорити, об'єднати
3. CВгадати, перевірити, повторити
4. DПрочитати, обчислити, записати

Що таке алгоритм повного перебору?

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

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

1. AАлгоритм Краскала
2. BПошук у глибину (DFS)
3. CАлгоритм Дейкстри
4. DУ всіх випадках потрібен алгоритм Беллмана–Форда

Що обчислює алгоритм Флойда–Воршелла і як швидко?

1. AНайкоротші шляхи між усіма парами вершин за O(V³)
2. BМінімальне кістякове дерево за O(E log V)
3. CТопологічний порядок за O(V²)
4. DНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)

Яке твердження про позначення «мале o» правильне?

1. An² = o(n)
2. Bn = o(n²), але n не є o(n)
3. Cn = o(n), бо кожна функція є «мале o» від самої себе
4. D2n = o(n), бо 2n зростає повільно

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

1. AНевідомої якості порівняно з оптимумом
2. BЩонайбільше вдвічі більше за мінімальне вершинне покриття
3. CЩонайбільше в log n разів більше за мінімум
4. DЗавжди мінімальне вершинне покриття