112 中央資工所軟體考點分析｜國立中央大學

全卷僅 3 頁卻有 50 分問答題，且問答只有兩大題。第二題要求模仿給定格式手寫非確定性演算法，是十年來最特殊的考法。

題型與配分

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

區段	題號	配分	倒扣
一、複選題	1–10	50%（每題 5 分）	答錯 1 題倒扣 1 分，扣到該大題 0 分為止
二、問答題	1–2	50%	題目要求用深色筆書寫

頁數最少，但問答題只有兩大題就佔 50 分，單題份量極重。

第 1 題｜哪一個不屬於 open addressing 的溢位處理（linear probing／dynamic hashing／rehashing／quadratic probing）
第 2 題｜Quick sort 第一趟，分別以第一個元素和第二個元素為 pivot，要選出兩個對應的結果
第 3 題｜Leftist tree（題目直接給出 dist 定義）— 最右葉路徑長度、合併方式、delete min 複雜度、最左葉路徑與節點數下界
第 4 題｜LSD Radix sort — 是否為非比較式排序、第一／二／三趟結束後第六個元素是什麼
第 5 題｜Min-Heap 的插入／搜尋／刪除複雜度，以及逐一插入後的 level-order
第 6 題｜Stack 的 4 push + 4 pop，哪些輸出序列可能出現
第 7 題｜圖的三種表示法（adjacency matrix／list／multilist）在 m ≫ n 時的空間複雜度
第 8 題｜最短路徑問題的複雜度：單源單點、單源多點、全點對
第 9 題｜一維陣列與 singly／circular linked list 的插入刪除複雜度比較
第 10 題｜Infix、postfix、prefix 三種表示法互轉

第 1 題（25%）｜source vertex（所有頂點都能從它到達）三小題層層加難：
(a) 8%：給定頂點 v，設計 O(|V|+|E|) 演算法判斷 v 是否為 source vertex，需說明資料結構
(b) 8%：在 DAG 中判斷是否存在 source vertex，不能用「對每個頂點跑一次 (a)」的 O(|V|²+|V||E|) 做法
(c) 9%：在可能有環的一般有向圖中做同樣的事，同樣要更快
第 2 題（25%）｜非確定性演算法與 NP：
(a) 18%：題目先給出 ND 演算法的定義與 ND-SAT 的完整格式，要求依完全相同的格式寫出解 exact cover decision problem (ECDP) 的多項式時間 ND 演算法，以此證明 ECDP ∈ NP。題目明列必須包含 input 描述、output 描述、choosing phase、checking phase、return 敘述，缺一項就扣分
(b) 7%：用 big-O 分析該 ND 演算法確實是多項式時間

第 1(c) 題是全卷最難的一題。 DAG 可以用入度為 0 的頂點下手，但一般有向圖有環，必須先做強連通分量縮點（Kosaraju／Tarjan）再判斷 —— 這超出多數人的準備範圍。
第 2(a) 題的 18 分全押在「格式」上。 它不是問你 ECDP 是什麼，而是要你模仿 ND-SAT 的寫法。理解 choosing phase 與 checking phase 的分工是關鍵。
問答題只有兩大題，沒有分散風險的餘地 —— 有一題不會就直接失去 25 分。