107 交大資工所軟體考點分析
全卷 10 題手寫，兩題（第 5、6 題）合計 20 分是純程式碼追蹤，另有 Johnson 演算法與 Hamiltonian path 歸約各佔 15 分。
題型與配分
科目「資料結構與演算法（1101）」，系所班別資訊聯招，考試日期 107 年 2 月 2 日第 1 節，全卷 5 頁、10 題、100 分，不可使用計算機。全部手寫。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | MST 總權重 | 5 |
| 2 | 中序與後序走訪 | 10 |
| 3 | 紅黑樹插入（含所有 Fixup 步驟） | 10 |
| 4 | 二分搜尋的遞迴式推導 | 5 |
| 5 | 二元樹程式追蹤 | 10 |
| 6 | Linked list 程式追蹤 | 10 |
| 7 | Johnson 演算法 | 15 |
| 8 | Edmonds-Karp 與最小割 | 10 |
| 9 | 最大子陣列填空 | 10 |
| 10 | Hamiltonian path 歸約 | 15 |
逐題考點
- 第 1 題（5%）｜給一張帶權圖，求 MST 的總邊權
- 第 2 題（10%）｜給一棵樹，寫出 in-order 與 post-order 走訪序列
- 第 3 題（10%）｜給一棵紅黑樹（黑用方形、紅用圓形），插入
{9}後畫出結果。題目特別要求「必須畫出 Insertion-Fixup 的所有步驟」，不能只給最終結果 - 第 4 題（5%）｜給一支遞迴的二分搜尋函式
foo，用遞迴關係式推導時間複雜度，要一步一步寫出推導過程 - 第 5 題（10%）｜追蹤兩支函式：
foo1遞迴左右子樹互換（鏡射整棵樹），foo2做後序走訪並在flag為偶數時累加。要輸出最終的sum。難點在flag++寫在 if 外面且遞迴呼叫會改變它 - 第 6 題（10%）｜追蹤三支函式：
foo1做一趟氣泡交換、foo2反轉整條 linked list、bar累加奇數索引位置的值。注意flag&1==1因為 C++ 運算子優先序的關係實際上是flag & (1==1)也就是flag & 1 - 第 7 題（15%）｜給出 Johnson 演算法的完整 pseudo-code（加超級源點 s、跑 Bellman-Ford 求 h(v)、重新配權 w'(u,v) = w(u,v)+h(u)−h(v)、再對每個點跑 Dijkstra）：
- (a) 5%｜這個演算法的功能是什麼、用 Fibonacci heap 的複雜度為何（答案：全點對最短路徑、O(V2log V + VE)）
- (b) 10%｜為什麼第 3 步可以用 Dijkstra？ 要證明重新配權後所有邊權非負，且最短路徑不變
- 第 8 題（10%）｜給一張流網路（節點 0 為源點、節點 5 為匯點）：(a) 5% 用 Edmonds-Karp 求最大流，要畫出前五次迭代的殘餘網路與對應的流 (b) 5% 找出一個最小割
- 第 9 題（10%）｜最大子陣列和的 O(n) 解法填空。程式先把 A 改成前綴和，再用一個變數
k追蹤目前見過的最小前綴和，要填 (a)(b) 兩格 - 第 10 題（15%）｜已知有 O(nc) 時間的
HamP(G)可判斷圖是否有 Hamiltonian path，要設計 O(nc+2) 時間的HamEx(G, x)（判斷 G 是否存在一條不以 x 為端點的 Hamiltonian path），並證明正確性。題目明訂「若演算法漸進較慢，不給部分分數」
這份考卷的難點
- 第 5、6 題合計 20 分全是程式碼追蹤，而且都埋了陷阱：第 5 題的
flag++位置、第 6 題的flag&1==1運算子優先序。這兩題考的是 C/C++ 語意而非演算法。 - 第 7(b) 是全卷最需要真正理解的地方。 要能證明 w'(u,v) = w(u,v)+h(u)−h(v) ≥ 0（三角不等式）以及路徑總權重的伸縮和只差 h(u)−h(v)。
- 第 10 題的歸約要控制在指定的複雜度內，且沒有部分分數。標準做法是加一個新節點連到所有非 x 的節點再呼叫 HamP。
- 第 3 題要畫出所有 Fixup 步驟，只寫最終樹會失分。
準備建議
- 程式碼追蹤是交大的招牌（106 第 3 題、107 第 5、6 題、108 第 1、2、4、9 題都是），要練到能穩定模擬指標操作與運算子優先序
- Johnson 演算法建議完整讀懂（不只是記得名字），交大 107 直接考它的正確性證明
- 紅黑樹插入的 Fixup 三種情況（叔叔紅／叔叔黑且為三角形／叔叔黑且為直線）要能逐步畫出來
- Kadane's algorithm（最大子陣列和）的兩種寫法（DP 版與前綴和版）都要會，107 考的是前綴和版