109 中央資工所軟體考點分析
申論題佔 65% 的重度手寫卷。選擇題部分僅 35%，且複選題全對才給分、倒扣 1.25 分，是歷年倒扣最重的一年。
題型與配分
科目全名「資料結構與演算法」（所別：資工類），全卷 4 頁、100 分，禁用計算器。
| 區段 | 題號 | 配分 | 倒扣 |
|---|---|---|---|
| 複選題 | 1–6 | 30%（每題 5 分） | 全對才給分，答錯倒扣 1.25 分 |
| 是非題 | 7–11 | 5%（每題 1 分） | 答錯倒扣 0.5 分 |
| 申論題 | 1–4 | 65% | — |
申論題佔了三分之二，這是近十年中央軟體手寫比重最高的一年。倒扣 1.25 分也是歷年最重。
複選題（1–6）考點
- 第 1 題｜給定一張圖，判斷哪些是從節點 1 出發的 DFS 走訪序列
- 第 2 題｜Min-Heap 陣列末端插入 9 後重建，問 9 最後落在哪個索引
- 第 3 題｜Threaded binary tree — 問節點 3 的兩條 thread 分別指向哪些節點
- 第 4 題｜判斷哪些序列是給定有向圖的 topological sorting
- 第 5 題｜由 Quick sort 第一次 partition 的結果反推 pivot（與 108 年第 1 題同型）
- 第 6 題｜Hash table 11 buckets × 每 bucket 2 slots、linear probing，算滿的 bucket 內數字總和（與 108 年第 6 題同型）
是非題（7–11）考點
- 第 7 題｜判斷一個 postfix 運算式是否合法
- 第 8 題｜有向圖的 adjacency matrix：row sum 是 in-degree 還是 out-degree
- 第 9 題｜|E| = |V| − 1 的圖是否必為 binary tree
- 第 10 題｜DFS 能否用 stack 實作
- 第 11 題｜connected component 的定義（只滿足子集合關係是否就算）
申論題（1–4）考點
- 第 1 題（10%）｜兩個 stack 共用同一個陣列
mem[]，要完成PUSH演算法。經典的雙堆疊題，關鍵在兩個 top 相向成長時的溢位判斷 - 第 2 題（5%）｜
perm排列演算法填空（兩格，與 108 年第 4、5 題同一支程式） - 第 3 題（25%）｜MST — (a) 15%：描述一個有效率的演算法，同時要分析時間複雜度、說明使用的資料結構 (b) 10%：設計演算法求 second best spanning tree（次佳生成樹，成本可能與最佳相同）
- 第 4 題（25%）｜3-SUM 與其推廣 — (a) 10%：設計比 O(n3) 更快的演算法找出三數和為 M，並分析複雜度 (b) 5%：證明 k-SUM 是 NP-Complete (c) 10%：當 M 夠小時，設計 O(nkM) 的演算法
這份考卷的難點
- 倒扣 1.25 分且全對才給分，複選題的期望值很低。30 分裡如果沒把握，硬猜會倒扣到零。
- 第 3(b) 次佳生成樹是進階題，不是標準課本內容，需要理解「換掉 MST 中一條邊」的思路。
- 第 4 題三小題層層遞進 —— 從 3-SUM 的 O(n2 ) 解法，到證明 k-SUM 為 NP-Complete，再到 M 有界時的 pseudo-polynomial DP。這是整份考卷區分度最高的一題。
- 申論題佔 65%，字要寫得快、演算法要能默寫，時間壓力很大。
準備建議
- 這一年必須會「設計演算法並分析複雜度」，不是只判斷對錯。MST（Prim／Kruskal 的資料結構與複雜度）要能完整論述
- 3-SUM 的 O(n2) 解法（排序後雙指標）、以及 subset sum 型 DP 的 pseudo-polynomial 分析，是第 4 題的核心
- 雙堆疊共用陣列、threaded binary tree 這類「課本角落」的題目也出現了，基本功要紮實