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

題型與配分

全卷 6 頁、100 分。

與 110 年同型的題目

複選題（1–10）考點

• 第 1 題｜Infix 與 postfix 轉換：stack 內最多同時有幾個 token、(a+b−c)*(d−e) 的 postfix、一個 postfix 運算式的 infix 形式
• 第 2 題｜演算法範式：dynamic programming 是否避免遞迴爆炸、重疊的遞迴呼叫是否導致指數演算法、greedy 的局部最佳決策、divide and conquer 的遞迴屬於哪一部分
• 第 3 題｜n 個元素的 AVL tree 哪些敘述為假：刪除與插入後重新平衡旋轉的時間複雜度、高度 h 與 Fibonacci 數 n ≤ F(h+2) − 1、左右子樹高度差
• 第 4 題｜Height-biased leftist tree（HBLT），w(x) 為以 x 為根的子樹的內部節點數：最左路徑與最右路徑的長度限制、子樹高度、刪除最小值與 meld 的時間
• 第 5 題｜三個遞迴函式 F1（偶數回傳 x/2，奇數回傳 F1(F1(3x+2))）、F2（Euclidean algorithm，F2(21,12)）、F3（F3(x−2) + F3(x−3)，F3(5)）哪些敘述為假
• 第 6 題｜2D array arr[5][5] 哪些 pointer 寫法等於 arr[2][3]
• 第 7 題｜裝置 A 依序傳送 m1 到 m5 經過黑盒子到裝置 B，B 依不同順序收到時，黑盒子是 queue、stack、max heap 或兩者皆非
• 第 8 題｜把 {23, 12, 34, 46, 28, 11, 6, 7, 0, 33, 13, 45} 插入大小 17 的 hash table，h(k,i) = (h(k) + i) mod 17，刪除 46 之後哪些 key 必須改變位置
• 第 9 題｜反轉 linked list 的 reverse pseudo-code，三個空格 (1)、(2)、(3)，以及各敘述是否正確
• 第 10 題｜AOE network 以 adjacency list 表示：critical path 的總長度、路徑 0,1,4,6,8 是否為 critical path、count 欄位應為哪些值、事件 4 的最晚發生時間

多選題（11–12）考點

• 第 11 題｜排序演算法的時間複雜度與空間複雜度：insertion sort、merge sort、quick sort、heap sort、bubble sort 的 worst、average、best case 與空間複雜度
• 第 12 題｜NP 理論：是否已證明 NPC 問題沒有多項式時間的 deterministic 演算法、NPC 問題的下界為多項式階時的結論、NP-hard 問題 reduction 到 X 時 X 的類別、NP-hard 且屬於 NP 是否為 NPC、nondeterministic 多項式演算法與 NP

問答題（1–3）考點

• 第 1 題（15%）｜題目給出 Prim's MST 的 pseudo-code（T 初始為空、X = {w}、迴圈直到 |T| = n − 1、選權重最小且 u ∈ X、v ∈ V − X 的邊）。(1) 9% 依完全相同的格式寫出 Kruskal's MST 演算法 (2) 6% 分析 Kruskal 的最壞情況時間複雜度。題目明寫必須嚴格遵循 Prim 的格式，否則扣分
• 第 2 題（13%）｜健行投宿：起點在 0 公里，沿路 n 家旅館在 a₁ < a₂ < … < a_n 公里處，必須停在最後一家，一天走 x 公里的懲罰是 (20 − x)²，求總懲罰最小的投宿序列。若用 DP，要寫出 recurrence、說明符號意義、給初始值並分析時間複雜度
• 第 3 題（12%）｜n 個變數 x₁…x_n 與 m 個形如 x_i = x_j 或 x_i ≠ x_j 的限制，判斷能否同時滿足（例如 x₁ = x₂、x₂ = x₃、x₃ = x₄、x₁ ≠ x₄ 無法滿足）。要說明使用的資料結構並分析時間複雜度

作答時要注意的地方

1. 第一區複選題全對才給分，第二區多選題逐選項計分。
2. 問答第 1 題要求嚴格遵循 Prim 的格式。
3. 問答第 2 題若用 DP，要寫出 recurrence、符號意義、初始值和時間複雜度四項。
4. 問答第 3 題要說明使用的資料結構。

準備方向

• 110 與 111 的複選題九題同型，兩年一起練。
• 排序演算法的時間與空間複雜度（111 第 11 題），107、108、109、110、112、113、114、115 也有排序。
• NP 理論（111 第 12 題），106、107、109、110、112、114、115 也有。
• Prim 與 Kruskal（111 問答第 1 題），107、109、113、114、115 也有 MST。
• DP 的 recurrence（111 問答第 2 題），106、107、108、113、114、115 也有 DP。
• 等式與不等式限制的可滿足性（111 問答第 3 題）。