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

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

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

Доступ до елемента масиву за індексом займає:

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(n²)

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

1. A2 секунди
2. B4 секунди
3. C8 секунд
4. D1 секунду

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

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

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

1. AO(n)
2. BO(1)
3. CO(log n)
4. DO(n²)

Динамічне програмування корисне, коли задача має:

1. AПерекривні підзадачі та оптимальну підструктуру
2. BЖодних підзадач, тож її можна розв'язати за один крок
3. CОдин цикл
4. DЛише випадкові вхідні дані

Що встановила теорема Кука–Левіна?

1. AКожну задачу з NP можна розв'язати за експоненційний час
2. BПроблема зупинки нерозв'язна
3. CЗадача виконуваності булевих формул (SAT) є NP-повною
4. DP не дорівнює NP

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

1. AO(V + E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V × E)