NEW
Font size
S
M
L
XL
WorksheetsCTECH-02.02.2024-FN
Total questions: 15
Worksheet time: 30mins
Name
Class
Date
1.
What is dynamic programming in data structures?
a)
A technique for designing efficient algorithms by breacking down a problem into smaller subproblems
b)
A way to store and organize data in a computer program
c)
A process of optimizing memory usage in a program
d)
Amethod for creating algorithms that use only constant space
2.
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)
3.
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
4.
If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________
a)
Dynamic programming
b)
Greedy
c)
.
Divide and conquer
d)
Recursion
5.
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)
Recursion, Dynamic Programming, For loops
6.
What is the space complexity of the recursive implementation used to find the nth fibonacci term?
a)
O(1)
b)
O(n)
c)
O(n2)
d)
O(n3)
7.
Which of the following is/are property/properties of a dynamic programming problem?
a)
Optimal substructure
b)
Overlapping subproblems
c)
Greedy approach
d)
Both optimal substructure and overlapping subproblems
8.
Which of the following is not a characteristic of dynamic programming?
a)
Overlapping subproblems
b)
Optimal substructure
c)
Recursion
d)
Divide and Conquer
9.
In dynamic programming, the technique of storing the previously calculated values is called ___________
a)
Saving value property
b)
Storing value property
c)
Memoization
d)
Mapping
10.
Which of the following problems should be solved using dynamic programming?
a)
Mergesort
b)
Binary search
c)
Longest common subsequence
d)
Quicksort
11.
#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
12.
When a top-down approach of dynamic programming is applied to a problem, it usually _____________
a)
Decreases both, the time complexity and the space complexity
b)
Decreases the time complexity and increases the space complexity
c)
Increases the time complexity and decreases the space complexity
d)
Increases both, the time complexity and the space complexity
13.
Which of the following problems is NOT solved using dynamic programming?
a)
0/1 knapsack problem
b)
Matrix chain multiplication problem
c)
Edit distance problem
d)
Fractional knapsack problem
14.
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
15.
If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.
a)
Overlapping subproblems
b)
Optimal substructure
c)
Memoization
d)
Greedy
Reset
