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