Data Structure Questions and Answers – Fibonacci using Recursion

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

2. Which of the following is not a fibonnaci number?
a) 8
b) 21
c) 55
d) 14
View Answer

3. Which of the following option is wrong?
a) Fibonacci number can be calculated by using Dynamic programming
b) Fibonacci number can be calculated by using Recursion method
c) Fibonacci number can be calculated by using Iteration method
d) No method is defined to calculate Fibonacci number
View Answer

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

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

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

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

8. What is the time complexity of 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 fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(2*n)
c) O(n²)
d) O(2ⁿ)
View Answer

9. What is the space complexity of 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 fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(2*n)
c) O(n²)
d) O(2ⁿ)
View Answer

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

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

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

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

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]