This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Fibonacci using Recursion”.

1. Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?

a) 5

b) 6

c) 7

d) 8

View Answer

Explanation: The sixth fibonnaci number is 5.

2. Which of the following is not a fibonnaci number?

a) 8

b) 21

c) 55

d) 14

View Answer

Explanation: 14 is not a fibonnaci number.

3. Which of the following methods can be used to find the nth fibonnaci number?

a) Dynamic programming

b) Recursion

c) Iteration

d) All of the mentioned

View Answer

Explanation: All of the above mentioned methods can be used to find the nth fibonacci number.

4. Consider the following iterative implementation to find the nth fibonacci number:

int main() { int n = 10,i; if(n == 1) printf("0"); else if(n == 2) printf("1"); else { int a = 0, b = 1, c; for(i = 3; i <= n; i++) { c = a + b; ________; ________; } printf("%d",c); } return 0; }

Which of the following lines should be added to complete the above code?

a) c = b

b = a

b) a = b

b = c

c) b = c

a = b

d) a = b

b = a

View Answer

Explanation: The lines “a = b” and “b = c” should be added to complete the above code.

5. Which of the following recurrence relations can be used to find the nth fibonacci number?

a) F(n) = F(n) + F(n – 1)

b) F(n) = F(n) + F(n + 1)

c) F(n) = F(n – 1)

d) F(n) = F(n – 1) + F(n – 2)

View Answer

Explanation: The relation F(n) = F(n – 1) + F(n – 2) can be used to find the nth fibonacci number.

6. Consider the following recursive implementation to find the nth fibonacci number:

int fibo(int n) { if(n == 1) return 0; else if(n == 2) return 1; return ________; } int main() { int n = 5; int ans = fibo(n); printf("%d",ans); return 0; }

Which of the following lines should be inserted to complete the above code?

a) fibo(n – 1)

b) fibo(n – 1) + fibo(n – 2)

c) fibo(n) + fibo(n – 1)

d) fibo(n – 2) + fibo(n – 1)

View Answer

Explanation: The line fibo(n – 1) + fibo(n – 2) should be inserted to complete the above code.

7. Consider the following recursive implementation to find the nth fibonnaci number:

int fibo(int n) { if(n == 1) return 0; else if(n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { int n = 5; int ans = fibo(n); printf("%d",ans); return 0; }

Which of the following is the base case?

a) if(n == 1)

b) else if(n == 2)

c) return fibo(n – 1) + fibo(n – 2)

d) both if(n == 1) and else if(n == 2)

View Answer

Explanation: Both if(n == 1) and else if(n == 2) are the base cases.

8. What is the time complexity of the above recursive implementation to find the nth fibonacci number?

a) O(1)

b) O(2*n)

c) O(n^{2})

d) O(2^{n})

View Answer

Explanation: The time complexity of the above recursive implementation to find the nth fibonacci number is O(2

^{n}).

9. What is the space complexity of the above recursive implementation to find the nth fibonacci number?

a) O(1)

b) O(2*n)

c) O(n^{2})

d) O(2^{n})

View Answer

Explanation: The space complexity of the above recursive implementation to find the nth fibonacci number is O(1).

10. What is the output of the following code?

int fibo(int n) { if(n == 1) return 0; else if(n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { int n = -1; int ans = fibo(n); printf("%d",ans); return 0; }

a) 0

b) 1

c) Compile time error

d) Runtime error

View Answer

Explanation: Since negative numbers are not handled by the program, the function fibo() will be called infinite times and the program will produce a runtime error when the stack overflows.

11. What is the output of the following code?

int fibo(int n) { if(n == 1) return 0; else if(n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { int n = 5; int ans = fibo(n); printf("%d",ans); return 0; }

a) 1

b) 2

c) 3

d) 5

View Answer

Explanation: The program prints the 5th fibonacci number, which is 3.

12. How many times will the function fibo() be called when the following code is executed?

int fibo(int n) { if(n == 1) return 0; else if(n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { int n = 5; int ans = fibo(n); printf("%d",ans); return 0; }

a) 5

b) 6

c) 8

d) 9

View Answer

Explanation: The function fibo() will be called 9 times, when the above code is executed.

13. What is the output of the following code?

int fibo(int n) { if(n == 1) return 0; else if(n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { int n = 10; int ans = fibo(n); printf("%d",ans); return 0; }

a) 21

b) 34

c) 55

d) 13

View Answer

Explanation: The program prints the 10th fibonacci number, which is 34.

**Sanfoundry Global Education & Learning Series – Data Structure.**

To practice all areas of Data Structure, __here is complete set of 1000+ Multiple Choice Questions and Answers__.