115 中央資工所軟體考點分析
全卷 20 題皆為選擇題且設有倒扣，前 10 題考觀念判斷、後 10 題要完整跑過演算法才答得出來。範圍以演算法分析與樹、圖為主。
題型與配分
科目全名為「資料結構與演算法」（系所：資工類），全卷 9 頁、共 20 題、100 分，禁用計算器。
| 題號 | 題型 | 配分 | 倒扣方式 |
|---|---|---|---|
| 1–10 | 多選題（每個選項單獨計分） | 每題 5 分 | 答錯每個選項倒扣 1 分 |
| 11–20 | 複選題（全對才給分） | 每題 5 分 | 答錯一題倒扣 1 分 |
兩區皆倒扣到該區零分為止。這是這份考卷最需要注意的地方 —— 前 10 題選項獨立計分，沒把握的選項寧可不填；後 10 題全對才給分，錯一個選項整題就沒了還倒扣。
多選題（1–10）考點
這區考的是觀念是否精確，不需要大量計算。
- 第 1 題｜Quicksort — 最壞情況、以中位數為 pivot 的影響、穩定性、randomized 版本的期望複雜度、額外空間
- 第 2 題｜Amortized analysis — aggregate／accounting／potential 三種方法的定義，以及它和 average-case analysis 的本質差異
- 第 3 題｜LCS 的 DP — 遞迴式在字元相等與不相等時的寫法、時間複雜度、滾動陣列優化、能否用 greedy
- 第 4 題｜Greedy — greedy-choice property 與 optimal substructure、fractional vs 0/1 knapsack、Dijkstra 遇負權、Prim 與 Kruskal
- 第 5 題｜計算複雜度 — NP-complete 與 NP-hard、optimization 與 decision 版本的關係、coNP、reduction 的方向、PTAS
- 第 6 題｜漸進符號 — O、Ω、Θ、o 之間的互推關係
- 第 7 題｜排序下界 — comparison-based 的 Ω(n log n)、decision-tree model、counting／radix sort 為何不受此限、information-theoretic 論證
- 第 8 題｜最短路徑 — Dijkstra 遇負權邊、Bellman–Ford 偵測負環、Floyd–Warshall 的適用性、APSP 的複雜度
- 第 9 題｜Branch-and-bound 與 A — admissible heuristic 的意義、A 是 B&B 的特例、最壞情況下的效率
- 第 10 題｜Median of medians（prune-and-search） — 分組為 5 時的 3n/10 保證、遞迴式 T(n)=T(n/5)+T(7n/10)+O(n) 推出的複雜度、改成分組為 3 會發生什麼事
複選題（11–20）考點
這區全對才給分，而且多數題目必須完整跑過一次演算法才能判斷，是整份考卷最花時間的地方。
- 第 11 題｜AOV／AOE network — topological order 是否合法、critical path 的計算（含改變單一邊權重後的變化）
- 第 12 題｜Hash table — 給定 11 格的最終狀態，反推哪些插入順序在 linear probing／quadratic probing 下成立
- 第 13 題｜MST — Kruskal 與 Prim（分別從不同起點）加邊的先後順序
- 第 14 題｜Quick Sort 第一趟 partition 的結果、LSD Radix sort 各 pass 結束後的序列
- 第 15 題｜Red-black tree — 連續插入後各節點的顏色與 level-order traversal
- 第 16 題｜中序／前序／後序運算式互轉
- 第 17 題｜同一段 push／pop 程式碼，分別放進 stack、queue、min heap、max heap 的結果差異
- 第 18 題｜由 inorder 與 postorder 重建二元樹，再問 level-order、高度、葉節點
- 第 19 題｜課程排程的 greedy 策略（與 LeetCode 630 Course Schedule III 同型）— 排序依據、min-heap 的角色、複雜度
- 第 20 題｜structurally unique binary tree 的個數 — Catalan number，以及計算它的時間與空間複雜度
這份考卷的難點
- 倒扣是最大變因。 全卷沒有申論題，分數完全由選擇題決定，亂猜是負期望值。
- 第 11–20 題吃時間。 12、13、14、15 這四題都要手動跑完整個演算法，且全對才給分。時間分配上建議先確保 1–10 的觀念分。
- 第 15 題的紅黑樹要連續插入三個節點並維持性質，是全卷最容易算錯的一題。
- 第 20 題需要記得或能現場推出 Catalan number 的值。
準備建議
- 中央軟體近年大量使用「全對才給分」的複選題，演算法的手動追蹤（trace）必須練到穩，光懂觀念不夠
- 紅黑樹、AOE critical path、hash probing 這三個主題在中央出現頻率高，且都是容易算錯的類型
- 第 19 題這種 LeetCode 風格的貪婪排程題近年變多，建議補一下經典 greedy 題型
- 禁用計算器，Catalan number、2 的次方等常用數值建議先記熟