108 中央資工所軟體考點分析

題型與配分

科目全名「資料結構與演算法」（所別：資工類），全卷 5 頁、100 分，禁用計算器。

三種題型都有，是中央軟體少見的混合卷。

單選題（1–5）考點

• 第 1 題｜給定 Quick sort 第一次 partition 後的結果 12 9 1 13 19 24 22 20，反推 pivot 可能是哪個
• 第 2 題｜依序插入 9, 4, 8, 7, 20, 15, 14, 3, 10 建 BST，判斷層數、節點所在層、父節點關係
• 第 3 題｜由 level-order 序列判斷哪一個是合法的 max-heap
• 第 4、5 題｜遞迴產生所有排列的 perm 函式，兩個空格（B1 交換、B2 遞迴呼叫的參數）

複選題（6–12）考點

• 第 6 題｜Hash table 10 buckets × 每 bucket 2 slots，h(n)=n%10，依序插入 11 個數字，分別用 linear probing 與 quadratic probing，算「滿的 bucket」內數字總和。要完整模擬整個插入過程
• 第 7 題｜Hash function 性質 — 除數取 7^r、open addressing 與 chaining 的平均存取次數比較、dynamic hashing
• 第 8、9 題｜Floyd–Warshall，5 個頂點含負權邊，要算出 d⁽²⁾、d⁽³⁾、d⁽⁴⁾、d⁽⁵⁾ 的多個項
• 第 10–12 題｜自訂概念 progress path（路徑上每一步到終點的最短距離嚴格遞減）。給定 8 個頂點的無向圖，要 (10) 算最短距離 δ (11) 判斷哪些是 progress path (12) 數出 progress path 的數量

問答題（1–4）考點

• 第 1 題（17%）｜(a) 用題目給的 MERGE 副程式寫出完整的 merge sort 演算法，題目明確要求包含 input 與 output（9%）(b) 用 big-O 分析時間複雜度（8%）
• 第 2 題（8%）｜Matrix-chain multiplication — 寫出 m[i, j] 的遞迴式
• 第 3 題（7%）｜Floyd–Warshall（題中稱 AllPairCost）的三個空格
• 第 4 題（8%）｜Max heap 的 adjust 與 heapsort 兩個空格

這份考卷的難點

1. 第 10–12 題的 progress path 是臨時定義的概念，課本上找不到。要先看懂定義、算出所有最短距離，才能判斷與計數 —— 三題連動，第一題算錯後面全錯，而且複選題有倒扣。
2. 第 6 題的 hash 模擬很花時間，每個 bucket 有 2 個 slot 增加了複雜度，還要分 linear 與 quadratic 兩種做一遍。
3. 問答題第 1 題明確要求寫出 input/output，只寫演算法主體會被扣分。

準備建議

• Floyd–Warshall 的 d^(k) 定義（只用編號 ≤ k 的中繼點）必須真的理解，這份考卷考了 10 分，且和 107 年考法幾乎相同
• Hash 的 linear probing 與 quadratic probing 要能穩定手動模擬，特別是「一個 bucket 有多個 slot」的變形
• Merge sort、matrix-chain multiplication 的遞迴式要能默寫