110 台大資工所軟體考點分析

題型與配分

科目「資料結構與演算法（A）」（題號 397、節次 1），全卷 4 頁、20 題選擇題、100 分，全部作答於答案卡。

倒扣規則：卷面明訂「每題答對 5 分，不答零分，答錯倒扣 2.5 分」。答錯的代價是答對的一半，猜對機率需高於三分之一才划算。

這是台大 106 年以來第一次完全沒有非選擇題。 從 110 年起，選擇題成為台大軟體的主要形式。

逐題考點

• 第 1 題（I）｜Quicksort 最壞情況何時發生 —— 三種情境（每次選中位數、最左元素且已正序、最左元素且已逆序）的組合判斷
• 第 2–5 題（II）｜Snake sequence 的 DP，給一個 4×4 數字格子，相鄰數字差 ±1 才能延伸：
• 第 2 題｜最長蛇序列的長度
• 第 3 題｜此解法的時間複雜度
• 第 4 題｜最長序列的最後一個數字（含座標）
• 第 5 題｜最長序列的第三個數字
• 四題共 20 分，必須完整算出整張 DP 表
• 第 6 題（III）｜「把問題切成同型的較小子問題再遞迴求解」是哪一類演算法 —— 送分的定義題
• 第 7–8 題（IV）｜給定兩組只能透過 f()／g() 存取陣列 A 與指標 p、q 的函式，判斷各自實作出的是哪種資料結構。第 7 題是 stack（同一個指標增減），第 8 題改成 q 寫入、p 讀出，變成 queue
• 第 9–10 題（V）｜二元樹以陣列表示 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 格環狀陣列、h(k)=k mod 9：第 11 題問第一個發生碰撞的資料、第 12 題問用 linear probing 時 37 落在哪一格。要先把十六進位換成十進位再算
• 第 13 題（VII）｜n 個元素的單向串列，只有 head 指標時的尾端插入／刪除複雜度 f₁、g₁，加上 tail 指標後變成 f₂、g₂，問四個比值極限哪一個是錯的。關鍵：加 tail 後插入變 O(1)，但刪除最後一個元素仍是 O(n)
• 第 14–15 題（VIII）｜給一張帶權圖：第 14 題問 Kruskal 加入的第六條邊、第 15 題問 Prim 從 A 出發納入的第六個頂點
• 第 16 題（IX）｜給定 s-t 流網路，求 maximum flow 的值
• 第 17 題（X）｜KMP 的 prefix function，給一個長度 10 的 pattern，求 π 值的最大值
• 第 18 題（XI）｜字串比對的有限自動機：給一張殘缺的狀態轉移表，要反推原字串 s，再問 s 裡有幾個 A
• 第 19 題（XII）｜已知 PROBLEM A 是 NP-complete 且 A 可線性時間歸約到 B，判斷四個推論何者成立 —— 考的是歸約方向與 P = NP 的關係
• 第 20 題（XIII）｜Vertex-Cover 歸約到 Subset-Sum：給一張圖、k = 3 與已建好的集合 S，問對應的 target t 是多少。要看懂歸約中每個頂點與每條邊如何編碼成數字

這份考卷的難點

1. 倒扣 2.5 分，但題目普遍需要計算。 第 2–5、11–12、14–16 題都得完整跑一次演算法，時間壓力大又不能亂猜。
2. 第 18 題（自動機反推字串）是全卷最難的一題，必須從殘缺的轉移表回推原字串，沒有現成套路。
3. 第 20 題的 Vertex-Cover → Subset-Sum 歸約是 CLRS 裡的進階內容，要記得「每個頂點一列、每條邊一列，用 base-4 編碼」的構造才算得出 t。
4. 第 2–5 題四題連動：DP 表算錯一格，20 分一起沒了。

準備建議

• KMP 的 prefix function 與字串比對自動機在台大出現頻率極高（110 的第 17、18 題，111 的第 11 題，112 的第 16 題，115 的第 8 題），是必守主題
• Kruskal 與 Prim 要能標出加入順序，而不只是畫出最後的 MST
• NP 歸約的方向（A ≤_p B 代表 B 至少和 A 一樣難）務必畫圖釐清，110 的第 19 題、114 的第 17 題、115 的第 5、6 題都在考這件事
• 格子型 DP（snake sequence、最小路徑和、LCS）要練到能快速填表