112 成大資工所軟體考點分析

題型與配分

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

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

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

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

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

• 第 11 題｜用 Master method 求 T(n) = 27T(n/3) + Θ(n³/lg n) 的緊界。與 109 年 Part II 第 5 題完全相同 —— 答案同樣是 Master theorem 不適用（落在 case 2 與 case 3 之間的 gap）
• 第 12 題｜Matrix chain order 的 bottom-up pseudo-code 填空三格：(a) j = i + l − 1、(b) q = m[i,k] + m[k+1,j] + p_{i−1}·p_k·p_j、(c) s[i,j] = k
• 第 13 題｜對陣列 [5, 13, 2, 25, 7, 17, 20, 8, 4] 完整演示 HEAPSORT 的過程
• 第 14 題｜最佳二元搜尋樹：n = 7 個真實鍵與 8 個虛擬鍵，給定機率求最佳 BST 的成本與結構。與 106 年第 5 題、111 年第 14 題同型，但規模最大
• 第 15 題｜給一張標了容量的流網路，求 s 到 t 的最大流

這份考卷的難點

1. 第 14 題的最佳 BST 規模是三次考題中最大的（7 個鍵、8 個虛擬鍵），要填一張 8×8 的 DP 表，禁用計算器的情況下極耗時間。
2. 第 8 題的 Min-Max heap 是很少見的結構（奇偶層交替為 min／max），要先弄清楚規則才能判斷。
3. Part I 全部是複選題且要整理成表格，十題各 5 分，判斷不精確就大量失分。
4. 第 10 題的 trie 家族比較（trie／compressed trie／Patricia／digital search tree）需要對四種結構的空間與比較次數都有掌握。

準備建議

• 最佳二元搜尋樹在成大 106、111、112 考了三次，是十年最高頻的手寫題，DP 表的填法務必練熟
• Master theorem 不適用的同一題在 109、112 出現兩次（T(n)=27T(n/3)+Θ(n³/lg n)），成大重複出題的傾向很明顯
• trie 家族（trie／compressed trie／Patricia／digital search tree）與 Min-Max heap 是成大偏好的冷門結構，111、112 連兩年出現
• Matrix chain order 的 pseudo-code 要能默寫，成大 112 直接考填空
• 記得 Part I 要在答案卷第一頁做表，這是成大 111、112 明訂的規定