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

題型與配分

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

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

• 第 1 題（10%）｜由 preorder 50, 15, 11, 3, 2, 22, 84, 80, 77, 90, 95 重建 BST，寫出樹的層數（題目定義根為 level 1）
• 第 2 題（10%）｜給字元與其出現頻率，求 Huffman code 編碼後的總位元數
• 第 3 題（10%）｜四個字串 abcdef、bcdefa、cdefab、defabc 存入 hash table
• 第 3(1) 題（5%）｜hash function 為「ASCII 值總和 mod 11」時發生幾次 collision
• 第 3(2) 題（5%）｜改為「ASCII 值乘上在字串中的位置後加總 mod 11」時發生幾次 collision
• 第 4 題（10%）｜給一段由兩個 for 迴圈先後執行的程式（先 i 由 1 到 2n、再 i 由 n 到 1，累加 sum）：(1) 5% n = 4 時的輸出 (2) 5% 時間複雜度 T(n)
• 第 5 題（10%）｜給一張 weighted graph，求 MST 的成本

Part II 演算法考點（6–9）

• 第 6 題（15%）｜用 Master method 求緊界，若不適用要指出並說明，五小題各 3%
• 第 6(1) 題｜T(n) = 2T(n/4) + √n
• 第 6(2) 題｜T(n) = T(n−1) + n lg n
• 第 6(3) 題｜T(n) = 3T(n/4) + n lg n
• 第 6(4) 題｜T(n) = 4T(n/2) + n² lg n
• 第 6(5) 題｜T(n) = 7T(n/2) + Θ(n²)
• 第 7 題（15%）｜是非題並說明理由，五小題各 3%
• 第 7(1) 題｜NPC 問題可多項式 reduction 到 L，L 是否必為 NPC
• 第 7(2) 題｜A 可 reduction 到 B 且 A ∈ P，是否 B ∈ P
• 第 7(3) 題｜A ∈ P 是否必有 A ∈ NP
• 第 7(4) 題｜P ≠ NP 時，一般 TSP 是否有 2-approximation algorithm
• 第 7(5) 題｜高度 h 的 heap 最多元素數是否為 2^h − 1
• 第 8 題（10%）｜Shuffle 字串：判斷 z 是否為 x 與 y 的 shuffle（例如 NioCKsiUe 與 NCKU、csie），要填 isShuffle pseudo-code 的三個空格
• 第 9 題（10%）｜Floyd-Warshall：(1) 2% 時間複雜度 (2) 3% 補完 D^k 由 D^k−1 遞推的公式 (3) 5% 對給定的 directed graph 計算 dist(1,5)+dist(2,5)+dist(3,5)+dist(4,5)+dist(6,5)

作答時要注意的地方

1. 第 6 題要指出哪些小題 Master method 不適用，並說明原因。
2. 第 6、7 題各 15 分，是 Part II 配分最高的兩題。
3. 第 8 題給的是填空形式的 pseudo-code。
4. 第 9(3) 題不可使用計算機。

準備方向

• Master theorem 不適用的情況：109 Part II 第 5 題、110 第 6 題。
• 一般 TSP 與 metric TSP 的近似性（110 第 7(4) 題）。
• shuffle 字串的 DP，與 LCS 同屬二維 DP：110 第 8 題、109 Part II 第 4 題。
• Floyd-Warshall 的遞推式：110 第 9 題、114 第 18 題。
• Huffman code（110 第 2 題）。
• MST：107 第 2 題、110 第 5 題。