Free Printable Индукция и рекурсия

1.

Индукция - это принцип...

a)

рассуждения от общего к частному

b)

рассуждения от частного к общему

c)

вычисления суммы последовательности чисел

d)

написания рекурсивных функций

2.

Чему равна сумма первых $n$ нечётных чисел?

a)

$n^2$

b)

$\frac{n^2}{2}$

c)

$n\left(n+1\right)$

d)

$\frac{n\left(n+1\right)}{2}$

3.

Из скольких значений $n$ может состоять необходимая база индукции...

a)

0

b)

1

c)

2

d)

3

e)

100

4.

Какие утверждения про числа Фибоначчи верны?

a)

$F_n\ =\ F_{n-1}\ +\ F_{n-2}$

b)

$F_n^2\ =\ F_{n-1}F_{n+1}$

c)

$F_n\ =\ F_{n+2}\ -\ F_{n+1}$

d)

$F_n\ =\ F_{n-1}\ -\ F_{n-2}$

5.

Какое наименьшее количество операций потребуется для перекладывания пирамидки из 5 колец в задаче о Ханойских башнях?

(a)

6.

Через какую структуру данных реализован рекурсивный вызов функций в C++?

a)

Множество

b)

Очередь

c)

Очередь с приоритетом

d)

Стек

7.

За сколько мы умеем считать произведение всех чисел от 1 до $n$ рекурсией? (выбрать лучшую асимптотику)

a)

$O\left(1\right)$

b)

$O\left(\log_{ }n\right)$

c)

$O\left(n\right)$

d)

$O\left(n^2\right)$

e)

$O\left(n!\right)$

8.

Что вернёт f(2)?

(a)

9.

Что должно стоять на месте пропуска?

a)

n == 1

b)

n == 2

c)

n < 2

d)

n < 3

10.

Что вернёт f(3)?

a)

0

b)

1

c)

2

d)

Произойдёт ошибка

11.

Какой рекурсивный переход у функции быстрого возведения в степень f(a, n) в случае чётного показателя степени (чётного n)?

a)

f(a/2, n) ^ 2

b)

f(a, n/2) ^ 2

c)

f(a, n-1) * a

d)

f(a, n/2) * a

12.

Почему в данном коде мы можем не ставить else во второй строчке тела функции f?

4 lines

Индукция и рекурсия

Total questions: 12

Worksheet time: 9mins

Similar Resources on Wayground