111 成大資工所軟體考點分析
成大改版最大的一年：資料結構改成 12 個題組、16 頁，考了 Patricia trie、Bloom filter、2-3-4 tree、Fibonacci heap 等罕見主題。
題型與配分
編號 201，系所「電機資訊學院－資訊聯招」，考試科目：程式設計，考試日期 111 年 2 月 19 日第 2 節，全卷 16 頁、17 題、100 分，不可使用計算機。
這是成大十年來篇幅最長的一份考卷（16 頁，前一年只有 3 頁）。
| 區段 | 題號 | 配分 |
|---|---|---|
| Part I 資料結構 | 1–12（12 個題組） | 50% |
| Part II 演算法 | 13–17 | 50%（每題 10 分） |
作答方式特殊：Part I 要求「在一頁上提供一張整合的表格」來彙整所有答案，卷面第 1 頁直接給出表格的格式與每一小題的配分。沒有照這個格式寫會很難閱卷。
Part I 資料結構考點（1–12）
- 第 1 題（4%，2 格）｜給一支把 prefix 運算式轉 postfix 的完整 C 程式，填
Stack_pop與Stack_push的兩個空格（指標操作） - 第 2 題（2%）｜Disjoint set 的 union by height：給兩棵樹，合併後的結果是哪一個
- 第 3 題（5%）｜給一棵紅黑樹插入 62：(i) 2% 結果是哪一棵 (ii) 3% 畫出它對應的 2-3-4 tree。紅黑樹與 2-3-4 樹的對應關係是成大特有的考點
- 第 4 題（4%）｜Bloom filter：給三個具體的雜湊函式與一張 16 格的 filter，判斷 8 與 9 各自是「不在」「可能在」還是「在」。注意 Bloom filter 永遠不能斷定「在」
- 第 5 題（2%）｜B-tree 依序刪除 70, 10, 60, 95 後的結果
- 第 6 題（5%）｜Patricia trie：插入 1001, 1100, 0000, 0001 後 (i) 2% 畫出結果 (ii) 3% 畫出對應的壓縮二元 trie。這是十年間唯一一次考 Patricia
- 第 7 題（2%）｜給一張圖從節點 1 開始做 DFS，哪些是可能的走訪序列
- 第 8 題（4%，5 格）｜linear probing 雜湊表，f(x) = x mod 17，依序插入 23, 52, 11, 1, 50, 99, 65, 20, 35, 34, 82，填出表中五個空格
- 第 9 題（4%，4 格）｜Quicksort 的 C 程式填空：
Partition裡的i++、回傳值，以及QuickSort的兩次遞迴呼叫範圍 - 第 10 題（4%）｜給一支遞迴函式
unknown（先遞迴左右子樹、再交換左右子節點）：(i) 2% 它是哪一種走訪順序（postorder） (ii) 2% 執行後最右葉節點的值 - 第 11 題（6%）｜Min-Heap 的 job priority queue，三個步驟連動：extract 一次後 Q[4] 的值、再 extract 一次後 Q[5] 的值、再插入優先權 11 後 Q[9] 的值。三步驟連動，第一步錯全錯
- 第 12 題（8%）｜Fibonacci heap 的 DecreaseKey：填 pseudo-code 的兩個空格（切斷條件、CUT 後的 parent 設定），並回答 DecreaseKey 的攤銷複雜度與 insert 的複雜度
Part II 演算法考點（13–17，各 10%）
- 第 13 題｜求 T(n) = 2T(n/2) + √n·log n 的緊界 Θ
- 第 14 題｜最佳二元搜尋樹：5 個真實鍵、6 個虛擬鍵，給定機率求最佳 BST 的成本。與 106 年第 5 題同型
- 第 15 題｜給一個有向強連通圖，設計演算法判斷它是否含奇數長度的有向環。標準解：對強連通圖做二分著色，若不是二分圖則存在奇環
- 第 16 題｜差限制系統（system of difference constraints）：求一組可行解或證明無解。要建約束圖後跑 Bellman-Ford（有負環則無解）
- 第 17 題｜給 CLRS 的
GREEDY-SET-COVER演算法，求它的最小近似比 ρ。答案是 H(max|S|) ≈ ln n，要能論證
這份考卷的難點
- 主題冷門度是十年最高。 Patricia trie、Bloom filter、2-3-4 tree、Fibonacci heap 的 DecreaseKey —— 這四個主題加起來 21 分，都不是必修課會細講的內容。
- 第 11 題三步驟連動（6 分），第一步的 extract-min 重整算錯，後兩小題必錯。
- 第 17 題要算出 greedy set cover 的緊近似比（H_n 而非常數），與 107 年的 vertex cover 2-近似形成對比。
- 16 頁的閱讀量加上要把答案整理成一張表格，時間壓力遠大於前幾年。
準備建議
- 111 年是成大出題風格的分水嶺：從「少題大分」轉向「多題組、多細節」，112 年之後延續這個方向
- 紅黑樹 ↔ 2-3-4 樹的對應（111 第 3 題）務必弄懂，這是成大獨有的考法
- Fibonacci heap 的 DecreaseKey / CUT / CASCADING-CUT 要能默寫，成大 111 直接考填空
- Bloom filter 的三種答案（「不在」是確定的、「可能在」、永遠不能說「在」）是必考觀念，成大 109、111 連兩次出現
- 近似比的計算：vertex cover 是 2、set cover 是 ln n —— 成大 107、111 分別考了這兩題