110 台大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 4 頁、20 題選擇題、100 分，全部作答於答案卡。這一年起全卷沒有非選擇題。

倒扣規則：卷面明訂「每題答對 5 分，不答零分，答錯倒扣 2.5 分」。

逐題考點

• 第 1 題（I）｜Quicksort 最壞情況何時發生，三種情境（每次選 median、最左元素且已正序、最左元素且已逆序）的組合判斷
• 第 2–5 題（II）｜Snake sequence 的 DP，給一個 4×4 數字格子，相鄰數字差 ±1 才能延伸。第 2 題問最長蛇序列的長度，第 3 題問此解法的時間複雜度，第 4 題問最長序列的最後一個數字（含座標），第 5 題問最長序列的第三個數字
• 第 6 題（III）｜「把問題切成同型的較小子問題再遞迴求解」是哪一類演算法
• 第 7–8 題（IV）｜給定兩組只能透過 f()、g() 存取 array A 與 pointer p、q 的函式，判斷各自實作出的是哪種資料結構
• 第 9–10 題（V）｜binary tree 以 array 表示 T = {+, a, *, null, null, −, d, null, null, null, null, b, c}，T[i] 的子節點是 T[2i+1] 與 T[2i+2]。第 9 題問 postorder，第 10 題問 BFS（level-order）
• 第 11–12 題（VI）｜10 個十六進位數 53, 3B, 66, 43, 60, 5B, 7C, 14, 30, 37 依序插入 10 格 circular array、h(k)=k mod 9。第 11 題問第一個發生 collision 的資料，第 12 題問用 linear probing 時 37 落在哪一格
• 第 13 題（VII）｜n 個元素的 singly linked list，只有 head pointer 時的尾端插入、刪除複雜度 f₁、g₁，加上 tail pointer 後變成 f₂、g₂，問四個比值極限哪一個是錯的
• 第 14–15 題（VIII）｜給一張 weighted graph。第 14 題問 Kruskal 加入的第六條邊，第 15 題問 Prim 從 A 出發納入的第六個頂點
• 第 16 題（IX）｜給定 s-t flow network，求 maximum flow 的值
• 第 17 題（X）｜KMP 的 prefix function，給一個長度 10 的 pattern，求 π 值的最大值
• 第 18 題（XI）｜string matching 的 finite automaton：給一張殘缺的狀態轉移表，反推原字串 s，再問 s 裡有幾個 A
• 第 19 題（XII）｜已知 PROBLEM A 是 NP-complete 且 A 可線性時間 reduction 到 B，判斷四個推論何者成立
• 第 20 題（XIII）｜Vertex-Cover reduction 到 Subset-Sum：給一張圖、k = 3 與已建好的集合 S，問對應的 target t 是多少

作答時要注意的地方

1. 第 2–5、11–12、14–16 題都要完整跑一次演算法，同時有倒扣。
2. 第 2 到 5 題四題用同一張 DP 表。
3. 第 18 題要從殘缺的轉移表反推字串。
4. 第 20 題的 reduction 要自己算出 target t。

準備方向

• KMP 的 prefix function 與 string matching 自動機，在 110 第 17、18 題，111 第 11 題，112 第 16 題，115 第 8 題都出現。
• Kruskal 與 Prim 的加入順序，不只是最後的 MST。
• NP reduction 的方向，110 第 19 題、114 第 17 題、115 第 5、6 題都考。
• 格子型 DP（snake sequence、最小路徑和、LCS）。