107 成大資工所軟體考點分析
資料結構 50%＋演算法 50%、全卷 10 題手寫。多數是課本標準題（MST、最大流、攤銷分析、Master theorem），第 10 題要自己算出近似比。
題型與配分
編號 209，系所「電機資訊學院－資訊聯招」，考試科目：程式設計，考試日期 107 年 2 月 5 日第 2 節，全卷 3 頁、10 題、100 分，不可使用計算機。
| 區段 | 題號 | 配分 |
|---|---|---|
| 一、資料結構 | 1–5 | 50%（每題 10 分） |
| 二、演算法 | 6–10 | 50%（每題 10 分） |
配分非常整齊：十題各 10 分，全部手寫。
一、資料結構考點（1–5）
- 第 1 題（10%）｜BST 中存放 1 到 1000 的數字、要搜尋 363，五個序列中哪些不可能是被檢查過的節點序列。考的是搜尋路徑上的區間單調收縮
- 第 2 題（10%）｜給一張帶權圖，求 MST 與其總成本
- 第 3 題（10%）｜給一張圖，填出它的 adjacency matrix
- 第 4 題（10%）｜攤銷分析：stack 支援 PUSH、POP、MULTIPOP（成本 1+min(s,k)），求 n 次操作的總成本。這是 CLRS 攤銷分析章節的開場範例，答案 O(n)
- 第 5 題（10%）｜高度 h 的 heap 最多有幾個元素（與 106 年第 3 題同一組觀念）
二、演算法考點（6–10）
- 第 6 題（10%）｜「如果有人給出某個 NP-hard 問題的多項式演算法，可以推論出什麼？」考的是 NP-hard 的定義與 P = NP 的關係
- 第 7 題（10%）｜以比較與交換為基礎的排序，其下界是多少（Ω(n log n)，要能說明 decision tree 的論證）
- 第 8 題（10%）｜給一張標了容量的流網路，求 s 到 t 的最大流
- 第 9 題（10%）｜用 Master theorem 解 T(n) = 3T(2n/3) + O(1)
- 第 10 題（10%）｜給 CLRS 的
APPROX-VERTEX-COVER演算法（每次任取一條未覆蓋的邊、把兩端點都放入），求它的最小近似比 δ。答案是 2，要能論證
這份考卷的難點
- 這是成大十年間最「標準」的一份考卷。 十題幾乎都是 CLRS 的課本題或直接改編，沒有偏題。
- 第 1 題的五個序列要逐一檢查，稍不小心就漏判。判斷法則：搜尋路徑上的數字必須維持一個不斷縮小的區間。
- 第 9 題的 T(n) = 3T(2n/3) + O(1) 是 Master theorem 的 case 1，a = 3、b = 3/2，log3/23 ≈ 2.7，很多人會被非整數的 b 卡住。
- 第 10 題要算出「最小的 δ」，不只是說「這是 2-近似」，還要說明為什麼 2 是緊的（存在達到 2 倍的例子）。
準備建議
- MULTIPOP 的攤銷分析（107 第 4 題）是 CLRS 第 17 章的招牌範例，三種方法（aggregate／accounting／potential）都建議會
- 2-近似的 vertex cover 在成大 107、台大 113 都出現，要能寫出「取的邊構成 matching，因此 |C| = 2|M| ≤ 2|C*|」的論證
- 「BST 搜尋序列是否合法」這題成大 107 與台大 106 幾乎一樣，是跨校共通題型
- Master theorem 的三種 case 與 b 不是整數時的處理要練熟