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

題型與配分

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

Part I 資料結構考點（1–3）

• 第 1 題（12%）｜是非題，答錯要寫出正確答案或清楚說明理由，三小題各 4%
• 第 1(1) 題｜圖用 adjacency matrix 表示時，DFS 是否需要 O(e²) 時間
• 第 1(2) 題｜MST 上 u 到 v 的路徑是否也是 shortest path
• 第 1(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% 列出所有 critical path
• 第 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，要寫出完整步驟
• 第 5 題（10%）｜設計判斷 undirected graph 是否含 cycle 的演算法，要求 O(V) 時間、與 |E| 無關，題意與 106 第 7 題相同（106 年沒有寫與 |E| 無關）
• 第 6 題（10%）｜是非題並說明理由，五小題各 2%
• 第 6(a) 題｜0-1 knapsack 能否用 greedy 解
• 第 6(b) 題｜undirected graph 的 DFS 能否得到 cross edge
• 第 6(c) 題｜top-down 方法能否用 memoization 降低時間
• 第 6(d) 題｜無權 longest simple path 是否有 optimal substructure
• 第 6(e) 題｜先 topological sort 再跑 DFS 是否就不會有 back edge
• 第 7 題（10%）｜用 Master theorem 解 T(n) = T(2n/3) + 1
• 第 8 題（10%）｜從節點 0 出發（小號碼優先）寫出 BFS spanning tree

作答時要注意的地方

1. 第 1、6 題是非題要寫理由或正確答案，合計 22 分。
2. 第 3 題 20 分、第 2 題 18 分，是 Part I 配分最高的兩題。
3. 第 8 題指定從節點 0 出發、小號碼優先。

準備方向

• winner tree 與 loser tree（108 第 3 題）。
• AOE network 的 critical path（108 第 2 題）。
• 判斷 undirected graph 有無 cycle：106 第 7 題、108 第 5 題。
• MST 路徑與 shortest path 的關係：108 第 1(2) 題、109 Part I 第 1(3) 題。
• undirected graph DFS 的邊分類、longest simple path 的子結構（108 第 6 題）。
• Master theorem：106 第 8 題、107 第 9 題、108 第 7 題、109 Part II 第 5 題。
• NP-complete 的證明步驟（108 第 4 題）。