Просто УрокТест · Информатика
Рекурсия
Отвечай кликом — после каждого вопроса пояснение. 10 вопросов, 4 варианта, 3–5 минут. Без таймеров и регистрации.
Отвечено 0 из 10 · Верно: 0
1/10
Какой признак является основным для рекурсивной функции?
Пояснение. Рекурсивная функция прямо или косвенно вызывает саму себя. Для завершения такой функции обычно используют условие остановки.
2/10
Что задаёт условие остановки рекурсии?
Пояснение. Базовый случай определяет ситуацию, в которой функция прекращает рекурсивные вызовы. Без него рекурсия может продолжаться бесконечно.
3/10
Какая структура данных используется для хранения незавершённых рекурсивных вызовов?
Пояснение. Каждый вызов функции помещается в стек вызовов. После завершения вложенного вызова управление возвращается к предыдущему.
4/10
Чему равно значение функции fact(4), если fact(1)=1, а fact(n)=n·fact(n−1) при n>1?
Пояснение. Функция вычисляет произведение чисел от 1 до 4: 4·3·2·1=24. Поэтому значение fact(4) равно двадцати четырём.
5/10
Сколько раз выполнится базовый случай при вычислении fib(5), если fib(0)=0, fib(1)=1, а остальные значения получают двумя рекурсивными вызовами?
Пояснение. При наивном рекурсивном вычислении fib(5) листья дерева вызовов имеют значения fib(0) или fib(1). Таких базовых вызовов получается восемь.
6/10
Какой результат напечатает процедура f(3), если сначала вызывается f(n−1), а затем выводится n, при условии остановки n=0?
Пояснение. Сначала вызовы доходят до f(0), после чего завершаются в обратном порядке. Поэтому числа выводятся как 1, 2, 3.
7/10
Какова временная сложность рекурсивного двоичного поиска в отсортированном массиве?
Пояснение. На каждом шаге двоичный поиск уменьшает область поиска примерно в два раза. Поэтому его временная сложность равна O(log n).
8/10
Какова временная сложность наивного рекурсивного вычисления чисел Фибоначчи по формуле с двумя вызовами?
Пояснение. Наивная функция многократно вычисляет одни и те же значения и порождает дерево вызовов. Его размер растёт экспоненциально, поэтому сложность обычно оценивают как O(2^n).
9/10
Какое рекуррентное соотношение описывает время работы сортировки слиянием?
Пояснение. Сортировка слиянием делит массив на две половины, рекурсивно сортирует их и за линейное время выполняет слияние. Поэтому используется соотношение T(n)=2T(n/2)+n.
10/10
Какой результат вернёт рекурсивная функция НОД(48,18), если при b≠0 она возвращает НОД(b,a mod b), а при b=0 возвращает a?
Пояснение. Последовательность остатков имеет вид 48 mod 18=12, 18 mod 12=6, 12 mod 6=0. Последнее ненулевое значение равно 6, это и есть НОД.
Разобрать тему перед пересдачей: разбор темы «Рекурсия» — примеры и типичные ошибки.
Важно. Тесты носят информационно-образовательный характер и не являются публичной офертой (ст. 437 ГК РФ) или аттестацией. Возможны неточности — сверяйтесь с официальными источниками (ФИПИ, учебники). Заметили ошибку — напишите нам.