107 交大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 5 頁、10 題、100 分，不可使用計算機，全部手寫。

逐題考點

• 第 1 題（5%）｜給一張 weighted graph，求 MST 的總邊權
• 第 2 題（10%）｜給一棵樹，寫出 in-order 與 post-order traversal 序列
• 第 3 題（10%）｜給一棵 red-black tree（黑用方形、紅用圓形），插入 {9} 後畫出結果。題目要求必須畫出 Insertion-Fixup 的所有步驟，不能只給最終結果
• 第 4 題（5%）｜給一支遞迴的 binary search 函式 foo，用 recurrence relation 推導時間複雜度，要寫出推導過程
• 第 5 題（10%）｜追蹤兩支函式：foo1 遞迴處理左右子樹，foo2 做 postorder traversal 並在 flag 為偶數時累加。要輸出最終的 sum
• 第 6 題（10%）｜追蹤三支函式：foo1 做一趟氣泡交換、foo2 反轉整條 linked list、bar 累加特定索引位置的值
• 第 7 題（15%）｜給出一段名為 Mystery-Algorithm 的 pseudo-code（先加一個新頂點跑 Bellman-Ford、調整邊權，再對每個頂點跑 Dijkstra）：(a) 5% 這個演算法的功能是什麼、用 Fibonacci heap 的複雜度為何 (b) 10% 為什麼第 3 步可以用 Dijkstra
• 第 8 題（10%）｜給一張 flow network（節點 0 為源點、節點 5 為匯點）：(a) 5% 用 Edmonds-Karp 求 max flow，要畫出前五次迭代的 residual network 與對應的流 (b) 5% 找出一個 min cut
• 第 9 題（10%）｜maximum subarray 和的 O(n) 解法填空，要填 (a)(b) 兩格
• 第 10 題（15%）｜已知有 O(n⁷) 時間的 HamP(G) 可判斷圖是否有 Hamiltonian path，要設計同樣 O(n⁷) 時間的 HamEx(G, x)（判斷 G 是否存在一條不以 x 為端點的 Hamiltonian path），並證明正確性。題目明訂若演算法漸進較慢，不給部分分數

作答時要注意的地方

1. 第 5、6 題合計 20 分，都是程式碼追蹤。
2. 第 7(b) 配分 10 分，是證明題。
3. 第 10 題要在指定的時間複雜度內完成，且沒有部分分數。
4. 第 3 題要畫出所有 Fixup 步驟，只寫最終樹會失分。

準備方向

• 程式碼追蹤：106 第 3 題、107 第 5、6 題、108 第 1、2、4、9 題組都有。
• 給 pseudo-code 問功能與複雜度的 shortest path 題（107 第 7 題）。
• red-black tree 插入的 Fixup 步驟（107 第 3 題）。
• maximum subarray 和（107 第 9 題）。
• Hamiltonian path、cycle 的 reduction：107 第 10 題、108 第 16 題組、109 第 3 題組。