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

科目：台大◆資工◆資料結構與演算法(A) | 年份：110年 | 選擇題數：20 | 申論題數：0

試卷資訊

所屬科目：台大◆資工◆資料結構與演算法(A)

選擇題 (20)

I .When CAN the worst case of Quicksort occur? __(1)__
C1:Quick Sort where leftmost (or rigltmost) element is always chosen as pivot
C2: leftmost element is chosen as pivot and array is already sorted in SAME order
 C3: leftmost element is chosen as pivot and array is already sorted in REVERSE order (A)C1 (B)C2 (C) C1 and C2 (D) C2 and C3
(a) The maximum LENGTH of snake sequence is (A) 6 (B) 7 (C) 5 (D) 4
(b) Time complexity of above solution is__(3)__ (A) O(M X N) T(B) O(M2) (C) O(N2) (D) O(M)
(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)
(d) The third number of the maximum-length snake sequence is__(5)__ (A)7(1,1) (B) 7(0,2) (C) 3(1,2) (D) 6(2,1)  (E) 8(0,1)
III For questions with sequences, we constantly split the problem into a number of sub-problems that are smaller instances of the same problem, and we try to solve the smaller problems recursively. We called this type of algorithm __(6)__ (A) Dynamic  programming (B) Divide and   Quicksort   (C) Greedy al-  gorithms(D) conquer
(a) Which data structure is operated by those functions?__ (7)__  (A) Queue (B) Stack (C)Hash(D) Heap

(b) If functions f(x) and g() are changed as following:
61e1100ddeabf.jpg 

Which data structure is operated by those functions?__(8)__ (A) Queue (B) Stack (C) Hash (D) Heap
(a) What is its postorder traversal result? __(9)__ (A) +a*-dbc (B)a+b-c*d (C) abc-d*+(D) +a * -bcd
(b) What is its BFS traversal result? (10) (A) +a* -dbc (B)atb-c*dT(C) abc-d*+T (D) +a* -bcd
(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)61e11194914c0.jpg (B) 61e111b991b15.jpg(C) 61e111d531473.jpg (D)61e11208a47c6.jpg
(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)__
61e11306401a5.jpg(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)__61e1136a617d6.jpg (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)__
61e113b4f2d07.jpg (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 61e1146fe037f.jpg, we ask whether there is a subset 61e1148e6d76c.jpgwhose 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)__61e114f80dbab.jpg61e1151220da0.jpg(A) 2389 (B) 3417 (C) 3754 (D) 3758

申論題 (0)