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

1..(A)O(B)X

8.Given a weighted directed graph G = (V,E, w) with no negative-weight edges, we can solve its single source shortest path problem in O(V + E) time.(A)O(B)X

9. Given a weighted directed graph G = (V,E,w), we can determine whether a negative-weight cycle exists in G in O(V + E) time.(A)O(B)X

10. Every problem in NP can be solved in exponential time. Please choose the best possible answer in each of the following qucstions. In questions that ask for time complexities, please choose the tightest bound.(A)O(B)X

11.Which of the following is correct? (A) (B) (C)(D)

12. Let f(n) and g(n) be two asymptotically non-negative functions. Which of the following is always true? (A)(B)(C) (D)

13. Consider a divide-and-conquer algorithm, which solves a problem of size n by dividing it into two subproblems of size n/3 and n/5, respectively. The solutions of the subproblems are then combined in θ(n²) time. Which of the following is correct about the time complexity T(n) of this algorithm? (A) T(n) must be in θ(n²). (B) T(n) must be in O(n²) but not nec ssarily in Ω(n²). (C) T(n) must be in Ω(n²) but not necessarily in O(n²). (D)None of the above. The complexity of T(n) depends on the exact valuc of n.

14. Consider an array of size n with perfectly inversely sorted order. Which of the following is correct about the running times to sort this array (deterministically)? (A) Quicksort: O(n ign)； Merge Sort: O(n ign)； Insertion Sort: O(n²) (B) Quicksort: 0(n²)； Merge Sort: O(n²)； Insertion Sort: 0(n²) (C) Quicksort: O(n²)； Merge Sort: O(n lgn)； Insertion Sort: O(n lgn) (D) Quicksort: 0(n²)； Merge Sort: O(n lgn)； Insertion Sort: O(n²)

複選題

15. Consider the problem of making change for n cents using the fewest number of coins. An algorithm to solve this problem is to give the coin with the highest available denomination without going over, and repeat the process until the amount of remaining change drops to O. Which of the following sets of available coin denominations would cause this algorithm to fail at yielding an optimal solution? (A) {1,3} (B) {1,3,4,5} (C) {1,5,10, 25} (D) {c⁰,c¹,..,..c^k) for any set of integers c > 1 and k ≥1

16. Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph? (A) Depth First Search (DFS) (B)Breadth First Search (BFS) (C) Prim's Minimun Spanning Tree (MST) Algorithm (D) Kruskal's Minimum Spanning Tree (MST) Algorithm

17. Consider the following undirected connected graph. What is the total weight of its maximum spanning tree?
(A)23(B)24(C)25(D)26

18. Suppose we run Dijkstra's single-source shortest-path algorithm on the following weighted directed graph with vertex a as the source. In what order do the nodes get included into the set of verticcs for which the shortest path distances are finalized?
(A) a, b, c, d, e,f (B) a, b, c,f, d,e (C) a, b, c, f,e, d (D) a, b, e, c, f, d

19. Let G be a graph represented using adjacency matrix with n vertices and m cdges. What is the tightest upper bound on the running time of depth-first search (DFS) on this graph? (A) 0(n) (B) 0(m+n) (C) 0(n²) (D) 0(mn)

20. Assume P ≠NP. Which of the following is true? (A)(B)NP-complete = NP (C) NP-hard -NP (D) P=NP-complete

21. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which of the following statements is true? (A)R is NP-complete. (B) Ris NP-hard. (C) Ois NP-complete. (D) Q is NP-hard.

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|²+|E| log|V|) (B) O(|V|²) (C) O(|E| log|V|) (D) O(|E| ||+|V| log|V|)(E) O(|E|)

