22. Suppose you can take any arbitrary portion of cach item. What is the highest total value you can get by filling your knapsack?
(A) 184
(B) 100
(C)90
(D) 84

23. Suppose you can only choose to take or leave cach entire item. Let V[i]U] denote the highest total value you can obtain with items 1~i and a knapsack of weight capacity j. Which of the following recurrence relations is correct? (A) V[i][j] = max(V[i - 1][j]，V[i - 1][j -1] +v[i]) (B) V[i][j]=max(V[i - 1][j]，V[i - 1][j -w[i])+v[i]) (C) V[i][j] = max(V[i][j - 1]，V[i -1] [j-1] +v[i]) (D)V[i][j]= max(V[i][j-w[i]]，V[i -1][j-w[i]]+  v[1])

24. Suppose you can only choose to take or leave each entire item. What is the highest total value you can get by filling your knapsack? (A) 184 (B)90 (C) 84 (D) 80 

25. The recurrence relation in the previous problem solves the 0-1 knapsack problem in a dynamic programming manner by filling the table of V[i][j]. Which of the following statements is correct about the running time of this algorithm? (A)It is a linear-t -time algorithm. (B) It is a polynomial-time algorithm, but not a lincar-time algorithr. (C) It is an exponential-time algorithm, but not a polynomial-time algorithr. (D) Nobody knows yet whether or not it is a polynomial-time algorithm.

26. Consider the following five recursive functions: (A) (B) (C) (D) (E)Which recursion yields the highest asymptotic complexity for T(n)?

27. For an AVL tree with 2021 nodes, let x be the minimum possible height, y be the maximum height, then (y-x) mod 5 is (A)0 (B)1(C)2(D)3(E)4

28. For a 2-3-4 tree of height 5, let x be the minimum possible size, y be the maximum possible size, then (xy) mod 5 is (A) 0 (B) 1 (C) 2 (D) 3 (E)4

29. For a binary heap of height 2021, let x be the minimumn possible size, y be the maximum possible size, then (3xty) mod 5 (A) 0 (B) 1 (C)2 (D) (E) 4

30. Consider a binary heap that results from successively inserting keys 6, 3, 7, 8, 5, 1, 2, 4, 9 into an initially empty heap. Then the depth of key 5 is (A)0 (B)1 (C) 2 (D) 3(E) None of above

31. A binomial heap contains 2021 items. How many among them have depth 7? (A) 165 (B) 170 (C) 175 (D) 180 (E) 185

32. If Dijkstra algorithm is implemented with Binomial heap as priority qucue, then the complexity is (A) O(|V|2+|E| log|V|) (B) O(|V|2) (C) O(|E| log|V|) (D) O(|E|  ||+|V| log|V|)(E) O(|E|)

115年 - 115 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147260

114年 - 114 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147250

113年 - 113 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147281

112年 - 112 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147280

111年 - 111 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147272

110年 - 110 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147276

110年 - [非官方正解]110 國立臺灣大學_碩士班招生考試_電信工程研究所丙組:資料結構與演算法(B)#113108

110年 - [非官方正解]110 國立中央大學_碩士班招生考試_資工類：資料結構與演算法#105890

109年 - 109 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147273

109年 - 109 東吳大學_轉學生招生考試_資訊管理學系三年級︰資料結構#105850