Problem A: 动态规划选择题

1. Which of the following standard algorithms is not Dynamic Programming based?

A. Bellman–Ford Algorithm for single source shortest path

B. Floyd Warshall Algorithm for all pairs shortest paths

C. 0-1 Knapsack problem

D. Prim's Minimum Spanning Tree

2. We use dynamic programming approach when

A. We need an optimal solution

B. The solution has optimal substructure

C. The given problem can be reduced to the 3-SAT problem

D. It's faster than Greedy

3. Which of the following is NOT a characteristic of dynamic programming?

A. Memoization which involves storing the results of expensive function calls and reusing them.

B. Breaking a problem into smaller overlapping subproblems.

C. Solving problems in a sequential manner.

D. Dynamic programming can be used for problems where the solution has an optimal substructure.

4. The subset-sum problem is defined as follows. Given a set of n positive integers S = {a1，a2，a3，…，an} and positive integer W is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X with n rows and W+1 columns. X[i，j]，1 <= i <= n，0 <= j <= W is TRUE if and only if there is a subset of {a1，a2，...，ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?

A. X[ij] = X[i - 1，j] ∨ X[i，j -ai]

B. X[i，j] = X[i - 1，j] ∨ X[i - 1，j - ai]

C. X[i，j] = X[i - 1，j] ∧ X[i，j - ai]

D. X[i，j] = X[i - 1，j] ∧ X[i -1，j - ai]

5. A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m，n) where an incomplete recursive definition for the function l(i，j) to compute the length of The LCS of X[m] and Y[n] is given below:

l(i，j) = 0， if either i=0 or j=0

      = expr1， if i，j > 0 and X[i-1] = Y[j-1]

      = expr2， if i，j > 0 and X[i-1] != Y[j-1]

A. expr1 ≡ l(i-1，j) + 1

B. expr1 ≡ l(i，j-1)

C. expr2 ≡ max(l(i-1，j)，l(i，j-1))

D. expr2 ≡ max(l(i-1，j-1)，l(i，j))

6. Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.

A. 33

B. 23

C. 43

D. 34

7. What is memoization in the context of dynamic programming?

A. A technique to write memory-efficient programs.

B. A way to avoid solving subproblems by storing their solutions and reusing them.

C. A process of converting recursive algorithms into iterative ones.

D. A method of analyzing the time complexity of algorithms.

8. Consider a sequence F00 defined as : F00(0) = 1 F00(1) = 1 F00(n) = 10 ∗ F00(n – 1) + 100 F00(n – 2) for n ≥ 2 Then what shall be the set of values of the sequence F00 ?

A. (1，110，1200)

B. (1，110，600，1200)

C. (1，2，55，110，600，1200)

D. (1，55，110，600，1200)

9. What happens when a top-down approach of dynamic programming is applied to any problem?

A. It increases both the time complexity and the space complexity

B. It increases the space complexity and decreases the time complexity.

C. It increases the time complexity and decreases the space complexity

D. It decreases both the time complexity and the space complexity

10. The Fibonacci sequence is often used to illustrate dynamic programming concepts. What is the time complexity of a naive recursive implementation of Fibonacci numbers?

A. O(1)

B. O(log n)

C. O(n)

D. O(2^n)

11. In dynamic programming the time complexity of solving a problem with overlapping subproblems using memoization is:

A. O(1)

B. O(log n)

C. O(n)

D. O(n^2)

12. What are the different techniques to solve dynamic programming problems:

A. Memoization

B. Bottom-Up

C. Both

D. None

13. Dynamic programming is particularly useful for solving problems that have exponential time complexity.

A. True

B. False

14. The time complexity of solving the 0-1 Knapsack Problem using dynamic programming with a bottom-up approach (tabulation) is:

A. O(n)

B. O(n log n)

C. O(n * capacity)

D. O(n * capacity^2)

15. In the 0-1 Knapsack Problem if an item's weight is greater than the remaining capacity of the knapsack what action is typically taken?

A. Ignore the item and move to the next one

B. Remove the least valuable item from the knapsack to make space

C. Add the fractional part of the item that can fit into the knapsack

D. Remove the most valuable item from the knapsack to make space

16. The "Longest Increasing Subsequence" problem involves finding the length of the longest subsequence of an array in which the elements are in increasing order. What is the time complexity of the dynamic programming approach for solving the LIS problem for an array of length n?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(2^n)