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. | matrix | A₁ | A₂ | A₃ | A₄ | A₅ | A₆ | | --- | --- | --- | --- | --- | --- | --- | | dimension | 30×35 | 35×15 | 15×5 | 5×10 | 10×20 | 20×25 | 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.$$

Part II 1. 請針對Figure 1所示的 AOE(Activity On Edge)網路，其中有向邊(directed edge)代表工作或活動且邊上的數值代表工作或活動所需時間。(18%) (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)

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

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

110年 - [非官方正解]110 國立中央大學_碩士班招生考試_資工類：資料結構與演算法#105890

109年 - 109 東吳大學_轉學生招生考試_資訊管理學系三年級︰資料結構#105850

104年 - [非官方正解]104 國立交通大學_碩士班考試入學試題_資訊聯招：資料結構與演算法#113199