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

題型與配分

科目「資料結構與演算法」（題號 295、節次 1），全卷 7 頁、19 題、100 分。

這一年完全沒有倒扣：單選題「答對 5 分，不答或答錯為 0 分」；複選題「每個選項單獨計分，選項答對得 1 分，選項答錯得 0 分」，只有整題未作答才是 0 分。

這代表每一題、每一個選項都應該填滿 —— 猜錯沒有任何代價。這是台大十年間對考生最寬鬆的計分方式。

單選題考點（1–7）

• 第 1 題｜隨機遞迴演算法印出的 ! 與 * 的期望個數，要挑最緊的界。本質是 randomized quicksort 的遞迴樹分析（答案分別是 O(n) 與 O(n log n)）
• 第 2 題｜Akra-Bazzi theorem 的性質判斷 —— 子問題可否不等大、g(n) 是否需滿足多項式成長條件、是否一定給出封閉解、是否比 Master theorem 更一般、p 是否必為整數。這是 CLRS 附錄等級的內容
• 第 3 題｜五條 DNA 序列做 k-means 分群：是否必收斂成三群、用 Hamming distance 時 a 和 b 是否必同群、是否保證全域最佳、用 2-mer 頻率向量時 c 和 d 是否必不同群、複雜度是否為 O(n)
• 第 4 題｜兩條蛋白質序列的全域比對 DP（match +2、mismatch −1、gap −2）：時間複雜度、空間複雜度、遞迴式寫法、回溯的起點、是否能找出所有最佳比對。這就是 Needleman-Wunsch
• 第 5 題｜化學結構編號：把分子當無向圖，頂點初值設為度數，反覆把每個頂點更新為鄰居值的總和，跑兩輪後依值排序。純手算，考的是耐心與細心
• 第 6 題｜容量 17 的 unbounded knapsack（物品可重複取），最大價值寫成 10a+b，求 a+b。要完整跑一次 DP
• 第 7 題｜球隊淘汰問題（baseball elimination）：把五隊的勝場與剩餘賽程建成 12 個節點的流網路（源點、匯點、6 個對戰節點、4 個球隊節點），求 maximum flow。這是 max flow 最經典的應用之一

複選題考點（8–17）

• 第 8 題｜五個函數兩兩比較成長速度，選出所有「後者成長快於前者」的配對
• 第 9 題｜五條遞迴式的解：T(n)=2T(n/2)+Θ(n)、T(n)=7T(n/2)+Θ(n²)、T(n)=log n+T(√n)、T(n)=2ⁿT(n−1)、T(n)=T(n/6)+T(7n/9)+O(n)。第三、四條需要換元，第五條要看出 1/6+7/9 < 1
• 第 10 題｜二元樹與 BST 的性質：每棵二元樹是否都是 BST、n 節點 BST 樹高是否 O(log n)、找次小元素是否 O(1)、三個已排序陣列合併建平衡 BST 是否 O(n)、完全二元樹用 BFS 找路徑是否需 Ω(n lg n)
• 第 11 題｜Universal hashing：n 個 key 雜湊到 m = ⌈n^1.5⌉ 個 bucket，問在 uniform hash family、universal hash family、以及兩個具體的 family（(ax+b) mod m 與 (x²+x+c) mod m）之下，最壞期望碰撞數是否為 O(√n)，並判斷 (C) 的 family 是否為 universal。這是研究所等級的雜湊理論
• 第 12 題｜同一張圖的兩棵 MST T₁、T₂，令 F 為只屬於其中一棵的邊集合：(V,F) 是否為環與路徑的不交聯集、F 中的邊是否等權、是否有唯一權重的邊、MOST-DISTANT-MSTS 問題是否 NP-hard
• 第 13 題｜給一段通用的 SOLVE(G, s, t) pseudo-code（就是 Dijkstra 的骨架），問填入不同的鬆弛式可以分別解出 ST-DISTANCE、ST-BOTTLENECK、MST。這題把 Dijkstra 與 Prim 的共通結構講得很透
• 第 14 題｜n×n 格子圖的 minimum cut，四位學生提出四種做法（暴力枚舉、單調路徑 DP、轉最大流用 Dinic、從西南邊界到東北邊界跑 Bellman-Ford），判斷誰對誰錯。格子圖的最小割對偶成對偶圖上的最短路是關鍵觀念
• 第 15 題｜樹上重新著色的 DP：讓每個非根節點與父節點顏色不同，最小化被重新著色的節點權重和。選項把它連結到最大權重獨立集、最小權重點覆蓋、最小權重支配集，並給出一條完整遞迴式
• 第 16 題｜0-1 整數線性規劃：問可行解個數 α、最佳解個數 β、integrality gap γ、以及鬆弛後 LP 的四維體積 v
• 第 17 題｜五個決策問題的歸約鏈（A ≤_p B ≤_p C ≤_p D、C ≤_p E，且 A ∈ P、B ∈ NP），逐一判斷推論是否成立。純邏輯推演，不需計算

非選擇題考點（18–19）

• 第 18 題（5%）｜k 位元二進位計數器的攤銷分析，但在一台「有缺陷的 RAM」上：索引 i 是 3 的倍數但不是 5 的倍數時，寫入要花 3^i/3 單位時間；是 5 的倍數但不是 3 的倍數時要花 5^i/5。要設計一個 potential function Φ(A) 讓每次 INCREMENT 的攤銷時間仍是 O(1)。題目明訂「本題沒有部分分數」，且 potential function 必須完全具體、不能留下未定常數
• 第 19 題（10%）｜ODDNUMBERSUM 決策問題。(a) 5% 證明它是 NP-complete (b) 5% 設計一個 (1−ε)-近似演算法，執行時間需為 |S| 與 1/ε 的多項式。這是 subset sum 的 FPTAS（修剪法），題目要求「除了演算法之外不要寫任何東西」

這份考卷的難點

1. 超綱內容多。 Akra-Bazzi（第 2 題）、universal hashing 的碰撞期望（第 11 題）、integrality gap（第 16 題）、FPTAS（第 19(b) 題）都超出一般資料結構課本。
2. 第 18 題是全卷最難的 5 分。 要為一個「寫入成本隨索引指數成長」的計數器設計位能函數，而且沒有部分分數。
3. 跨領域情境題增加：DNA 分群、蛋白質比對、化學結構編號、球隊淘汰，都需要先把題意翻譯成演算法問題。
4. 第 14 題的格子圖最小割要看穿「最小割 ↔ 對偶圖最短路」，四個選項每個都很像對的。

準備建議

• 這一年沒有倒扣，答案卡務必全部填滿，複選題更要逐個選項判斷 —— 對了加分、錯了不扣
• 近似演算法與 FPTAS（subset sum 的修剪法）已是台大的常態考點，114(19b)、113(13) 連續兩年出現
• Akra-Bazzi、universal/perfect hashing 這類進階內容，建議至少讀懂結論與適用條件，選擇題通常只考「哪個敘述對」
• Max flow 的建模（球隊淘汰、二分圖匹配、最小割）是台大十年的主軸之一，106、110、114 都考過
• 攤銷分析要練到能自己設計 potential function，而不只是套用課本的二進位計數器範例