33. If Dijkstra algorithm is implemented with Fibonacci heap as priority queue, then the complexity is (A) O(|V|²+|E| log |V|) (B) O(|V|²) (C) O(|E| log|V|) (D) O(|E|+I|V| log(|V|) (E) O(|E|)

34. If Dijkstra algorithn is implemented with binary heap as priority queue, then the complexity is (A) O(|V|²+[IEl log|V|) (B) O(|V|²) (C) O(|E|log|V|) (D)O(|E|+|V|logIV|) (E) O(|E|)

35. If Dijkstra algorithm is implemented with doubly-linked Iist as prionity qucue, then the complexity is (A) O(|V|²+1Ellog|V|) (B) O(|V|²) (C) O(|E|log|V|) (D) O(|E|+|V| log|V|) (E) O(|E|)

複選題

36. Which of the following statements are true? (A) [logn]! = 0(n²) (B) (logn)ⁿ = 0(n!) (C) log(n!) = O(nlogn) (D) log* n = O(log *logn) (E)

複選題
37. Which of the following statements are true? (A) Stack implements a FIFO (first-in-first-out) policy. (B) Queue implements a LIFO (last-in-first-out) policy. (C) Stack can be realized by deque (double-ended qucue). (D) The Find() operation in a doubly linked list takes O(n) time. (E) The EnqueueO operation in a queue takes O(1) time.

複選題
38. Consider a binary scarch tree that results from successively inserting keys 2, 8, 9, 1, 5. 7, 6, 3, 4 into an initially empty tree. Which of the following statements are true? (A) The tree height is 4. (B) Key 8 is prior to key 3 in terms of pre-order traversal. (C) Key 2 is prior to key 7 in terns of post-order traversal. (D) Key 4 is prior to key 5 in terms of in-order traversal. (E) Key 3 and key 9 are siblings.

複選題
39. Which of the following are balanced search trees? (A) Binary search tree (B) Red-black trec (C) AVL tree (D) 2-3-4 tree (E) Splay tree

複選題

40. Which of the following statem ents are true? (A) An insertion in AVL tree requires Ω(logn) single- and double-rotations in the worst case. (B) An insertion in AVL trce requires O(1) single- and double-rotations in the worst case. (C) A deletion in AVL tree requires Ω(logn) single- and double-rotations in the worst case. (D) Adeletion in AVL tree requires O(1) singie- and double-rotations in the worst case. (E) There is no red left child in AA tree.

複選題
41. Consider an AVL tree that results from successively inserting keys 2, 4, 5, 3, 8, 7, 1, 6, 9 into an initially empty tree. Which of the following statements are true? (A) The tree height is 4. (B) Key 3 and key 5 have the same depth. (C) Key 2 and key 8 have the same height. (D) Key 6 is a leaf. (E) Key 7 is the parent ofkey 9.

複選題
42. Consider the splay tree in Figure 1. Which of the following statements are true? (Assume bottom-up splay, also assume the Join0 operation splays on the maximum element in the left tree, which then attaches the right tree.) (A) In Figure I, after deleting key 26, then key 33 is a child of key 48. (B) In Figure I , after deleting key 26, then key 17 is the root. (C) In Figure I, after inserting key 75, then key 64 is an ancestor of key 99. (D) In Figure I, after inserting key 75, then key 33 is a descendant of key 55. (E) In Figure I, after inserting key 75, then key 75 is the root.

複選題
43. Consider the red-black tree in Figure 2, which of the following statements are true? (Assume bottom-up insertion/deletion) (A) In Figure 2, after inserting key 14, then there are 6 red nodes. (B) In Figure 2, after inserting key 54, then key 49 and key 54 are siblings. (C) In Figure 2, after deleting key 22, then key 25 and key 73 are siblings. (D) In Figure 2, after deleting key 66, then key 35 is red. (E) In Figure 2, after deleting key 83, then key 89 is red.

複選題
44.Consider an AA tree that results from suc ccessively inserting keys 96, 49, 79, 14, 41, 87, 75, 90, 61 into an initially empty tree. Which of the following statements are true? (A) The root is key 61. (B) There is less than 3 horizontal links. (C) Key 41 and key 49 are in the same level. (D) Key 87 and key 96 are siblings. (E) Key 14 is the parent of key 4 1.

複選題
45. Consider a min-heap. Which of the following statements are true? (A) For any subtrec of a min-heap, the root of the subtree contains the smallest key occurring anywhere in that subtree. (B) An array that is in ascending order is a binary min-heap. (C) The scqucnce [1.5.6,7.14,17.10.23 13.12] is a binary min-heap. (D) The largest key must reside in a leaf. (E) The smallest key must reside in a leaf

複選題
46. Consider a Fibonacci heap that results from successively inseting 929 (distinct) keys into an initially empty heap. followed by deleting the minin imum key. Which of the following statements are true? (A) The Fibonacci heap is of degree 9. (B) The Fibonacci heap is of height 12. (C) There are 5 trees in the Fibonacci heap. (D) With one additional decrease key operation, the Fibonacci heap can have 6 trees. (E) With two additiunal dourcase key uperations, the Fibonacct heap can have 7 trees.

複選題

47. Which of the following are desirable properties of a hash function h(x)?(A) If x₁,...,x_n are the items to be hashed. then the numbers h(x₁),..., h(x_n) should be uniformly distributed over the (B) The range of h(x) should incinde a wide r range of integers. (C) The range of h(x) should stay within the desired hash-table sizc. (D) It should be computable in O( 1) time. (E) It should take distinct values over all possible items to be hashed. integers.

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

試卷資訊

選擇題 (47)

申論題 (0)