Data Structure Questions and Answers-Fibonacci using Dynamic Programming

DOWNLOAD FREE PDF <<CLICK HERE>>

Data Structure Questions and Answers-Fibonacci using Dynamic Programming

Congratulations - you have completed Data Structure Questions and Answers-Fibonacci using Dynamic Programming.

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%


Your answers are highlighted below.
Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
The following sequence is a fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, .....

Which technique can be used to get the nth fibonacci term?

A
Recursion
B
Dynamic programming
C
A single for loop
D
All of the mentioned
Question 1 Explanation: 
Each of the above mentioned methods can be used to find the nth fibonacci term.

Question 2 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Consider the recursive implementation to find the nth fibonacci number:

int fibo(int n) if n <= 1 	return n return .....

Which line would make the implementation complete?

A
fibo(n) + fibo(n)
B
fibo(n) + fibo(n - 1)
C
fibo(n - 1) + fibo(n + 1)
D
fibo(n - 1) + fibo(n - 2)
Question 2 Explanation: 
Consider the first five terms of the fibonacci sequence: 0, 1, 1, 2, 3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore, the nth term of a fibonacci sequence would be given by:

fibo(n) = fibo(n-1) + fibo(n-2).

Question 3 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
What is the time complexity of the recursive implementation used to find the nth fibonacci term?
A
O(1)
B
O(n2)
C
O(n!)
D
Exponential
Question 3 Explanation: 
The recurrence relation is given by fibo(n) = fibo(n - 1) + fibo(n - 2). So, the time complexity is given by:

T(n) = T(n - 1) + T(n - 2)

Approximately,

T(n) = 2 * T(n - 1)

= 4 * T(n - 2)

= 8 * T(n - 3)

:

:

:

= 2k * T(n - k)

This recurrence will stop when n - k = 0

i.e. n = k

Therefore, T(n) = 2n * O(0) = 2n

Hence, it takes exponential time.

It can also be proved by drawing the recursion tree and counting the number of leaves.

Question 4 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:

fibonacci(8) fibonacci(7) + fibonacci(6) fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4) fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) + fibonacci(3)	+ fibonacci(3) + fibonacci(2) : : :

Which property is shown by the above function calls?

A
Memoization
B
Optimal substructure
C
Overlapping subproblems
D
Greedy
Question 4 Explanation: 
From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.

Question 5 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
What is the output of the following program?

#include<stdio.h> int fibo(int n) { if(n<=1) 	 return n; return fibo(n-1) + fibo(n-2); } int main() { int r = fibo(50000); printf("%d", r); return 0; }
A
1253556389
B
5635632456
C
Garbage value
D
Runtime error
Question 5 Explanation: 
The value of n is 50000. The function is recursive and it's time complexity is exponential. So, the function will be called almost 250000 times. Now, even though NO variables are stored by the function, the space required to store the addresses of these function calls will be enormous. Stack memory is utilized to store these addresses and only a particular amount of stack memory can be used by any program. So, after a certain function call, no more stack space will be available and it will lead to stack overflow causing runtime error.

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results
There are 5 questions to complete.