Data Structure Questions and Answers on Fibonacci using Recursion for Freshers

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

Answer: a

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

Answer: d

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

Answer: d

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

Answer: b

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)

Answer: d

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)

Answer: b

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 a and b

Answer: d

Explanation: Both a and b 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(n2
d) O(2n)

Answer: d

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

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(n2)
d) O(2n)

Answer: a

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

Answer: d

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

Answer: c

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

Answer: d

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

Answer: b

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