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

題型與配分

全卷 3 頁、10 題、100 分，不可使用計算機，全部手寫。

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

• 第 1 題（10%）｜BST 中存放 1 到 1000 的數字、要搜尋 363，五個序列中哪些不可能是被檢查過的節點序列
• 第 2 題（10%）｜給一張 weighted graph，求 MST 與其總成本
• 第 3 題（10%）｜給一張圖，填出它的 adjacency matrix
• 第 4 題（10%）｜amortized analysis：stack 支援 PUSH、POP、MULTIPOP（成本 1+min(s,k)），求 n 次操作的總成本
• 第 5 題（10%）｜高度 h 的 heap 最多有幾個元素

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

• 第 6 題（10%）｜如果有人給出某個 NP-hard 問題的多項式演算法，可以推論出什麼
• 第 7 題（10%）｜以比較與交換為基礎的排序，其下界是多少，並說明論證
• 第 8 題（10%）｜給一張標了容量的 flow network，求 s 到 t 的 max flow
• 第 9 題（10%）｜用 Master theorem 解 T(n) = 3T(2n/3) + O(1)
• 第 10 題（10%）｜給 APPROX-VERTEX-COVER 演算法（每次任取一條未覆蓋的邊、把兩端點都放入），求它的最小 approximation ratio δ，並要能論證

作答時要注意的地方

1. 十題各 10 分，配分平均。
2. 第 10 題要求最小的 δ 並論證，不只是說出 approximation ratio。

準備方向

• MULTIPOP 的 amortized analysis（107 第 4 題），aggregate、accounting、potential 三種方法。
• vertex cover 的 approximation algorithm：107 第 10 題，台大 113 也有。
• BST 搜尋序列是否合法：107 第 1 題，台大 106 第 2 題同型。
• Master theorem：106 第 8 題、107 第 9 題、108 第 7 題、109 Part II 第 5 題。
• 排序下界：107 第 7 題、113 第 14 題。
• max flow：107 第 8 題，108 數學第 6 題、112 第 15 題也考。
• heap 的元素數量：106 第 3 題、107 第 5 題。