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

題型與配分

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

作答規定：Part I 明訂「請在答案卷第一頁做表，將答案整理於該表中，否則不予計分」，沿用 111 年的格式要求。

Part I 資料結構考點（1–10，各 5 分，多為複選）

• 第 1 題｜樹的基本性質：n 節點 BST 搜尋的比較次數、高度 h 的 full binary tree 節點數、array 表示時父節點索引、AVL／red-black tree／compressed trie 是否都是 binary tree
• 第 2 題｜給一棵 max heap，移除最大元素後：30 是否為葉、array 第 5 個元素、post-order 中 55 與 42 的先後、25 在 post-order 與 in-order 的索引是否相同、移除的複雜度
• 第 3 題｜MST：從節點 L 出發跑 Prim 時最後加入的邊、MST 是否唯一、移除某條邊後 MST 是否改變
• 第 4 題｜給一棵 AVL tree，五個獨立的操作（插入 18／33／38、刪除 35／22）中，哪些會造成失衡而需要重整
• 第 5 題｜red-black tree 依序插入 6, 14, 11 後的紅節點數、各節點顏色與父子關係
• 第 6 題｜m-way search tree 與 B-tree 的性質：最大資料量、2-3-4 tree 是否為 order 5 的 B-tree、內部節點的子節點數下界、red-black tree 是否為 2-3 tree 的二元形式
• 第 7 題｜大小 10 的 linear probing hash table、h(k) = k % 10，給定最終表格，反推哪一個插入順序是可能的
• 第 8 題｜Min-Max heap：給定 array，交換哪兩組數值後仍不是合法的 Min-Max heap
• 第 9 題｜Patricia trie：插入 0110 再刪除 1100 後，節點 1101 指向誰
• 第 10 題｜trie 家族的比較：trie 與 digital search tree 的比較次數、compressed trie 的儲存開銷、Patricia 與 compressed trie 與 digital search tree 的優劣

Part II 演算法考點（11–15，各 10 分）

• 第 11 題｜用 Master method 求 T(n) = 27T(n/3) + Θ(n³/lg n) 的緊界，與 109 Part II 第 5 題相同
• 第 12 題｜Matrix chain order 的 bottom-up pseudo-code 填空三格
• 第 13 題｜對 array [5, 13, 2, 25, 7, 17, 20, 8, 4] 完整演示 HEAPSORT 的過程
• 第 14 題｜optimal BST：n = 7 個 key 與 8 個 dummy key，給定機率求最佳 BST 的成本與結構，與 106 第 5 題、111 第 14 題同型
• 第 15 題｜給一張標了容量的 flow network，求 s 到 t 的 max flow

作答時要注意的地方

1. Part I 要在答案卷第一頁做表，否則不予計分。
2. Part I 十題都是選擇題、每題 5 分，多數問「哪些敘述正確」，第 9 題問節點 1101 指向誰，答案只有一個。
3. 第 14 題要填一張大型 DP 表，且不可使用計算機。
4. 第 13 題要求完整演示過程。

準備方向

• optimal BST：106 第 5 題、111 第 14 題、112 第 14 題。
• Master theorem：109 Part II 第 5 題與 112 第 11 題為同一題。
• trie 家族與 Patricia：111 第 6 題、112 第 9、10 題、113 第 10 題。
• Min-Max heap：112 第 8 題，113 第 2 題的 symmetric min-max heap、115 第 10 題的 SMMH。
• Matrix chain order（112 第 12 題），113 第 12 題也是 matrix chain multiplication。
• red-black tree、AVL tree 與 B-tree：112 第 4、5、6 題。
• heapsort（112 第 13 題）。