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

題型與配分

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

Part I 資料結構

一、問答題（1–4，14 分）：

• 第 1 題（3%）｜7 個 6-bit key 插入 digital search tree，列出搜尋 001111 時經過的 key
• 第 2 題（4%）｜同一組 key 建 compressed binary trie，用 BFS 列出各分支節點的 bitNumber
• 第 3 題（3%）｜由 postorder 與 inorder 重建 binary tree，列出 level 3 由左至右的 key
• 第 4 題（4%）｜n = 15 時，AVL tree 與 red-black tree 各自可能的最大高度（根為 level 1）

二、單選題（題組 A、B，各 4 小題）：

• 題組 A（第 1–4 題）｜防火牆的快速預檢（本質是 Bloom filter，卷面沒有寫出這個名稱）：給一支用兩個 hash function 與 bit mask 做快速預檢的 C 程式
• 題組 A 第 1 題｜precheck 的本質是什麼
• 題組 A 第 2 題｜給定輸入的程式輸出
• 題組 A 第 3 題｜最小的 x 使 precheck 通過但 exact_check 失敗
• 題組 A 第 4 題｜黑名單改成 {10, 14, 22} 時要改哪些部分
• 題組 B（第 5–8 題）｜校園光纖的 MST：給一支完整的 C 程式
• 題組 B 第 5 題｜這支程式在做什麼
• 題組 B 第 6 題｜給定輸入的輸出（總成本與邊數）
• 題組 B 第 7 題｜生成的骨幹中哪些頂點是 articulation point
• 題組 B 第 8 題｜要多印出 connected component 數時，哪一段修改是正確的

三、複選題（9–11，各 4 分）：

• 第 9 題｜支援 insert／delete／find 與 predecessor／successor 查詢：red-black tree、binary heap、B+ tree、AVL、hashing 各自的複雜度
• 第 10 題｜需要頻繁 meld、頻繁 delete-min、偶爾 find-max 的 priority queue：Fibonacci heap、leftist heap、SMMH（symmetric min-max heap）的適用性
• 第 11 題｜磁碟索引與 fan-out：B-tree／B+ tree 為何適合磁碟、red-black tree 為何不適合、B+ tree 的葉節點串接與範圍查詢

Part II 演算法

一、是非題（12–16，各 2 分，答錯倒扣 1 分）：

• 第 12 題｜T(n) = 50n² + 200n log n + 10⁶，宣稱 T(n) = O(n³) 是否數學上正確
• 第 13 題｜halting problem 是 NP-Hard，是否因此也是 NP-Complete
• 第 14 題｜NP 的定義是否為「給定候選解可在多項式時間驗證」
• 第 15 題｜0/1 knapsack 能否用「單位價值最高優先」的 greedy 解到最佳
• 第 16 題｜要證明 3-SAT 是 NPC，是否該從 3-SAT reduction 到 Robot-Path-Planning

二、問答題（1–4，各 10 分）：

• 第 1 題｜MRI 立體資料的遞迴分析：MRI_Voxel_Process(n) 呼叫 n 次 Surface_Scan(n)，再遞迴 8 個 n/2 的子問題。(1) 3% Surface_Scan 的複雜度 (2) 3% 寫出 recurrence (3) 4% 求整體緊界，並寫出計算過程
• 第 2 題｜微影機 scheduling：13 個班次各有產值，不能連續兩班生產。(1) 4% 求最大總值與選中的班次 (2) 4% 強制包含 S7 時的最大總值 (3) 2% 冷卻期改成兩班時，寫出完整的 recurrence
• 第 3 題｜衛星路由（含 negative-weight edge）：4 個節點、邊權含 −5，且要求需要時能有效率地取得任兩點 shortest path。(1) 4% 選出最適合的演算法並說明為什麼其他演算法不行 (2) 2% 寫出初始的 4×4 距離矩陣 M (3) 4% D 到 B 的最短成本與路徑，以及演算法的時間複雜度
• 第 4 題｜Smart Lasso 影像去背：像素格子上每格有能量成本，只能上下左右移動，方向優先序為右、下、上、左。(1) 4% 追蹤 greedy 法（每步選最低成本鄰居）的路徑與總成本 (2) 4% 追蹤保證最佳解的方法的路徑與總成本 (3) 2% priority queue 用 unsorted array 與 binary min-heap 時 Extract-Min 的複雜度

作答時要注意的地方

1. 單選題（24 分）與是非題（10 分）答錯倒扣 1 分，合計 34 分。
2. 題組 A、B 各給一支 C 程式，四個小題都依據同一支程式。
3. Part II 第 3 題要求說明為什麼其他演算法不行。
4. Part II 第 4 題的路徑追蹤依題目給的方向優先序進行。
5. Part I 與 Part II 的題號各自從 1 編起。

準備方向

• Bloom filter：109 第 2 題、111 第 4 題、113 第 5 題、115 題組 A。
• digital search tree 與 trie 家族：112 第 10 題、115 第 1、2 題。
• SMMH（symmetric min-max heap）：113 第 2 題、115 第 10 題。
• greedy 法與最佳解的對照（115 Part II 第 4 題）。
• 磁碟索引與 fan-out：B-tree、B+ tree（115 第 11 題）。
• recurrence 與 Master theorem（115 Part II 第 1 題）。
• 含 negative-weight edge 的 all-pairs shortest path（115 Part II 第 3 題）。
• NP-hard、NP-complete 與 reduction 的觀念（115 Part II 第 13、14、16 題）。
• 單位價值 greedy 與 knapsack：108 第 6(a) 題、115 Part II 第 15 題。