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

全卷 3 頁，複選 50 分加問答 50 分，問答只有兩大題。問答第 2 題要依 ND-SAT 的格式寫出 exact cover 的 nondeterministic 演算法。

題型與配分

全卷 3 頁、100 分。

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

第 1 題｜哪一個不屬於 open addressing 的 overflow 處理：linear probing、dynamic hashing、rehashing、quadratic probing
第 2 題｜對 [9, 7, 24, 6, 11, 4, 2, 19] 做 Quick sort，分別以第一個元素與第二個元素為 pivot，哪兩個是第一階段的結果
第 3 題｜Leftist tree（題目給出 dist 的定義）：最右葉路徑長度、合併方式、delete min 的時間、最左葉路徑有 x 個節點時的節點數下界
第 4 題｜輸入 L = [28, 203, 16, 30, 123, 521, 63, 528, 210, 216, 941, 45]，LSD radix sort 是否為非 comparison sort、第一趟、第二趟、第三趟結束後第六個元素是什麼
第 5 題｜Min-Heap：插入的時間複雜度、搜尋 max-Heap 的時間複雜度、依序插入 {42, 9, 23, 37, 4, 34, 2} 建 min-Heap 後的 level-order、delete min 的時間複雜度
第 6 題｜stack 做 4 次 push 與 4 次 pop，輸入序列 1234 的順序可能變成哪些輸出
第 7 題｜undirected graph n 個頂點、m 條邊（m ≫ n），用 adjacency matrix、adjacency list、adjacency multilist 表示時的空間複雜度，以及用 adjacency matrix 判斷 connectivity 的時間
第 8 題｜n 個節點 undirected graph 的 shortest path 問題：單源單點、單源多點、全點對的時間複雜度
第 9 題｜一維 array 與 singly linked list、circular singly linked list 的插入與刪除複雜度比較
第 10 題｜Infix、postfix、prefix 三種表示法互轉

第 1 題（25%）｜source vertex：directed graph 中，若所有頂點都可由 s 到達，s 就是 source vertex：(a) 8%：給定頂點 v，設計 O(|V|+|E|) 的演算法判斷 v 是否為 source vertex，並說明使用的資料結構；(b) 8%：在 DAG 中判斷是否存在 source vertex。對每個頂點跑 (a) 的做法要 O(|V|² + |V||E|)，題目要求更有效率的演算法並分析時間複雜度；(c) 9%：在可能有 cycle 的一般 directed graph 中判斷是否存在 source vertex，同樣要求比 O(|V|² + |V||E|) 更有效率並分析時間複雜度
第 2 題（25%）｜nondeterministic（ND）演算法與 NP：題目先給出 ND 演算法的定義（choosing phase 與 checking phase）與 ND-SAT 的完整格式：(a) 18%：依相同的格式寫出解 exact cover decision problem（ECDP）的多項式時間 ND 演算法，證明 ECDP ∈ NP。必須包含 input 描述、output 描述、choosing phase、checking phase 與 return 敘述，缺一項就扣分。ECDP：給全集 U = {u₁…u_m} 與 n 個 U 的非空子集合 S₁…S_n，判斷是否存在 S 的子集合使 U 中每個元素恰好出現在其中一個集合裡；(b) 7%：用 big-O 分析該 ND 演算法確實是多項式時間

Hash 的 overflow 處理（112 第 1 題），107、108、109、110、111、113、114、115 也有 hash。
Quick sort 與 LSD radix sort（112 第 2、4 題），114 第 3 題、115 第 14 題也有 radix sort。
Leftist tree（112 第 3 題），110、111 也有。
Min-Heap（112 第 5 題），106、107、108、109、114、115 也有 heap。
Stack 的輸出序列（112 第 6 題）。
圖的表示法與 shortest path 的複雜度（112 第 7、8 題），107、108、114、115 也有 Floyd–Warshall 與 shortest path。
Linked list 的插入刪除（112 第 9 題），110、111、113 也有 linked list。
運算式轉換（112 第 10 題），109、110、111、113、114、115 也有。
圖的可達性與 DFS／BFS 的應用（112 問答第 1 題），106、109、115 也有圖的 traversal。
nondeterministic 演算法與 NP（112 問答第 2 題），106、107、109、110、111、114、115 也有 NP 理論。