109 成大資工所軟體考點分析｜國立成功大學

資料結構 50%＋演算法 50%、全卷 8 題手寫。第 2 題的 Bloom filter 錯誤率推導是十年唯一一次，第 5 題則考 Master theorem「不適用」的情況。

題型與配分

編號 206，系所「電機資訊學院－資訊聯招」，考試科目：程式設計，考試日期 109 年 2 月 10 日第 2 節，全卷 2 頁、8 題、100 分，不可使用計算機。

區段	題號	配分
Part I 資料結構	1–3	50%
Part II 演算法	1–5	50%（每題 10 分）

第 1 題（30%，5 小題各 6%）｜是非題，答錯要寫出正確答案：
(1) static hashing 中 open addressing 成功搜尋最壞 O(n)、改用平衡搜尋樹能否降到 O(log n)
(2) 圖中所有頂點的度數總和與邊數的關係 e = Σd_i 是否正確（假，應為 2e = Σd_i）
(3) MST 上 u 到 v 的路徑是否也是最短路徑（與 108 年第 1(2) 題完全相同）
(4) 圖用 adjacency list 表示時 DFS 是否需要 O(e²)（假，是 O(v+e)）
(5) AOV network 可行時，拓撲順序是否不唯一
第 2 題（10%）｜Bloom filter 的錯誤率推導：m 個位元、h 個獨立均勻雜湊函式，做了 u 次更新後，任意查詢發生 filter error 的機率是多少。標準答案是 (1 − (1 − 1/m)^hu)^h。這是成大十年唯一一次考 Bloom filter
第 3 題（10%）｜給一張帶權圖，求最小成本並建出 MST

第 1 題（10%）｜判斷 5ⁿ⁺¹ = O(5ⁿ) 是否成立、6²ⁿ = O(6ⁿ) 是否成立。答案一真一假 —— 前者只差常數 5 倍（真），後者是 36ⁿ 對 6ⁿ（假）
第 2 題（10%）｜求 T(n) = √n·T(√n) + n 的漸進上下界，要盡可能緊。需要換元（令 m = lg n）
第 3 題（10%）｜說明如何讓 quicksort 的時間複雜度達到 O(n lg n)（用 median of medians 選 pivot，或隨機化＋期望分析）
第 4 題（10%）｜求 <1,0,0,1,0,1,0,1> 與 <0,1,0,1,1,0,1,1,0> 的 LCS
第 5 題（10%）｜「If possible, use the master method to solve T(n) = 27T(n/3) + Θ(n³/lg n)」。關鍵在 If possible —— 這裡 f(n) = n³/lg n 與 n^log₃27 = n³ 的差距不是多項式等級，Master theorem 不適用，要能指出這一點

第 5 題（Part II）是全卷最大的陷阱。 題目寫「if possible」就是在暗示可能不行，硬套 Master theorem case 1/2/3 都會錯，正確答案是「三種 case 都不適用（落在 case 2 與 case 3 之間的 gap）」。
第 2 題的 Bloom filter 需要自己推導機率，而不是背公式。要先算出某個位元在 u 次更新後仍為 0 的機率。
第 2 題（Part II）的 T(n) = √n·T(√n) + n 係數帶 √n，換元後要小心處理。
是非題佔 30 分且答錯要寫正確答案，相當於每題都要完整論述。

Master theorem 不適用的情況（109 Part II 第 5 題）是成大特別愛考的細節，要知道 case 2 與 case 3 之間有 gap
是非題有多題與 108 年重複（MST 路徑、DFS 複雜度、hashing），成大 106–109 的是非題重複率極高，一定要成組練習
Bloom filter 雖只考過一次，但機率型資料結構近年在各校都在增加，值得了解
換元法解遞迴式（T(n)=√n·T(√n)+n）在成大 109、台大 106、114 都出現，是必備技巧