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

Як працює сортування вибором?

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Випадок із найбільшими вхідними даними, який обробляється до будь-яких рекурсивних викликів
4. DВиклик, що використовує найбільше пам'яті

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

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

Швидке сортування завжди бере опорним перший елемент. На яких вхідних даних воно демонструє поведінку найгіршого випадку?

1. AНа масиві довжини 2
2. BНа масиві у випадковому порядку
3. CНа масиві, всі елементи якого різні
4. DНа вже відсортованому масиві

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

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

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

1. AДоступ до масивів має складність O(n)
2. BКлючі спершу потрібно відсортувати
3. CБагато ключів через колізії можуть потрапити в один і той самий кошик
4. DГеш-функції повільні

Як співвідносяться n! і 2ⁿ для великих n?

1. An! зростає швидше, ніж 2ⁿ
2. Bn! є O(n²)
3. CВони зростають з однаковою швидкістю
4. D2ⁿ зростає швидше, ніж n!