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

題型與配分

全卷 7 頁、19 題、100 分。

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

單選題考點（1–7）

• 第 1 題｜隨機遞迴演算法印出的 ! 與 * 的期望個數，要挑最緊的界
• 第 2 題｜Akra-Bazzi theorem 的性質判斷：子問題可否不等大、g(n) 是否需滿足多項式成長條件、是否一定給出 closed-form solution、是否比 Master theorem 更一般、p 是否必為整數
• 第 3 題｜五條 DNA 序列做 k-means 分群：是否必收斂成三群、用 Hamming distance 時 a 和 b 是否必同群、是否保證全域最佳、用 2-mer 頻率向量時 c 和 d 是否必不同群、複雜度是否為 O(n)
• 第 4 題｜兩條蛋白質序列的全域比對 DP（match +2、mismatch −1、gap −2）：時間複雜度、空間複雜度、recurrence 寫法、backtracking 的起點、是否能找出所有最佳比對
• 第 5 題｜化學結構編號：把分子當 undirected graph，頂點初值設為 degree，反覆把每個頂點更新為鄰居值的總和，跑兩輪後依值排序
• 第 6 題｜容量 17 的 unbounded knapsack（物品可重複取），最大價值寫成 10a+b，求 a+b
• 第 7 題｜球隊淘汰問題（baseball elimination）：把五隊的勝場與剩餘賽程建成 12 個節點的 flow network（源點、匯點、6 個對戰節點、4 個球隊節點），求 maximum flow

複選題考點（8–17）

• 第 8 題｜五個函數兩兩比較成長速度，選出所有「後者成長快於前者」的配對
• 第 9 題｜五條 recurrence 的解：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)
• 第 10 題｜binary tree 與 BST 的性質：每棵 binary tree 是否都是 BST、n 節點 BST 樹高是否 O(log n)、找次小元素是否 O(1)、三個已排序 array 合併建平衡 BST 是否 O(n)、complete binary tree 用 BFS 找路徑是否需 Ω(n lg n)
• 第 11 題｜Universal hashing：n 個 key hash 到 m = ⌈n^1.5⌉ 個 bucket，問在 uniform hash family、universal hash family、以及兩個具體的 family（(ax+b) mod m 與 (x²+x+c) mod m）之下，最壞期望 collision 數是否為 O(√n)，並判斷 (C) 的 family 是否為 universal
• 第 12 題｜同一張圖的兩棵 MST T₁、T₂，令 F 為只屬於其中一棵的邊集合：(V,F) 是否為 cycle 與路徑的不交聯集、F 中的邊是否等權、是否有唯一權重的邊、MOST-DISTANT-MSTS 問題是否 NP-hard
• 第 13 題｜給一段通用的 SOLVE(G, s, t) pseudo-code，問填入不同的鬆弛式可以分別解出 ST-DISTANCE、ST-BOTTLENECK、MST 中的哪些
• 第 14 題｜n×n 格子圖的 minimum cut，四位學生提出四種做法（暴力枚舉、單調路徑 DP、轉 max flow 用 Dinic、從西南邊界到東北邊界跑 Bellman-Ford），判斷誰對誰錯
• 第 15 題｜樹上重新 coloring 的 DP：讓每個非根節點與父節點顏色不同，最小化被重新 coloring 的節點權重和。選項把它連結到最大權重 independent set、最小權重 vertex cover、最小權重 dominating set，並給出一條完整 recurrence
• 第 16 題｜0-1 整數線性規劃：問可行解個數 α、最佳解個數 β、integrality gap γ、以及鬆弛後 LP 的四維體積 v
• 第 17 題｜五個決策問題的 reduction 鏈（A ≤_p B ≤_p C ≤_p D、C ≤_p E，且 A ∈ P、B ∈ NP），逐一判斷推論是否成立

非選擇題考點（18–19）

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

作答時要注意的地方

1. 第 2 題 Akra-Bazzi、第 11 題 universal hashing、第 16 題 integrality gap、第 19(b) 題近似方案，都在一般資料結構課本的範圍外。
2. 第 18 題沒有部分分數，potential function 要寫得完全具體。
3. 第 3、4、5、7 題是跨領域情境，要先把題意轉成演算法問題。
4. 第 14 題四位學生的做法各有對錯，要逐一判斷。

準備方向

• approximation algorithm 與近似方案，114(19b) 與 113(13) 連續兩年出現。
• Akra-Bazzi、universal hashing 這類內容，選擇題考的是哪個敘述成立，結論與適用條件要知道。
• Max flow 的建模（球隊淘汰、bipartite matching、min cut），106、110、114 都考過。
• amortized analysis 要能自己設計 potential function，114 第 18 題就是例子。