111 成大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 16 頁、17 題、100 分，不可使用計算機。

作答方式：Part I 要求在一頁上提供一張整合的表格來彙整所有答案，卷面第 1 頁給出表格的格式與每一小題的配分。

Part I 資料結構考點（1–12）

• 第 1 題（4%，2 格）｜給一支把 prefix 運算式轉 postfix 的完整 C 程式，填 Stack_pop 與 Stack_push 的兩個空格（pointer 操作）
• 第 2 題（2%）｜disjoint set 的 union by height：給兩棵樹，合併後的結果是哪一個
• 第 3 題（5%）｜給一棵 red-black tree 插入 62：(i) 2% 結果是哪一棵 (ii) 3% 畫出它對應的 2-3-4 tree
• 第 4 題（4%）｜Bloom filter：給三個具體的 hash function 與一張 16 格的 filter，判斷 8 與 9 各自是「不在」「可能在」還是「在」
• 第 5 題（2%）｜B-tree 依序刪除 70, 10, 60, 95 後的結果
• 第 6 題（5%）｜Patricia trie：插入 1001, 1100, 0000, 0001 後 (i) 2% 畫出結果 (ii) 3% 畫出對應的壓縮二元 trie
• 第 7 題（2%）｜給一張圖從節點 1 開始做 DFS，哪些是可能的 traversal 序列
• 第 8 題（4%，5 格）｜linear probing hash table，f(x) = x mod 17，依序插入 23, 52, 11, 1, 50, 99, 65, 20, 35, 34, 82，填出表中五個空格
• 第 9 題（4%，4 格）｜Quicksort 的 C 程式填空：Partition 與 QuickSort 的四個空格
• 第 10 題（4%）｜給一支遞迴函式 unknown（先遞迴左右子樹、再交換左右子節點）：(i) 2% 它是哪一種 traversal order (ii) 2% 執行後最右葉節點的值
• 第 11 題（6%）｜Min-Heap 的 job priority queue，三個步驟連動：extract 一次後 Q[4] 的值、再 extract 一次後 Q[5] 的值、再插入 priority 11 後 Q[9] 的值
• 第 12 題（8%）｜Fibonacci heap 的 DecreaseKey：填 pseudo-code 的兩個空格，並回答 DecreaseKey 的 amortized 複雜度與 insert 的複雜度

Part II 演算法考點（13–17，各 10%）

• 第 13 題｜求 T(n) = 2T(n/4) + √n·log n 的緊界 Θ
• 第 14 題｜optimal BST：5 個 key、6 個 dummy key，給定機率求最佳 BST 的成本，與 106 第 5 題同型
• 第 15 題｜給一個有向 strongly connected 圖，設計演算法判斷它是否含奇數長度的 directed cycle
• 第 16 題｜差限制系統（system of difference constraints）：求一組可行解或證明無解
• 第 17 題｜給 GREEDY-SET-COVER 演算法，求它的最小 approximation ratio ρ，並要能論證

作答時要注意的地方

1. Part I 的答案要整理成一頁整合的表格，格式以卷面第 1 頁為準。
2. 全卷 16 頁，是成大 106 至 115 年中頁數最多的一份。
3. 第 11 題三個步驟連動，後面的小題接續前面操作後的堆。
4. 第 12 題 8 分，是 Part I 配分最高的一題。

準備方向

• red-black tree 與 2-3-4 tree 的對應：111 第 3 題、113 第 8、9 題。
• Fibonacci heap 的 DecreaseKey 與 cascading cut：111 第 12 題、113 第 7 題。
• Bloom filter：109 第 2 題、111 第 4 題、113 第 5 題、115 題組 A。
• Patricia trie：111 第 6 題、112 第 9 題、113 第 10 題。
• optimal BST：106 第 5 題、111 第 14 題、112 第 14 題。
• approximation algorithm 的 approximation ratio：107 第 10 題（vertex cover）、111 第 17 題（set cover）。
• 差限制系統：111 第 16 題、113 第 15 題。