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

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

1. A«Розділяй і володарюй»
2. BЖадібний вибір
3. CПовний перебір
4. DДинамічне програмування

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

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

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

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

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

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

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

1. AЛінійною
2. BЕкспоненційною
3. CЛогарифмічною
4. DСталою

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

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

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

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

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

1. AТак, але лише для масивів, коротших за 100
2. BТак, отже, нижня межа хибна
3. CНі, бо сортування вставками не є сортуванням порівняннями
4. DНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних