**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%%

Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

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

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

Recursion | |

Dynamic programming | |

A single for loop | |

All of the mentioned |

Question 2 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

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

Which line would make the implementation complete?

fibo(n) + fibo(n) | |

fibo(n) + fibo(n - 1) | |

fibo(n - 1) + fibo(n + 1) | |

fibo(n - 1) + fibo(n - 2) |

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

Question 3 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

O(1) | |

O(n ^{2}) | |

O(n!) | |

Exponential |

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

Approximately,

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

= 4 * T(n - 2)

= 8 * T(n - 3)

:

:

:

= 2^{k} * T(n - k)

This recurrence will stop when n - k = 0

i.e. n = k

Therefore, T(n) = 2^{n} * O(0) = 2^{n}

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] |

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?

Memoization | |

Optimal substructure | |

Overlapping subproblems | |

Greedy |

Question 5 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

#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; }

1253556389 | |

5635632456 | |

Garbage value | |

Runtime error |

^{50000}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.