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

題型與配分

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

複選題（1–10）考點

• 第 1 題｜Infix 與 postfix 轉換：轉換 a(b+c/d)(e−f)+g 與 a(b+c/d)(e−f) 時 stack 內最多同時有幾個 token、(a+b−c)*(d−e) 的 postfix、一個 postfix 運算式的 infix 形式
• 第 2 題｜n 個元素的 AVL tree 哪些敘述為假：刪除的時間複雜度、插入的時間複雜度、高度 h 與 Fibonacci 數的下界 n ≥ F(h+1) − 1、左右子樹高度差
• 第 3 題｜Weight-biased leftist tree（WBLT），w(x) 為以 x 為根的子樹的內部節點數：最右路徑長度與 log₂(w(x)+1) 的關係、子樹高度與 log₂(w(x)+1) 的關係、合併兩棵 WBLT 的時間、max WBLT 的定義
• 第 4 題｜遞迴：遞迴版本是否一定比非遞迴版本慢且耗空間、函式 F1（偶數回傳 x/2，奇數回傳 F1(F1(3x+1))）是否對所有正整數都會終止、F2 求 F2(21,12)（F2(y, x mod y)）、F3(5) 的遞迴求值（F3(x−2) + F3(x−3)）
• 第 5 題｜二維整數 array arr[5][5]，哪些 pointer 寫法等於 arr[3][2]
• 第 6 題｜給定 PUSH 與 POP 序列，哪些關於容器是 stack、queue 或兩者皆非的敘述為假
• 第 7 題｜把 {23, 12, 34, 46, 28, 11, 6, 7, 0, 33, 30, 45} 插入大小 17 的 hash table，h(k,i) = (k + i) mod 17，刪除 46 之後哪些 key 必須改變位置
• 第 8 題｜QuickSort 的 T(n) recurrence：2T(n/2) + cn、4T(n/4) + cn、T(n−1) + cn、2T(n−2) + cn，哪些對應 worst case 或 best case 的敘述為假
• 第 9 題｜反轉 linked list 的 reverse pseudo-code（pointer P、C、N），兩個空格 (1)、(2)，以及各敘述的描述是否正確
• 第 10 題｜AOE network 以 adjacency list 表示（欄位 count、end、vertex、dur、link）：critical path 的總長度、路徑 0,1,4,6,8 與 0,2,4,7,8 是否為 critical path、事件 4 的最晚發生時間

問答題（1–2）考點

• 第 1 題（25%）｜NP-completeness，題目先給出四個定義與 Cook's Theorem：(A) 15%：已知 SAT ∝ B、B ∝ C、C ∝ D 且 D ∈ NP，證明 D 是 NP-complete；(B) 5%：判斷「一個 NPC 問題可以多項式歸約到任何 NPC 問題」是真是假，理由錯誤不給分；(C) 5%：判斷「若某 NPC 問題可用確定性演算法在多項式時間解出，則所有 NP 問題也可以」是真是假，理由錯誤不給分
• 第 2 題（25%）｜加權 undirected graph（邊權非負）的 shortest path：(A) 12%：給出求 x 到 y shortest path 的有效率演算法並分析複雜度；(B) 13%：給定圖 G、起點 s 與大小 |V| 的 array d[]，聲稱 d[v] 是 s 到 v 的 shortest path 長度，設計時間為 O(|V|+|E|) 的演算法檢查這個聲稱是否正確，並分析複雜度

作答時要注意的地方

1. 複選題全對才給分，答錯一個選項扣 1.5 分。
2. 問答第 1(B)(C) 題明訂理由錯誤不給分。
3. 問答第 2(B) 題要求時間為 O(|V|+|E|)。
4. 第 3 題的 WBLT 以 w(x) 定義，不是以高度定義。

準備方向

• Infix、postfix 轉換（110 第 1 題），109、111、112、113、114、115 也有運算式轉換。
• AVL tree（110 第 2 題），111 第 3 題同型。
• Leftist tree（110 第 3 題為 WBLT），111 第 4 題為 HBLT，112 第 3 題也有。
• 遞迴函式的終止性與求值（110 第 4 題），111 第 5 題同型。
• 2D array pointer（110 第 5 題），111 第 6 題同型。
• Stack 與 queue 的判斷（110 第 6 題），111 第 7 題同型。
• Hash table 刪除後的搬移（110 第 7 題），111 第 8 題同型，107、108、109、112、113、114、115 也有 hash。
• QuickSort 的 recurrence（110 第 8 題），107、108、109、111、112、113、115 也有排序。
• Linked list 反轉（110 第 9 題），111 第 9 題同型，112、113 也有 linked list。
• AOE network 與 critical path（110 第 10 題），111 第 10 題同型，115 第 11 題也有。
• NP-completeness 的證明（110 問答第 1 題），106、107、109、111、112、114、115 也有 NP 理論。
• shortest path 演算法與驗證（110 問答第 2 題），106、107、108、112、113、114、115 也有 shortest path。