1.Легка
Що означає f(n) = Θ(g(n))?
- Af завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
- Bf зростає строго повільніше, ніж g
- Cf зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
- Df зростає строго швидше, ніж g
2.Легка
Доступ до елемента масиву за індексом займає:
- AO(1)
- BO(n²)
- CO(log n)
- DO(n)
3.Легка
Яка часова складність пошуку в глибину на графі, збереженому у вигляді списків суміжності?
- AO(V²)
- BO(V × E)
- CO(V + E)
- DO(E log V)
4.Середня
Яка амортизована часова складність додавання елемента в кінець динамічного масиву, який подвоює свою місткість у разі заповнення?
- AO(n)
- BO(log n)
- CO(1)
- DO(n²)
5.Середня
Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?
- AO(n³)
- BO(n log n)
- CO(n)
- DO(n²)
6.Середня
Динамічне програмування корисне, коли задача має:
- AОдин цикл
- BЛише випадкові вхідні дані
- CПерекривні підзадачі та оптимальну підструктуру
- DЖодних підзадач, тож її можна розв'язати за один крок
7.Складна
Які дві речі треба показати, щоб довести, що задача розпізнавання X є NP-повною?
- AX належить до P, і X зводиться до SAT
- BX зводиться до задачі з P, і X належить до NP
- CX належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
- DX не має поліноміального алгоритму, і X розв'язна
8.Складна
Яка часова складність: for i = 1 to n: for (j = i; j ≤ n; j = j + i) виконати роботу O(1)?
- AO(n)
- BO(n²)
- CO(n log n)
- DO(n √n)
Ключ відповідей
- 1. C · f зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
- 2. A · O(1)
- 3. C · O(V + E)
- 4. C · O(1)
- 5. D · O(n²)
- 6. C · Перекривні підзадачі та оптимальну підструктуру
- 7. C · X належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
- 8. C · O(n log n)
Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.