113 中央資工所考古題解答｜軟體考點分析

20 題、100 分全部是複選題，全對才給分、答錯倒扣 1 分。範圍涵蓋圖論、排序、樹、recurrence、DP、Huffman 與 hash。

題型與配分

全卷 5 頁、20 題複選、每題 5 分、共 100 分，禁用計算器。

全部答對才給分，答錯倒扣 1 分。沒有問答題。

圖論（1、6、11、12、15）

第 1 題｜給定 6 個頂點的 weighted graph，哪一個不可能是 Kruskal 演算法的加邊順序
第 6 題｜5 個頂點 {0,1,2,3,4} 的 complete graph，邊權重以矩陣 W 給定，問 spanning tree 的最小成本，選項附帶頂點 0 是否為 root 或 leaf 的條件
第 11、12 題｜含 negative-weight edge 的 10 個頂點 directed graph，single-source shortest path：第 11 題問 d[0,1] 到 d[0,5]，第 12 題問 d[0,6]、d[0,7]、d[0,8]，以及從節點 0 到節點 4、節點 9 各有幾條 shortest path
第 15 題｜MST 的性質判斷：|E| ≥ |V| − 1 時唯一最重邊、含有唯一最重邊的 cycle、唯一最輕邊是否在每個 MST 中、含有唯一最輕邊的 cycle、兩點間 shortest path 是否必屬於某個 MST。題目聲明不要假設邊權重相異

排序（2、16）

第 2 題｜Quick sort、Heap sort、Merge sort、Insertion sort、Radix sort 五種：insertion sort 對已排序或幾乎排序 array 的表現、radix sort 排序 ASCII 字串、是否都是 comparison sort、是否都是 stable
第 16 題｜關於排序演算法哪些敘述不正確：merge 與 quick 的設計原理、大部分已排序時 quick sort 是否最佳、quick、merge、heap 的最壞時間、merge 與 heap 的最壞與期望時間、有沒有低於 O(n log n) 的排序

樹與資料結構（3、5、8、9、10）

第 3 題｜在 n 個元素的 BST 中插入的時間複雜度 T(n)：2T(n/2) + O(1)、T(n−1) + O(1)、T(n/2) + O(1)、T(n−2) + O(1) 哪些只對 best case 或 worst case 成立
第 5 題｜LASTPOST、LASTIN、LASTPRE（postorder、inorder、preorder traversal 的最後一個節點）在 complete binary tree 與 full binary tree 中的相等關係
第 8 題｜一段反轉 doubly linked list 的 C 程式（交換每個節點的 prev 與 next），給定四組 linked list，問執行後的結果
第 9 題｜反轉 singly linked list 的 reverse 函式，迴圈結束後缺少最後一行，問該補哪一個敘述
第 10 題｜判斷一段 binary tree 遞迴函式 f 在計算什麼：空樹回傳 0、葉節點回傳 0、其他回傳 1 + f(left) + f(right)，選項有葉節點數、內部節點數、高度、直徑

演算法分析（13、14）

第 13 題｜f(n) 與 g(n) 為漸近正函數：f(n) = O(g(n)) 是否蘊含 lg f(n) = O(lg g(n))、f(n) × f(n) = O(n²)、2^f(n) = O(2ⁿ)，f(n) + o(f(n)) = Θ(f(n))、f(n) = Θ(f(n/2))
第 14 題｜五個 recurrence 同時求解（n ≤ 2 時為常數）：t(n) = n + Σ[t(k) + t(n−k)]、f(n) = 2f(n/4) + √n、g(n) = g(n/2) + √n、h(n) = 5h(n/2) + (n lg n)²、a(n) = a(n−1) + n^k lg n

演算法範式（4、18、19、20）

第 4 題｜DP：optimal substructure、overlapping subproblems、循序求解、使用 memoization 時的時間複雜度
第 18 題｜Matrix-chain multiplication：Q、R、S、T 四個矩陣，dimension 依序為 13×12、12×30、30×15、15×18，問是否為 divide-and-conquer、第一個相乘的一對、最後相乘的矩陣、最佳順序是否不唯一、最少 scalar multiplication 次數是否為 11250
第 19 題｜Huffman coding：字母 a、b、c、d、e 的頻率為 25、20、10、20、50，問是否為 greedy、e 的碼長、a 與 c 的碼長是否相同、字串 "cad" 的碼長、最佳前綴碼是否不唯一
第 20 題｜DP 與 divide-and-conquer 的差異在哪些方面：子問題是否重疊、問題的劃分、子問題的合併、base case 的解法、遞迴深度

hash 與運算式（7、17）

第 7 題｜Infix 轉 postfix：四個運算式各自給出一個 postfix，判斷哪些正確
第 17 題｜Hash table 大小 7、H(k) = k % 7、pseudo random probing 的 i = (i + 5) % 7，依序插入 15, 11, 25, 16, 9, 8, 12，判斷各 key 的最終位置，以及是否有 key 放不進去

Kruskal 的加邊順序與 MST 的性質（113 第 1、6、15 題），107 第 3 題與 113 第 15 題同型，109、111、114、115 也有 MST。
排序演算法的比較（113 第 2、16 題），107、108、109、110、111、112、114、115 也有排序。
BST 與樹的 traversal（113 第 3、5 題），106、109、114、115 也有樹的 traversal 與重建。
Linked list 的反轉（113 第 8、9 題），110、111、112 也有 linked list。
single-source shortest path（113 第 11、12 題），107 第 18 題也有 Bellman–Ford。
asymptotic notation 與 recurrence 求解（113 第 13、14 題），114 第 18 題、115 第 6 題也有 asymptotic notation。
Matrix-chain multiplication（113 第 18 題），108 問答第 2 題也有。
Huffman coding（113 第 19 題）。
運算式轉換（113 第 7 題），109、110、111、112、114、115 也有。
Hash 的 pseudo random probing（113 第 17 題）。