Тест по предмету «Информатика» на тему «Рекурсия»
- Какие утверждения о рекурсивной функции верны?
A. Рекурсивная функция содержит вызов самой себя
B. В рекурсивной функции обязательно должно быть условие выхода (базовый случай)
C. Рекурсивная функция не может принимать аргументы
D. Если условие выхода отсутствует, рекурсия может привести к переполнению стека вызовов
- Дана функция вычисления факториала:
def fact(n):
return 1 if n == 0 else n * fact(n - 1)
Какие утверждения верны?
A. fact(0) возвращает 1
B. При вычислении fact(5) функция вызывается 6 раз, включая первоначальный вызов
C. Значение fact(5) равно 120
D. Значение fact(-1) определено и равно 1
- Какие утверждения о наивном рекурсивном вычислении чисел Фибоначчи верны?
A. Функция вида fib(n) = fib(n-1) + fib(n-2) без мемоизации многократно повторно вычисляет одни и те же значения
B. Число вызовов при наивной рекурсии растёт экспоненциально с увеличением n
C. Наивная рекурсивная реализация всегда работает быстрее итеративной
D. Базовыми случаями являются fib(0) = 0 и fib(1) = 1
- Какие утверждения о стеке вызовов верны?
A. При каждом рекурсивном вызове создаётся новый кадр (запись) в стеке вызовов
B. Слишком глубокая рекурсия может вызвать ошибку переполнения стека
C. Стек вызовов работает по принципу FIFO: первым пришёл — первым вышел
D. Локальные переменные каждого вызова хранятся, пока этот вызов не завершится
- Какие утверждения о задаче «Ханойские башни» верны?
A. Минимальное число перемещений для n дисков равно 2^n − 1
B. Для трёх дисков достаточно 7 перемещений
C. Рекурсивное решение: перенести n − 1 диск на вспомогательный стержень, затем самый большой диск на целевой, затем n − 1 диск на целевой
D. Для четырёх дисков достаточно 8 перемещений
