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

題型與配分

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

全部答對才給分，答錯倒扣一分。

沒有任何問答題，全卷靠 20 題複選決定成績。這代表單題權重 5%，而且沒有部分分數 —— 一題五個選項只要判斷錯一個，這題就歸零並倒扣。

逐題考點

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

• 第 1 題｜給定 6 個頂點的加權圖，判斷哪個不可能是 Kruskal 的加邊順序
• 第 6 題｜完全圖以權重矩陣 W 給定，求 spanning tree 的最小成本（並附帶「頂點 0 是 root／leaf」的條件）
• 第 11、12 題｜含負權邊的有向圖單源最短路徑，要算出 d[0,j] 的多個值，以及最短路徑的條數
• 第 15 題｜MST 性質判斷 —— 唯一最重邊、cycle 中的最重／最輕邊、最短路徑是否必屬於某個 MST。（與 107 年第 3 題同型）

排序（2、16）

• 第 2 題｜五種排序演算法的比較 — insertion sort 的最佳情境、radix sort 適用性、是否皆為比較式、是否皆為 stable
• 第 16 題｜排序演算法的錯誤敘述 — merge 與 quick 的設計原理、quick sort 在接近有序時的表現、worst-case 複雜度

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

• 第 3 題｜BST 插入的時間複雜度遞迴式，分辨哪個對應 best case、哪個對應 worst case
• 第 5 題｜LASTPOST／LASTIN／LASTPRE（後序／中序／前序走訪的最後一個節點）在 complete binary tree 與 full binary tree 中的關係
• 第 8 題｜一段反轉 doubly linked list 的 C 程式，判斷執行後的結果
• 第 9 題｜反轉 singly linked list 的函式缺少最後一行，要補上（考 *head_ref = prev;）
• 第 10 題｜判斷一段二元樹遞迴函式在計算什麼（葉節點數／內部節點數／高度／直徑）

演算法分析（13、14）

• 第 13 題｜漸進符號的推導性質 — f(n)=O(g(n)) 是否推得出 lg f(n)=O(lg g(n))、f(n)×f(n)=O(n²)、2^f(n)=O(2ⁿ) 等
• 第 14 題｜五個遞迴式同時求解，含 t(n)=n+Σ[t(k)+t(n−k)]（Catalan 型）、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 題｜動態規劃的性質（optimal substructure、overlapping subproblems）
• 第 18 題｜Matrix-chain multiplication — 4 個矩陣 13×12、12×30、30×15、15×18，求最少純量乘法次數與相乘順序
• 第 19 題｜Huffman coding — 給定字母頻率，判斷編碼長度、是否為 greedy、最佳前綴碼是否唯一
• 第 20 題｜DP 與 divide-and-conquer 的差異何在

雜湊與運算式（7、17）

• 第 7 題｜Infix 轉 postfix
• 第 17 題｜Hash table size 7、H(k)=k%7、pseudo random probing i=(i+5)%7，判斷各 key 的最終位置

這份考卷的難點

1. 沒有問答題等於沒有部分分數。 20 題全對才給分，任何一個選項判斷失誤就是 −1 分而非 0 分。
2. 第 14 題五個遞迴式一次考完，其中 t(n) 是 Catalan 型（不能用 Master theorem）、h(n) 落在 Master theorem 的 case 1 要看 n^log₂5 與 (n lg n)² 的大小關係。這題極耗時。
3. 第 11、12 題含負權邊，不能用 Dijkstra，要手動跑 Bellman-Ford，還要數最短路徑的條數。
4. 第 18、19 題都要實際算完整張 DP 表／建完 Huffman 樹才能判斷選項，很花時間。

準備建議

• 遞迴式求解必須超越 Master theorem —— Catalan 型、遞迴樹法、變數變換都要會
• Matrix-chain multiplication 與 Huffman coding 的手算流程要練到快，這兩題在中央反覆出現
• linked list 的反轉（單向與雙向）在 110、111、113 都出現過，是必考題型
• 全複選加倒扣的形式下，時間分配比正確率更關鍵 —— 先把能秒判的題目做完，再回頭處理第 14、18、19 這種計算題