106 中央資工所軟體考點分析
全卷 8 題皆為問答題，要手寫完整演算法。最大特色是有三題「給你一份 pseudo-code，要你改寫成另一個演算法」，合計 38 分。
題型與配分
科目全名「資料結構與演算法」（所別：資工類），全卷 5 頁、8 題、100 分，禁用計算器，作答寫在答案卷內。
全部是問答題，沒有任何選擇題。 這和近年中央軟體的出題方式差很多，寫這一年的考卷要有「動手寫演算法」的心理準備。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | 遞迴程式追蹤 | 5 |
| 2 | Max heap 操作（3 小題） | 15 |
| 3 | BST 走訪與陣列表示法（3 小題） | 20 |
| 4 | Insertion sort 填空 | 10 |
| 5 | NP-complete 證明（2 小題） | 12 |
| 6 | 改寫搜尋演算法（3 小題） | 18 |
| 7 | 延伸 Dijkstra | 10 |
| 8 | 改寫 DP 演算法 | 10 |
逐題考點
- 第 1 題（5%）｜追蹤一段分治法求最小值的遞迴程式，寫出
printf的完整輸出。要注意遞迴呼叫的先後順序 - 第 2 題（15%）｜Max heap — (a) 把給定的二元樹調整成 max heap (b) 再插入 4 (c) 再刪除 8。三小題都要畫出結果的樹
- 第 3 題（20%）｜BST — (a) 寫出 postorder (b) 插入節點 5 後重畫整棵樹 (c) 二元樹存在陣列 A 中、節點 A[i] 的父節點存在 A[⌊i/2⌋]，補完 preorder 遞迴函式的兩個空格
- 第 4 題（10%）｜Insertion sort 程式填空，兩個空格，考的是
insert函式裡搬移元素的索引 - 第 5 題（12%）｜NP 理論 — 已知 X 是 NP-complete，(a) 如何利用多項式時間歸約證明 Y 是 NP-hard (b) 如何證明 Y 屬於 NP。這題要寫文字論證，不是選擇
- 第 6 題（18%）｜給定 BFS 的完整 pseudo-code，改寫成 DFS、hill climbing、best-first search 三種演算法，各 6 分。題目明確要求寫出完整的 input、output 和所有步驟
- 第 7 題（10%）｜給定 Dijkstra 的 pseudo-code，延伸它使其同時計入節點權重（終點節點的權重不列入路徑總長）
- 第 8 題（10%）｜給定 0/1 knapsack 的 DP 演算法，改寫成解 subset sum 問題
這份考卷的特點
- 「改寫 pseudo-code」是這份考卷的核心。 第 6、7、8 題合計 38 分全是這個型態 —— 給你一個你應該很熟的演算法，要你改動它的目標。光背演算法沒有用，必須真的懂每一行在做什麼。
- 畫圖題佔 35 分。 第 2、3 題要畫 heap 和 BST，中央很常考這種手繪題。
- 第 5 題是純文字論證，要寫得出歸約的方向（是把已知的 NP-complete 問題歸約到 Y，方向反了就零分）。
準備建議
- 對 BFS、DFS、hill climbing、best-first search、Dijkstra、0/1 knapsack、subset sum 這幾個演算法，要能默寫出完整 pseudo-code，而不只是說得出概念
- Heap 的插入與刪除、BST 的插入與走訪，要練到能快速手繪正確
- NP-hard 與 NP-complete 的證明步驟（歸約方向、如何證明屬於 NP）要能用文字寫清楚