108 成大資工所軟體考點分析
資料結構 50%＋演算法 50%、全卷 8 題手寫。最大特色是第 3 題的 winner tree／loser tree（20 分），這是成大十年唯一一次考外部排序的敗者樹。
題型與配分
編號 202，系所「電機資訊學院－資訊聯招」，考試科目：程式設計，考試日期 108 年 2 月 23 日第 2 節，全卷 2 頁、8 題、100 分，不可使用計算機。
| 區段 | 題號 | 配分 |
|---|---|---|
| Part I 資料結構 | 1–3 | 50% |
| 二、演算法 | 4–8 | 50%（每題 10 分） |
Part I 資料結構考點（1–3）
- 第 1 題（12%，3 小題各 4%）｜是非題，答錯要寫出正確答案或清楚說明理由：
- (1) 圖用 adjacency matrix 表示時，DFS 是否需要 O(e2) 時間（假，是 O(v2)）
- (2) MST 上 u 到 v 的路徑是否也是最短路徑（假，經典陷阱）
- (3) static hashing 中 open addressing 成功搜尋的最壞比較次數是否 O(n)、改用 chaining 能否降到 O(log n)
- 第 2 題（18%）｜AOE network：(1) 7% 求出所有活動的 e(i) 與 l(i) (2) 7% 列出所有關鍵活動 (3) 4% 列出所有關鍵路徑。要完整跑一次 earliest／latest time 的前推後推
- 第 3 題（20%）｜Winner tree 與 loser tree（外部排序的 k-way merge）：(1) 5% 畫出 winner tree (2) 5% 輸出一筆記錄後重整的 winner tree (3) 5% 依據 (2) 畫出對應的 loser tree (4) 5% 推導用 k 路 winner tree 合併 n 筆記錄的總時間。這是全卷配分最高、也最偏門的一題
二、演算法考點（4–8）
- 第 4 題（10%）｜「如何證明一個問題是 NP-complete？」要寫出完整步驟：先證屬於 NP，再從已知 NPC 問題歸約過來
- 第 5 題（10%）｜設計判斷無向圖是否含環的演算法，要求 O(V) 時間、與 |E| 無關。與 106 年第 7 題完全相同
- 第 6 題（10%，5 小題各 2%）｜是非題並說明理由：
- (a) 0-1 knapsack 能否用貪婪解（否）
- (b) 無向圖的 DFS 能否得到 cross edge（否，無向圖只有 tree edge 與 back edge）
- (c) top-down 方法能否用 memoization 降低時間
- (d) 無權最長簡單路徑是否有最佳子結構（否，這是 CLRS 的經典反例）
- (e) 先拓撲排序再跑 DFS 是否就不會有 back edge
- 第 7 題（10%）｜用 Master theorem 解 T(n) = T(2n/3) + 1（答案 Θ(log n)）
- 第 8 題（10%）｜從節點 0 出發（小號碼優先）寫出 BFS 生成樹
這份考卷的難點
- 第 3 題的 winner tree／loser tree（20 分）是最大變數。 這是外部排序的內容，許多課程會略過，但成大一次給了 20 分。敗者樹的「節點存敗者、冠軍另外記」這個設計必須清楚。
- 第 2 題的 AOE network（18 分）計算量大，e(i)、l(i) 要對每個活動都算，錯一個關鍵活動就連帶影響關鍵路徑。
- 第 6(d) 的「最長簡單路徑沒有最佳子結構」是 CLRS 的經典反例，要能舉例說明（子路徑最長不代表整體最長，因為會重複用到節點）。
- 是非題要寫理由（第 1、6 題合計 22 分），不能只圈對錯。
準備建議
- Winner tree 與 loser tree 建議補齊（108 第 3 題），這是《資料結構》教科書（Horowitz）的內容而非 CLRS
- AOE network 的 critical path 在成大 108、中央多年都考，前推 earliest、後推 latest 的流程要練熟
- 「MST 上的路徑不是最短路徑」「無向圖 DFS 沒有 cross edge」「最長簡單路徑無最佳子結構」—— 這三個是非題陷阱在多校反覆出現
- 「O(V) 判斷無向圖有無環」成大 106、108 連兩年考同一題，成大有重複出題的習慣，練考古題時要注意跨年度比對