107 中央資工所軟體考點分析
全卷 22 題全為選擇題且三區皆倒扣，其中 8 題是 pseudo-code 填空。重心落在遞迴式求解、圖論演算法與 NP 理論。
題型與配分
科目全名「資料結構與演算法」（所別：資工類），全卷 8 頁、22 題、100 分，禁用計算器，答案卡作答。
| 題號 | 題型 | 配分 | 倒扣 |
|---|---|---|---|
| 1–10 | 單選題 | 每題 4 分 | 答錯倒扣 1 分 |
| 11–14 | 單選題 | 每題 5 分 | 答錯倒扣 1 分 |
| 15–22 | 多選題 | 每題 5 分 | 答錯每小題倒扣 1 分，扣到零分為止 |
全卷都有倒扣，多選題更是逐選項倒扣。和 106 年全問答的形式完全相反。
逐題考點
演算法分析（1–2）
- 第 1 題｜給定一個三分遞迴的排序演算法 E-SORT（遞迴排序前 2/3、後 2/3、再前 2/3），求時間複雜度。要會解 T(n) = 3T(2n/3) + O(1) 這類遞迴式
- 第 2 題｜承上，問該演算法的 auxiliary space（遞迴深度）
圖論（3–5）
- 第 3 題｜MST 的兩個性質判斷：最輕邊唯一時是否必在所有 MST 中、cycle 中最輕邊是否必在所有 MST 中。注意題目特別聲明「不要假設邊權重相異」
- 第 4、5 題｜Floyd–Warshall，給定 5 個頂點的有向圖（含負權邊），要實際算出 d(4)[2,3] 與 d(5)[1,4]。要理解上標 k 的意義是「只用編號 ≤ k 的中繼點」
動態規劃與遞迴（6–7）
- 第 6 題｜兩條長度 11 的字串求 LCS 長度，要手動填 DP 表
- 第 7 題｜河內塔變形 —— 初始盤子可任意分布在三根柱子上（只要各柱由大到小），求移到指定柱的最少步數
程式填空（8–13）
- 第 8–10 題｜Max heap 的
adjust與heapsort，三個空格：下濾時的搬移、迴圈結束後的收尾、建堆迴圈的起始索引 - 第 11–13 題｜Quick sort 的 partition，三個空格：交換條件、do-while 的結束條件、最後 pivot 歸位的交換對象
雜湊（14）
- 第 14 題｜Hash function 的性質判斷 —— 除法雜湊取 2r 為除數的問題、doubling 重建的代價、dynamic hash、chaining 時的比較對象
NP 理論（16–17、19）
- 第 16、17 題｜NP／NP-hard／NP-complete 的定義與歸約方向。這兩題選項高度相似，差別只在歸約箭頭朝哪邊，要非常小心
- 第 19 題｜Subset Sum 的 DP — 時間複雜度 O(n·c)、pseudo-polynomial 的意義、subset sum 是否為 NP-complete
演算法改寫（15、18、20–22）
- 第 15 題｜Maximum Contiguous Subsequence Sum 的 DP，要選出哪些改動「合起來」能讓它允許空子序列（和為 0）
- 第 18 題｜把 Bellman–Ford 改成負環偵測演算法，要選出哪幾項改動合起來才正確
- 第 20、21 題｜Floyd–Warshall（題中稱 AllPairCost）的兩個空格
- 第 22 題｜AllPairCost 的適用性 —— 有環的圖、無向圖、重邊
這份考卷的難點
- 倒扣很重。 22 題全部倒扣，多選題還是逐選項扣。沒把握就不要填。
- 第 15、18 題是「選出一組改動」，不是單純判斷對錯 —— 要模擬這些改動同時套用後演算法是否正確，比一般多選難得多。
- 第 4、5 題要手算 Floyd–Warshall，圖有負權邊，容易算錯。
- 第 16、17 題的選項只差歸約方向，是整份考卷最容易失分的地方。
準備建議
- Heap、Quick sort、Floyd–Warshall 這三個演算法要熟到能看著殘缺的程式碼補出正確的那一行 —— 光知道演算法概念不足以應付填空題
- NP-hard / NP-complete 的歸約方向建議自己整理成一張圖，考場上才不會被相似選項繞暈
- 遞迴式求解（Master theorem 與非標準形式）要練