1.Лёгкая
Что такое мемоизация?
- AОсвобождение памяти после возврата из функции
- BНаписание комментариев рядом с каждой строкой кода
- CАвтоматическое преобразование рекурсии в эквивалентный цикл, так что стек вызовов не нужен
- DСохранение результатов вызовов функции, чтобы повторные вызовы получали ответ из памяти
2.Лёгкая
Какая нотация описывает верхнюю границу роста?
- AO-большое
- BОмега-большое
- CОмега-малое
- DТета-большое
3.Лёгкая
Какое из этих времён работы полиномиально?
- AO(2ⁿ)
- BO(nⁿ)
- CO(n³)
- DO(n!)
4.Средняя
Какова временная сложность быстрой сортировки (quicksort) в худшем случае?
- AO(n)
- BO(n log n)
- CO(n²)
- DO(log n)
5.Средняя
Жадный алгоритм:
- AНа каждом шаге делает локально наилучший выбор
- BПеребирает все возможные решения
- CВсегда даёт оптимальное решение
- DИспользует только рекурсию
6.Средняя
Какова временна́я сложность: for i = 1 to n: for j = 1 to i: выполнить работу O(1)?
- AO(n)
- BO(n³)
- CO(n²)
- DO(n log n)
7.Сложная
Какое определение класса NP верно?
- AЗадачи, которые нельзя решить за полиномиальное время
- BЗадачи распознавания, положительные ответы которых можно проверить за полиномиальное время при наличии сертификата
- CЗадачи, которые не являются полиномиальными
- DЗадачи, которые не может решить ни один алгоритм
8.Сложная
Каково решение рекуррентного соотношения T(n) = 2T(n/2) + n log n?
- AΘ(n²)
- BΘ(n log n)
- CΘ(n log² n)
- DΘ(n)
Ответы
- 1. D · Сохранение результатов вызовов функции, чтобы повторные вызовы получали ответ из памяти
- 2. A · O-большое
- 3. C · O(n³)
- 4. C · O(n²)
- 5. A · На каждом шаге делает локально наилучший выбор
- 6. C · O(n²)
- 7. B · Задачи распознавания, положительные ответы которых можно проверить за полиномиальное время при наличии сертификата
- 8. C · Θ(n log² n)
Полные пошаговые решения: занимайтесь этой темой на examproblems.com.