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

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

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

Що означає, що операція виконується за час O(1)?

1. AВона обробляє рівно один елемент за секунду часу виконання
2. BЇї час виконання не зростає з розміром вхідних даних
3. CЇї можна виконати лише один раз
4. DВона завжди триває рівно одну секунду

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

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

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

1. AБлизько 500,000
2. BБлизько 1,000
3. CБлизько 20
4. DБлизько 100

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

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

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

Яке визначення класу P правильне?

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

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

1. AАлгоритм Флойда–Воршелла
2. BАлгоритм Краскала
3. CАлгоритм Дейкстри
4. DАлгоритм Прима, що починає з однієї вершини