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

Part I

1. Run Dijkstra algorithm on the following graph to find the shortest distance from the source vertex to all vertex. The source vertex is s. Run the algorithm step by step. (15%)

2. Give an asymptotic upper bound for the function \( T(n) \) where \( T(n) \) satisfies the recurrent equation \( T(n) = T(n/5) + T(7n/10) + n \). (5%)

3. The following table shows dimensions of six matrices.

Please fully parenthesize the product A₁A₂A₃A₄A₅A₆ in a way such that the number of scalar multiplications is minimum and compute this minimum number. (15%)

(For example, the number of scalar multiplications of (A₁(A₂(A₃(A₄(A₅A₆))))is 47500).

4. Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints: (15%)

$$x1 - x2 \le 1, x1 - x4 \le -4, x2 - x3 \le 2, x2 - x5 \le 7, x2 - x6 \le 5, x3 - x6 \le 10, x4 - x2 \le 2, x5 - x1 \le -1,$$

$$x5 - x4 \le 3, x6 - x3 \le 8.$$

(a) 請算出每個邊的最早(earliest)開始時間 e() 和最晚(latest)開始時間 l()、與鬆散(slack)時間，並寫出其臨界路徑(critical path)。

(b) 哪些活動，單獨的加速會導致專案長度的縮短？(a₁=5 a₂=6, a₃=3, a₄=4, a₅=6, a₆=6, a₇=5, a₈=3, a₉=2, a₁₀=4, a₁₁=4, a₁₂=5, a₁₃=2, a₁₄=2)

2. 請依序利用下列數值1000,1010,1110,0110,0111,0010,0100建一Patricia(Practical Algorithm To Retrieve Information Coded In Alphanumeric)trie. (12%)

3. 請將下列數字49,5,9,10 and 15 依序插入Figure 2 AVL tree並平衡之。(10%)

4. 請利用Bellman-Ford演算法一步一步算出Figure 3從node 1到各點之最短距離。(10%)
(e₁₂=6, e₁₃=5, e₁₄=5, e₂₅=-1, e₃₂=-2, e₃₅=1, e₄₃=-2, e₄₆=-1, e₅₆=2)