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

題型與配分

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

科目雖然叫「程式設計」，但完全不考語法，考的是資料結構與演算法。這是成大十年不變的特色，看到科目名稱不要誤判準備方向。

卷面註明「於本試題紙上作答者，不予計分」，必須寫在答案卷上。

全部是手寫題。

一、資料結構考點（1–5）

• 第 1 題（10%）｜給 inorder JHKFIDGBEAC 與 preorder ABDFHJKIGEC：(a) 5% 重建二元樹 (b) 5% 寫出 postorder
• 第 2 題（10%）｜11 個槽（從 250 開始），要設計一個 division method 的雜湊函式，讓 42, 77, 85, 113, 315, 433, 474, 479, 574, 582, 698 完全不碰撞，並畫出雜湊表。這題要自己找出合適的除數，是反向設計題
• 第 3 題（10%）｜高度 h 的 heap，元素數量的最小值與最大值各是多少
• 第 4 題（10%）｜設計 O(n lg k) 的演算法把 k 條已排序串列合併成一條（n 為總元素數）。標準解是 min-heap 維護 k 個候選
• 第 5 題（10%）｜最佳二元搜尋樹（Optimal BST）：給 6 個鍵值與其機率、7 個虛擬鍵與其機率，依題目給的期望搜尋成本公式求出最佳 BST 的成本。要跑完整的區間 DP

二、演算法考點（6–9）

• 第 6 題（18%）｜little-o 記號的六個是非題，包含 n = o(8n)（假，同階不算 little-o）、2ⁿ = o(n²)、2ⁿ = o(4ⁿ)、n = o(lg n) 等。這是全卷配分最高的一題，也是最容易失分的地方 —— little-o 要求嚴格小於，同階就不成立
• 第 7 題（12%）｜設計 O(V) 時間的演算法判斷無向圖是否含環。關鍵：若 |E| ≥ |V| 則必有環，所以 DFS 最多走 V 條邊就能停 —— 與 |E| 無關
• 第 8 題（10%）｜用 Master method 解 T(n) = 7T(n/2) + Θ(n²)（答案 Θ(n^log₂7)，即 Strassen 的複雜度）
• 第 9 題（10%）｜半連通（semiconnected）：有向圖 G 中任兩點必有一方可達另一方，設計線性時間演算法判定。標準解是先縮成 SCC 的 DAG，再檢查拓撲順序上相鄰的點是否都有邊

這份考卷的難點

1. 第 6 題（18 分）的 little-o 判斷看似簡單但陷阱很多。n = o(8n) 是假的（常數倍不影響階），很多人會答對成假。
2. 第 9 題的半連通判定需要同時掌握 SCC 縮點與拓撲排序，是研究所等級的題目。
3. 第 2 題要自己設計雜湊函式使 11 個特定鍵值完全不碰撞，得實際試幾個除數。
4. 第 5 題的最佳 BST 要填一張 6×6 以上的 DP 表，禁用計算器的情況下計算量很大。

準備建議

• 成大的「程式設計」= 資料結構 50% + 演算法 50%，兩部分配分固定，準備時要平均分配
• little-o 與 big-O 的差別（106 第 6 題佔 18 分）務必弄清楚：o 要求嚴格小於，O 允許同階
• 「O(V) 判斷無向圖有無環」這題成大在 106、108 連續兩年考（108 第 5 題一字不差），是必背題
• Master theorem 幾乎每年都考（106 第 8 題、107 第 9 題、108 第 7 題、109 第 5 題），三種 case 與不適用的情況都要熟
• SCC、拓撲排序、最佳 BST 這類進階內容成大都會考，CLRS 要讀完整