(a) Which data is the first one that occurs a collision?__ (11)__
(A) 43
(B) 5B
(C) 14
(D) 37

(b) If the hash table uses linear probing to resolve collisions and has no resizing mechanism, which position in the array is 37 inserted? __(12)__ (A)3 (B)8 (C) 4 (D)0

VII There is a linked-list with n elements, which arex1,x2,...,xn. Let f(n) be the time complexity of inserting a new element Int: to the tail of the list, and g(n) be that of deleting the last element an. If there is only one pointer pointed to the head of the list, we kuow to access the list is time-consuming, and functions f(n) and g(n) are denoted as f1(n) and g1(n) in this case. 'To improve it, we may also add another pointer pointed to the tail of it, so the functions f(n) and g(n) become f2(n) and g2(n). Which of the following option is false if n becomes large.__ (13)__ (A) (B) (C)  (D)

(a) What is the sixth edge that Kruskal's algorithm includes (the numbering of the inclusion order starts from 1, not 0)? __(14)__ (A) 6 (B) 7 (C)8 (D) 9

(b) What is the sixth vertex that Prim's algorithm includes if starting from vertex A (the numbering of the inclusion order starts from 1, not 0)?__ (15)__ (A)C(B)E (C)H (D)I 

IX What is the value of the maxinum fow for the following st-How network? __ (16)__(A) 16 (B) 17 (C) 18 (D) 19

X The Knuth-Morris-Pratt (KMP) algorithm is an string-matching algorithm. Its core is the pre- fix function. Given a pattern Pl1..m], the prefix function for the pattern P is the function π : {1,2,...,m} →{0,1.... .,m - 1}. What is π[7] for the following pattern P?__ (17)__ (A) 4 (B)5 (C)6 (D) 7

XI Many string-matching algorithms build a finite automata. Below is a partially-completed state transition function for a string s of length 10 over the alphabet f {A, B, C}. It is possible to reconstruct s from the partial table. How many A's does the string s have?__ (18)__ (A) 4 (B) 5 (C) 6 (D) 7

XII What can you infer from the facts that PROBLEMA is NP-complete and PROBLEMA linear-time reduces to PROBLEMB? __(19)__ C1: If there exists an O(N3) algorithm for PROBLEMB, then P = NP. C2: If there does not exist an O(N3) algorithm for PROBLEMB, then P ≠ NP. C3: If there exists an O(N3) algoritlim for PROBLEMB, then there exists an O(N3) algorithm for PROBLEMA. C4: If there exists an O(N3) algorithm for PROBLEMA, then there exists an O(N3) algorithm for PROBLEMB. (A) C1 and C3(B) C1 and C4(C) C2 and C3 (D) C2 and C4

XIII The VERTEX-COVER problem is to find a vertex cover of the size k in a given graph G. In the SUBSET-SUM problem, given a finite set , we ask whether there is a subset whose elements sum to t. The VERTEX-COVER problem is polynomial-time reducible to the SUBSET-SUM problem. Given an instance ＜ G,k ＞ of the VERTEX-COVER problem, one can construct a corresponding instance ＜ S,t ＞ of the SUBSET-SUM problem. Given the following graph G and k = 3, {u1, u3, u4} is the vertex cover of size k = 3. The corresponding set S = [1 4, 16, 64 256, 1040, 1041, 1093, 1284, 1344) is constructed as the following table. What is the target t?__ (20)__(A) 2389 (B) 3417 (C) 3754 (D) 3758

(c) The last number of the maximum-length snake sequence is__(4)__ (A)9(0,0)(B) 6(3,2) (C) 7(3,3)  (D) 1(2,3) (E) 7(0,2)

110年 - 110 國立臺灣大學_碩士班招生考試_部分系所:資料結構與演算法(A)#105777

109年 - 109國立臺灣大學_碩士班招生考試_資訊工程學研究所:資料結構與演算法(A)#106053