114 中央資工所軟體考點分析
20 題全複選、全對才給分。與隔年 115 有大量同型題，前半段偏手動模擬，後半段是五選項的觀念判斷。
題型與配分
科目全名「資料結構與演算法」（系所：資工類），全卷 7 頁、20 題複選、每題 5 分、共 100 分，禁用計算器。
全部答對才給分，答錯倒扣 1 分。
與 113、115 同樣是全複選卷，中央軟體自 113 年起已固定為這個形式。
與 115 年的高度重複
這一年和隔年 115 有一整批同型題，準備時兩年必須一起練：
| 114 年 | 115 年 | 題型 |
|---|---|---|
| 第 1 題 hash quadratic probing 反推插入順序 | 第 12 題 | 同一種考法 |
| 第 2 題 infix／postfix／prefix 互轉 | 第 16 題 | 同型 |
| 第 3 題 LSD Radix sort 各 pass | 第 14 題 | 同型 |
| 第 4 題 inorder＋postorder 重建二元樹 | 第 18 題 | 同型 |
| 第 5 題 同一段 push／pop 在四種容器的結果 | 第 17 題 | 幾乎完全相同 |
| 第 6 題 red-black tree 插入後的顏色與 level order | 第 15 題 | 同型 |
| 第 8–10 題 LeetCode 型貪婪＋heap | 第 19 題 | 同型 |
逐題考點
手動模擬（1–6）
- 第 1 題｜11 格 hash table、quadratic probing 雙向探測 (h(k)±i2)%11，給定最終表格反推哪些插入順序可能成立
- 第 2 題｜Infix、postfix、prefix 三種表示法互轉
- 第 3 題｜LSD Radix sort，判斷第一／二趟結束後特定位置的元素
- 第 4 題｜由 inorder
ILOVENCU與 postorderILVNCUEO重建二元樹，再問 level-order 的第五、第六個字母、樹高、C 是否為葉節點 - 第 5 題｜同一段 push／pop 程式碼，分別套用 standard stack、standard queue、min heap、max heap，問容器內元素的排列
- 第 6 題｜Red-black tree（初始 level order 50, 30, 80, 90），插入 70、75 或 70、60、65 之後的節點顏色與 level order
Floyd–Warshall（7）
- 第 7 題｜給出 Floyd–Warshall 的完整 pseudo-code，判斷「k 在最短路徑上」與遞迴式條件之間的充分／必要關係 —— 選項在 D(k) 與 D(k−1) 之間反覆切換，非常容易看錯
UAV 加油問題（8–10）
三題連動，題型與 LeetCode 871 Minimum Number of Refueling Stops 相同：
- 第 8 題｜補上
for迴圈條件 L1（關鍵在判斷加油站是否在目前油量可達範圍內） - 第 9 題｜容器
Q可以是 stack、priority queue、max heap 還是 min heap - 第 10 題｜區分「這個演算法的時間複雜度」與「這個問題的時間複雜度」—— 選項刻意混用兩者
觀念判斷（11–20）
這十題都是五個選項的「哪些不正確／哪些正確」，範圍極廣：
- 第 11 題｜Hashing — load factor 定義、h(k)=k mod m 當 m 有因數 d 時的影響、probe sequence 是否應為 {1,…,m} 的排列、perfect hashing 是否存在
- 第 12 題｜LCS — 暴力法的 O(n2m)、遞迴式在 x[i]≠y[j] 時的寫法、DP 是否為指數複雜度、prefix 性質
- 第 13 題｜MST — spanning tree 是否唯一、Prim 與 Kruskal 優化後複雜度是否相同、disjoint-set 是用來優化 Prim 還是 Kruskal、Fibonacci heap 用在哪一個
- 第 14 題｜Maximum Flow — Ford–Fulkerson 的 O(Ef)、max-flow min-cut（注意是最小割不是最大割）、antiparallel edges 的處理。最大流在中央軟體是少見的考點
- 第 15 題｜單源最短路徑 — 負權環的影響、subpath 最佳性、Dijkstra 用 binary heap 的複雜度、等權重圖的更快解法
- 第 16 題｜證明一個決策問題是 NP-complete 的必要步驟（歸約方向 + 非確定性多項式演算法）
- 第 17 題｜NP-hard／NP-complete 的歸約方向，五個選項只差箭頭方向
- 第 18 題｜漸進符號 — f(n)=3n4+8n−1666 的 O／Ω 上下界判斷
- 第 19 題｜動態規劃的性質 — 是否一定用二維表、memoization、與 greedy choice property 的關係
- 第 20 題｜搜尋策略 — BFS／DFS 是否為 uninformed、**A\* 在 admissible 且 consistent 下的最佳性**、hill climbing 能否跳出區域最佳、branch and bound 的上下界剪枝
這份考卷的難點
- 第 7 題的充要條件是全卷最容易錯的一題，四個選項只在 D(k)／D(k−1) 和「若…則」的方向上不同。
- 第 10 題刻意區分「演算法」與「問題」的複雜度，沒看清楚主詞就會選錯。
- 第 13 題的 disjoint-set 與 Fibonacci heap 分別優化哪個演算法是常見誤區（disjoint-set → Kruskal，Fibonacci heap → Prim）。
- 第 14 題的最大流在中央軟體很少出現，容易準備不到。
- 第 6 題的紅黑樹要連續插入並維持性質，且分成兩組不同的插入序列，計算量大。
準備建議
- 必須連 115 年一起練，兩年同型題超過三分之一
- Floyd–Warshall 的遞迴式意義要理解到能判斷充要條件，不能只會套公式
- 最大流（Ford–Fulkerson、max-flow min-cut theorem）雖然少考，但 114 出現了，建議補齊
- LeetCode 風格的貪婪＋heap 題型（加油站、課程排程）在 114、115 連續出現，值得針對性練習
- 紅黑樹的插入與重新著色要練到能手繪正確