108 台大資工所軟體考點分析
全卷 10 題無選擇題，且明訂「子題答錯不給部分分數」。第 9、10 兩題把匹配與 DP 包裝成船隻停靠和圖形替換，是台大少見的情境題。
題型與配分
科目「資料結構與演算法（A）」（題號 413、節次 1），全卷 4 頁、10 題、100 分。沒有選擇題，全部寫在答案卷上。
計分規定：卷面第一行就寫明「NO partial score will be given for partially correct answer」—— 每一個子題答對才給分，答錯一部分就整個子題沒分。另外註明「除非特別說明，只需要最終答案」。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | Stack 排列數（遞迴式＋封閉式） | 10 |
| 2 | Infix 轉 postfix | 5 |
| 3 | Min-heap 操作後畫圖 | 10 |
| 4 | O(n) 建堆的說明 | 8 |
| 5 | Quicksort 三路分割（3 小題） | 20 |
| 6 | Hash open addressing（3 小題） | 13 |
| 7 | 最短路徑是非題 | 6 |
| 8 | 去環 pseudo-code 填空 | 8 |
| 9 | 船隻停靠（非交叉匹配） | 10 |
| 10 | 圖形替換 DP | 10 |
逐題考點
- 第 1 題（10%）｜1..n 經過 stack 後可以產生幾種排列 bn。(a) 遞迴式 (b) 封閉式 —— 答案是 Catalan number，(a) 要寫出 bn = Σ bk·bn−1−k 的卷積形式
- 第 2 題（5%）｜把
(a/(c*(b+d)))/(e-a)*c轉成 postfix。純技術題，穩分 - 第 3 題（10%）｜依序 insert 7、4、3、1、delete min、insert 9、2、5、delete min、delete min，畫出最終的 min-heap
- 第 4 題（8%）｜說明如何在 O(n) 時間建堆，可用 n = 15 舉例（不必證明複雜度）。考的是 bottom-up heapify 而非逐一插入
- 第 5 題（20%）｜Quicksort 深入題，是全卷配分最高的一題
- (a) 6%｜三個是非：輸出是否非遞增、是否為 stable sort、是否為 in-place sort
- (b) 4%｜當 n 個元素全部相同時的最壞複雜度
- (c) 10%｜補完
PARTITION_THREE()的 (A)(B)(C) 三個空格，讓三路分割版本在全等輸入下跑出 O(n) - 第 6 題（13%）｜Open addressing
- (a) 3%｜寫出 linear probing 的 h(k,i)
- (b) 5%｜double hashing，h1(k)=k mod 16、h2(k)=1+(k mod 15)、m=16，依序插入 {16, 3, 35, 67, 51, 1, 15, 31, 19, 17}，畫出最終表格
- (c) 5%｜Alpha 教授改用 h2(k)=2·(k mod 8)，舉例說明這個設計為何有問題 —— 關鍵在 h2(k) 與 m=16 不互質，探測序列走不完整張表
- 第 7 題（6%）｜三個是非：Dijkstra 能否處理負權（無負環）、Bellman–Ford 是否解全點對、Floyd–Warshall 在有負環時是否仍正確
- 第 8 題（8%）｜給一段
Cycle-Removal(G,u)的 pseudo-code，節點分成 Type-0/1/2 三色，要填出第 8、10、11、14 行的 A、B、C、D 四個值使它能正確輸出無環圖。這就是 DFS 的白灰黑三色法，考的是能不能認出來 - 第 9 題（10%）｜14 艘船要到對岸，同字母的船才能停同字母的碼頭，航線交叉的船必須等 15 分鐘。(a) 9 點能出發的最大船數 (b) 寫出那些船的編號。本質是非交叉匹配 / LIS 型的 DP
- 第 10 題（10%）｜給一串圖形與一張替換規則表（含替換前後成本），求總成本最小的替換方式。(a) 最小總成本 (b) 由左至右列出使用的規則。這是一維的區間 DP，與 rod cutting 同型
這份考卷的難點
- 沒有部分分數。 第 5(c) 的三個空格、第 8 題的四個值、第 6(b) 的整張 hash 表，只要錯一格整題歸零，容錯率極低。
- 第 9、10 題的「包裝」是最大障礙。 題面完全不提匹配或 DP，要自己看穿船隻交叉其實是逆序對、圖形替換其實是區間 DP。
- 第 5 題佔 20 分，且 (c) 的三路分割（Dutch national flag）不是每本課本都會講。
- 第 6(c) 要能講出「h2(k) 必須與 m 互質」的理由，這個觀念在 115 年第 16 題又考了一次。
準備建議
- Catalan number 的三種常見場景（stack 排列、二元樹形狀數、括號合法序列）要一起記，台大 108 考 stack 排列
- Quicksort 的三路分割（Dutch national flag partition）建議實際寫過一次，不然第 5(c) 很難現場推
- hash 的 h2(k) 與表大小互質是台大反覆出現的細節（108 第 6(c)、115 第 16 題）
- 看到「情境題」先問自己「這是不是某個經典問題換皮」—— 台大很愛這樣出題，109 的 SNP 題（其實是 set cover）、110 的 snake sequence（其實是格子 DP）、114 的球隊淘汰題（其實是 max flow）都是同一個套路