所屬科目：台大◆資工◆資料結構與演算法(A)
(b) If functions f(x) and g() are changed as following:
Which data structure is operated by those functions?__(8)__ (A) Queue (B) Stack (C) Hash (D) Heap
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)
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
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
阿摩線上測驗
登入
阿摩線上測驗
登入
(B) 
(C) 
(D)
(A) 16 (B) 17 (C) 18 (D) 19
(A) 4 (B)5 (C)6 (D) 7
(A) 4 (B) 5 (C) 6 (D) 7
, 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