115 成大資工所軟體考點分析

題型與配分

編號 139，系所「電機資訊學院－資訊聯招」，考試科目：程式設計，考試日期 115 年 2 月 3 日第 2 節，全卷 11 頁、24 題、100 分，不可使用計算機。

成大十年來第一次出現倒扣：單選題答錯扣 1 分、是非題答錯扣 1 分，合計 34 分的區塊有倒扣。是非題只有兩個選項卻要倒扣 1 分，等於猜測的期望值是 0.5 分 —— 仍略有利，但不確定時要謹慎。

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 重建二元樹，列出 level 3 由左至右的 key
• 第 4 題（4%）｜n = 15 時，AVL 樹與紅黑樹各自可能的最大高度（根為 level 1）

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

• 題組 A（第 1–4 題）｜防火牆的 Bloom filter：給一支用兩個雜湊函式與位元遮罩做快速預檢的 C 程式：
• 第 1 題｜precheck 的本質是什麼（機率性成員測試，可能有偽陽性）
• 第 2 題｜給定輸入的程式輸出
• 第 3 題｜最小的 x 使 precheck 通過但 exact_check 失敗（即最小的偽陽性）
• 第 4 題｜黑名單改成 {10, 14, 22} 時要改哪些部分
• 題組 B（第 5–8 題）｜校園光纖的 MST：給一支完整的 C 程式（Kruskal + 路徑壓縮的 union-find）：
• 第 5 題｜這支程式在做什麼（排序所有邊後掃描，只在連接兩個不同群組時加入）
• 第 6 題｜給定輸入的輸出（總成本與邊數）
• 第 7 題｜生成的骨幹中哪些頂點是 articulation point
• 第 8 題｜要多印出連通元件數時，哪一段修改是正確的（答案是數 f1(i) == i 的根節點個數）

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

• 第 9 題｜支援 insert／delete／find 與 predecessor／successor 查詢：紅黑樹、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 為何適合磁碟、紅黑樹為何不適合、B+ tree 的葉節點串接與範圍查詢

Part II 演算法

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

• 第 12 題｜T(n) = 50n² + 200n log n + 10⁶，宣稱 T(n) = O(n³) 是否數學上正確（真 —— O 是上界，不必緊）
• 第 13 題｜停機問題是 NP-Hard，是否因此也是 NP-Complete（假 —— NPC 還要求屬於 NP，停機問題不可判定）
• 第 14 題｜NP 的定義是否為「給定候選解可在多項式時間驗證」（真）
• 第 15 題｜0/1 knapsack 能否用「單位價值最高優先」的貪婪解到最佳（假）
• 第 16 題｜要證明 3-SAT 是 NPC，是否該從 3-SAT 歸約到 Robot-Path-Planning（假 —— 方向反了，要從已知 NPC 歸約到新問題）

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

• 第 1 題｜MRI 立體資料的遞迴分析：MRI_Voxel_Process(n) 呼叫 n 次 Surface_Scan(n)，再遞迴 8 個 n/2 的子問題。(1) 3% Surface_Scan 的複雜度（Θ(n)，內層迴圈是常數 100 次） (2) 3% 寫出 T(n) = 8T(n/2) + Θ(n²) (3) 4% 求整體緊界（Θ(n³)），並寫出計算過程
• 第 2 題｜微影機排程（House Robber 型 DP）：13 個班次各有產值，不能連續兩班生產。(1) 4% 求最大總值與選中的班次 (2) 4% 強制包含 S7 時的最大總值 (3) 2% 冷卻期改成兩班時，寫出完整的遞迴式 f[i] = max(f[i−1], v_i + f[i−3])
• 第 3 題｜衛星路由（含負權邊）：4 個節點、邊權含 −5，且要求「需要時能有效率地取得任兩點最短路徑」。(1) 4% 選出最適合的演算法（Floyd-Warshall）並說明為什麼 Dijkstra 不行（有負權邊） (2) 2% 寫出初始的 4×4 距離矩陣 M (3) 4% D 到 B 的最短成本與路徑、以及演算法的時間複雜度 Θ(n³)
• 第 4 題｜Smart Lasso 影像去背：像素格子上每格有能量成本，只能上下左右移動。(1) 4% 追蹤貪婪法（每步選最低成本鄰居）的路徑與總成本 (2) 4% 追蹤保證最佳解的方法（Dijkstra／DP）的路徑與總成本 (3) 2% priority queue 用 unsorted array vs binary min-heap 時 Extract-Min 的複雜度

這份考卷的難點

1. 倒扣首次出現在成大。 單選題 24 分（扣 1）與是非題 10 分（扣 1）合計 34 分，策略要調整。
2. 題組 A、B 各要完整讀懂一支 C 程式，而且四個小題連動 —— 題組 B 的程式有 qsort 比較函式、路徑壓縮的 find、union by size，讀不懂就四題全失。
3. 第 3 題（Part II）的「為什麼 Dijkstra 不行」要明確指出負權邊，而不只是說「用 Floyd-Warshall」。
4. 第 4 題的兩次路徑追蹤要照題目給的方向優先序（右 > 下 > 上 > 左）逐格追蹤，很容易算錯。

準備建議

• 115 年全面情境化：防火牆、光纖、MRI、微影機、影像去背 —— 但背後都是標準題（Bloom filter、Kruskal、遞迴式、House Robber DP、Dijkstra）。先剝掉情境再解題
• 成大首次倒扣，單選與是非要留意；但是非題只有兩選項、倒扣 1 分，期望值仍為正
• 「貪婪 vs 最佳解」的對照（115 第 4 題）是近年熱門考法，要能說出貪婪在什麼情況會失敗
• 磁碟索引與 fan-out（115 第 11 題）是 B-tree／B+ tree 的實務動機，不只是結構規則
• digital search tree、compressed binary trie、SMMH 這些冷門結構成大連四年都考（111–115），Horowitz 的資料結構課本要讀