108 中央資工所考古題詳解｜軟體考點分析

題型與配分

全卷 5 頁、100 分，禁用計算器，作答於答案卷（卡）。

單選題（1–5）考點

• 第 1 題｜給定 Quick sort 第一次 partition 後的結果 12 9 1 13 19 24 22 20，判斷 pivot 可能是 13、19 還是都不可能
• 第 2 題｜依序插入 9, 4, 8, 7, 20, 15, 14, 3, 10 建 BST（根在第 1 層）：層數、20 所在的層、7 與 10 是否同一個父節點、20 的左子樹節點數
• 第 3 題｜哪一個 level-order 序列是合法的 max-heap
• 第 4、5 題｜遞迴產生 list[i] 到 list[n] 所有 permutation 的 perm 函式，兩個空格：B1 為迴圈內第一個交換，B2 為遞迴呼叫

複選題（6–12）考點

• 第 6 題｜Hash table 10 個 bucket、每個 bucket 有 2 個 slot，h(n) = n % 10，依序插入 6 16 22 45 54 25 7 75 5 108。分別用 linear probing 與 quadratic probing，問「滿的 bucket」內數字總和，並比較兩者的平均 bucket 存取次數
• 第 7 題｜Hash function 的性質：除數取 7^r、open addressing 與 hash chaining 的平均 bucket 存取次數、chaining 時比較的 key、dynamic hashing 的 bucket 增減
• 第 8、9 題｜Floyd–Warshall，5 個頂點、9 條有向邊（含 negative-weight edge）：(1,4,−5)、(1,5,2)、(2,1,6)、(3,1,1)、(3,2,7)、(4,3,4)、(5,2,−4)、(5,3,3)、(5,4,8)。第 8 題問 d⁽²⁾、d⁽³⁾ 的各項，第 9 題問 d⁽⁴⁾、d⁽⁵⁾ 的各項
• 第 10–12 題｜自訂概念 progress path：無向 weighted graph 上，路徑 [v₁, …, v_k] 若對每個 i 都有 δ[v_i, v_k] > δ[v_i+1, v_k]（δ 為最短距離），就稱為 progress path。給一個 4 個頂點的例子，再給 8 個頂點 a 到 h 的圖。第 10 題問 δ 的各個值，第 11 題問哪些路徑是 progress path，第 12 題問各起點到 h 的 progress path 共有幾條

問答題（1–4）考點

• 第 1 題（17%）｜題目給 MERGE(A, p, q, r) 的 pseudo-code。(a) 9% 用 MERGE 寫出完整的 divide-and-conquer merge sort 演算法，須包含 input 與 output 的說明 (b) 8% 用 big-O 分析時間複雜度
• 第 2 題（8%）｜Matrix-chain multiplication：n 個矩陣 A₁…A_n，A_i 的 dimension 為 p_i−1 × p_i，m[i,j] 為計算 A_i…A_j 的最少 scalar multiplication 次數，寫出 m[i,j] 的 recurrence
• 第 3 題（7%）｜Floyd–Warshall（題中稱 AllPairCost，邊距離非負）的三個空格：(a) 4% 迴圈內的判斷式 B3 與更新式 B4 (b) 3% 初始化的 B5
• 第 4 題（8%）｜Max heap 的 adjust 與 heapsort：(a) 4% 空格 B6 (b) 4% 空格 B7

作答時要注意的地方

1. 單選與複選各自扣到該大題 0 分為止。
2. 第 10–12 題三題連動，progress path 是題目臨時定義的概念。
3. 第 6 題每個 bucket 有 2 個 slot，要分 linear 與 quadratic 兩種做。
4. 問答題第 1 題明確要求寫出 input 與 output。

準備方向

• Quick sort 第一趟 partition（108 第 1 題），109 第 5 題同型，107、110、113、115 也有 quick sort。
• permutation 的遞迴產生（108 第 4、5 題），109 申論第 2 題是同一支程式。
• Heap 的判斷與 adjust、heapsort（108 第 3 題與問答第 4 題），107 第 8–10 題相同。
• Hash table 的 linear 與 quadratic probing、一個 bucket 多個 slot（108 第 6 題），109 第 6 題同型。
• Floyd–Warshall（108 第 8、9 題與問答第 3 題），107、112、114、115 也有。
• shortest path 自訂概念（108 第 10–12 題）。
• Merge sort 與 matrix-chain multiplication 的 recurrence（108 問答第 1、2 題），113 第 18 題也有 matrix-chain。