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

Яка часова складність пошуку в глибину на графі, збереженому у вигляді списків суміжності?

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

Задачу зазвичай називають практично розв'язною (tractable), якщо:

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

Що таке базовий випадок рекурсивної функції?

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

Що означає, що задача має оптимальну підструктуру?

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

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

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

Який алгоритм сортування є стійким?

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

Які дві речі треба показати, щоб довести, що задача розпізнавання X є NP-повною?

1. AX зводиться до задачі з P, і X належить до NP
2. BX належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
3. CX належить до P, і X зводиться до SAT
4. DX не має поліноміального алгоритму, і X розв'язна

Чому бінарний пошук не дає часу O(log n) на однозв'язному списку?

1. AПорівняння вузлів зв'язного списку повільніші
2. BБінарному пошуку потрібно щонайменше вдвічі більше пам'яті
3. CЩоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом
4. DЗв'язні списки неможливо сортувати