#### Iteration and Recursion - Important Question Paper

11th Standard

Reg.No. :
•
•
•
•
•
•

Computer Science

Time : 01:00:00 Hrs
Total Marks : 50

Part A

Multiple Choice Question

9 x 1 = 9
1. A loop invariant need not be true

(a)

at the start of the loop

(b)

at the start of each iteration

(c)

at the end of each iteration

(d)

at the start of the algorithm

2. If m x a + n x b is an invariant for the assignment a, b : = a + 8, b + 7, the values of m and n are

(a)

m=8,n=7

(b)

m=7,n=-8

(c)

m=7,n=8

(d)

m =8,n=-7

3. Which of the following is not an invariant of the assignment? m, n := m2+, n3+

(a)

m mod2

(b)

n mod3

(c)

3 X m - 2 X n

(d)

2 X m - 3 X n

4. Which of the following algorithm design techniques to execute the same action repeatedly

(a)

Assignment

(b)

Iteration

(c)

Recursion

(d)

Both b and c

5. Which statements executed repeatedly as long as the loop condition is true?

(a)

Sequential

(b)

Abstraction

(c)

Iteration

(d)

Assignment

6. Which of the following is a recursive solver case

(a)

Base case

(b)

Recursive case

(c)

loop case

(d)

Both a and b

7. How many important points the loop variant is true?

(a)

1

(b)

2

(c)

3

(d)

4

8. How many base case at least must be in recursion?

(a)

1

(b)

2

(c)

4

(d)

3

9. ___________is an algorithm design technique, closely related to induction.

(a)

Iteration

(b)

Invariant

(c)

Loop invariant

(d)

Recursion

10. Part B

Answer all the Two mark Questions  in Three Lines

5 x 2 = 10
11. What is an invariant?

12. Define a loop invariant.

13. What is recursive problem solving

14. Define factorial of a natural number recursively

15. When will the loop variant be true?

16. Part C

Answer all the Three  Mark Questions in Five Lines

7 x 3 = 21
17. Write a note on loop variant?

18. How will you solve a problem using recursion?

19. Show that p - c is an invariant of the assignment. P, C : = P + 1, C + 1

20. Consider two variable m and n under the assignment m, n : = m + 3, n - 1. Is the expression m + 3n an invariant?

21. Using a loop variant how will you construct a loop?

22. Write a note on Recursion.

23. Write a note on Iteration.

24. Part D

Answer all  the Five Mark  Questions

2 x 5 = 10
25. Explain Loop invariant with a neat diagram.

26. Give an example for loop invariant.