111 中央資工所軟體考點分析
與 110 年高度重複的一份考卷，複選題有八題以上是前一年的同型題改數字。問答題則三題全是演算法設計。
題型與配分
科目全名「資料結構與演算法」（所別：資工類），全卷 6 頁、100 分。
| 區段 | 題號 | 配分 | 計分方式 |
|---|---|---|---|
| 一、複選題 | 1–10 | 50%（每題 5 分） | 全對才給分，答錯倒扣 1 分 |
| 二、多選題 | 11–12 | 10%（每題 5 分） | 每個選項答對得 1 分，答錯倒扣 1 分 |
| 三、問答題 | 1–3 | 40% | 題目要求用深色筆書寫，勿用鉛筆 |
注意第一區與第二區的計分方式不同：複選題是全有全無，多選題是逐選項計分。
與 110 年的高度重複
這是準備中央軟體時最值得知道的一件事 —— 111 年的複選題有八題以上與 110 年是同型題，只改了數字或把概念換成對應版本：
| 111 年 | 110 年 | 差異 |
|---|---|---|
| 第 1 題 Infix/postfix | 第 1 題 | 選項幾乎完全相同 |
| 第 3 題 AVL tree | 第 2 題 | Fibonacci 不等式方向相反 |
| 第 4 題 HBLT（高度偏向） | 第 3 題 WBLT（重量偏向） | 換成另一種 leftist tree |
| 第 5 題 遞迴 F1/F2/F3 | 第 4 題 | F1 由 3x+1 改成 3x+2 |
| 第 6 題 二維陣列指標 | 第 5 題 | 問 arr[2][3]，前一年問 arr[3][2] |
| 第 7 題 stack/queue 判斷 | 第 6 題 | 改成「black box 傳訊息」的包裝 |
| 第 8 題 hash 刪除後搬移 | 第 7 題 | 集合中 30 改成 13 |
| 第 9 題 linked list reverse | 第 9 題 | 多挖一個空格 |
| 第 10 題 AOE network | 第 10 題 | dur 值微調 |
練過 110 年，這一年的複選題幾乎是送分。 反過來說，只練其中一年會錯過另一年的變化點。
複選題（1–10）考點
- 第 1 題｜Infix ↔ postfix 轉換與 stack 內 token 數上限
- 第 2 題｜演算法範式觀念 — DP 避免遞迴爆炸、重疊子問題導致指數複雜度、greedy 的局部最佳、divide-and-conquer 的遞迴屬於哪一部分
- 第 3 題｜AVL tree 的重平衡複雜度與高度下界
- 第 4 題｜Height-biased leftist tree (HBLT) 的性質與 meld 複雜度
- 第 5 題｜三個遞迴函式的終止性與求值
- 第 6 題｜二維陣列的指標算術
- 第 7 題｜黑盒子收送訊息的順序，判斷它是 stack、queue 還是 max heap
- 第 8 題｜Hash table 線性探測，刪除元素後哪些 key 要搬移
- 第 9 題｜Linked list
reverse的三個空格 - 第 10 題｜AOE network 的 critical path、count 欄位、latest time
多選題（11–12）考點
- 第 11 題｜各排序演算法的 worst／average／best case 時間複雜度與空間複雜度 —— insertion、merge、quick、heap、bubble 五種都要記準
- 第 12 題｜NP 理論 — NPC 的下界、NP-hard 的歸約方向、「NP-hard 且屬於 NP 即為 NPC」
問答題（1–3）考點
- 第 1 題（15%）｜題目給出 Prim's MST 的完整 pseudo-code，要求 (1) 依完全相同的格式寫出 Kruskal（9%）(2) 分析 Kruskal 的最壞情況複雜度（6%）。題目明寫「必須嚴格遵循 Prim 的格式，否則扣分」
- 第 2 題（13%）｜健行投宿問題（CLRS 經典習題）— 沿路有 n 家旅館在 a1 < a2 < … < an 公里處，一天走 x 公里的懲罰是 (20−x)2，求總懲罰最小的投宿序列。題目要求寫出遞迴式、符號意義、初始值、時間複雜度四項
- 第 3 題（12%）｜給定 m 個
xᵢ = xⱼ與xᵢ ≠ xⱼ的約束，判斷是否可同時滿足。要說明使用的資料結構並分析複雜度 —— 這是 union-find（disjoint set）的標準應用
這份考卷的難點
- 兩區選擇題的計分方式不同，第一區全對才給分、第二區逐選項計分，作答策略要跟著改。
- 第 1 題要求「嚴格遵循格式」，寫對 Kruskal 但格式散亂一樣會失分。
- 第 3 題要看出是 union-find —— 先處理所有等式建立等價類，再檢查不等式。看不出來就完全寫不動。
準備建議
- 一定要連 110 年一起練，兩年的複選題幾乎是同一套題庫
- Prim 與 Kruskal 都要能寫出完整 pseudo-code，而不只是描述流程
- union-find 是中央問答題會直接考的資料結構，路徑壓縮與按秩合併的複雜度要能說明
- 排序演算法的複雜度表（含空間）建議背熟，第 11 題是純記憶分