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

題型與配分

全卷 9 頁、20 題、100 分，禁用計算器。

113、114 年是 20 題全複選，115 年前 10 題改成逐選項計分。

多選題（1–10）考點

• 第 1 題｜Quicksort：最壞情況的時間、以 median 為 pivot 是否保證 O(n log n)、in-place Quicksort 是否 stable、randomized Quicksort 的期望時間、平均額外空間
• 第 2 題｜Amortized analysis：是否為不假設機率分布的平均成本上界、amortized cost O(1) 時每個操作是否都是 O(1)、potential method、accounting method、與 average-case analysis 是否等價
• 第 3 題｜LCS 的 DP（dp[i][j] 為 X[1..i] 與 Y[1..j] 的 LCS 長度）：字元相等與不相等時的 recurrence、時間複雜度 O(n × m)、DP 表是否可只用兩列、是否可用 greedy 解
• 第 4 題｜Greedy：greedy-choice property 與 optimal substructure、fractional 與 0/1 knapsack、Dijkstra 遇 negative-weight edge、DP 能解的問題是否都能用 greedy 解、Prim 與 Kruskal
• 第 5 題｜計算複雜度：NP-complete 問題最佳化版本的多項式演算法與決策版本、NP-hard 且屬於 coNP 的結論、是否存在補集也是 NP-complete 的問題、reduction 的方向、NP-complete 問題有 PTAS 的結論
• 第 6 題｜asymptotic notation：O、Ω、Θ、o 之間的互推，n = o(n log n)，n² + 200000002n 與 Θ(n)
• 第 7 題｜排序下界：comparison-based 排序的 Ω(n log n)、是否適用於 counting sort 與 radix sort、decision-tree model、n! 種 permutation 的 information-theoretic 論證、Ω(n) 下界的涵義
• 第 8 題｜邊權可正、零、負的 shortest path：Dijkstra 遇 negative-weight edge、Bellman–Ford 偵測 negative cycle、起點可達 negative cycle 時的 shortest path、Floyd–Warshall 偵測 negative cycle、全點對 shortest path O(V × E)
• 第 9 題｜Branch-and-bound 與 A：用 bound 剪枝、A 是否為 branch-and-bound 的特例、heuristic 不高估時的最佳性、A* 的最壞時間與窮舉比較、branch-and-bound 的最壞時間
• 第 10 題｜Median of medians（prune-and-search）：給出 Select(A, k) 的六個步驟（每五個一組找 median、遞迴找 median 的 median m、依 m 分成 L、E、R）。問至少有多少元素小於等於 pivot、T(n) = T(n/5) + T(7n/10) + O(n) 的複雜度、改成每三個一組是否仍為線性、剪枝正確性、median 問題與第 k 小問題的關係

複選題（11–20）考點

• 第 11 題｜給一張帶權 directed graph（Start 到 Finish）：當作 AOV network 時 ACEGFBD 與 ABECGFD 是否為合法的 topological order，當作 AOE network 時，每個活動一天或某條邊三天的情形下，哪條路徑是 critical path
• 第 12 題｜11 格 hash table（h(k) = k % 11），給定插入 8 個項目後的最終表格，問哪些輸入序列在 quadratic probing 或 linear probing 下成立
• 第 13 題｜給一張帶權 undirected graph：Kruskal 與 Prim（從不同起點開始）加邊的順序，指定的邊是第幾條加入、MST 是否為 binary tree、頂點 A 與 B 之間是否有邊
• 第 14 題｜對 [9, 7, 15, 6, 11, 4, 22, 119]：Quick sort 以第一個元素或第二個元素為 pivot 時第一趟的結果，LSD radix sort 第二趟、第三趟結束後指定位置的元素
• 第 15 題｜Red-black tree，初始 level order 為 52, 33, 80, 100：節點 33 的顏色、插入 65 與 55 後節點 100 的顏色、插入 65、55、60 後節點 60 的顏色與 level order
• 第 16 題｜Infix、postfix、prefix 互轉：(a+b)/c−d)+e 的 postfix、b+a*c/d 的 postfix、一個 postfix 的 infix 與 prefix 形式
• 第 17 題｜同一段程式碼依序 push(T)、pop、push(L)、push(O)、push(V)、pop、push(E)、push(N)、pop、push(C)、push(U)、pop，分別套用 standard stack、standard queue、min heap、max heap，問容器內元素的排列
• 第 18 題｜由 inorder ILOVENCU 與 postorder LIVNUCEO 重建 binary tree，問 level-order 的第五、第六個字母、樹高、C 是否為葉節點
• 第 19 題｜課程 scheduling：n 門線上課程，課程 i 要連續上 duration_i 天、最晚在 lastDay_i 前完成，從第 1 天開始、同時只能上一門，求最多能上幾門。問時間複雜度 O(n log n)、依 lastDay_i − duration_i 最小者優先、是否適用 min-heap 的 greedy、依最早 lastDay 優先
• 第 20 題｜結構相異的 n 節點 binary tree（n = 3 時有 5 棵）：決定個數的空間複雜度 O(n)、時間複雜度 O(n²)、n = 7 與 n = 9 時的個數

作答時要注意的地方

1. 前 10 題每個選項單獨計分，後 10 題全對才給分，兩區都倒扣到該區 0 分為止。
2. 第 12、13、14、15 題給的是具體的 hash 表、weighted graph、數列與 red-black tree。
3. 第 15 題的 red-black tree 要連續插入三個節點。
4. 第 20 題的選項給了 n = 7、n = 9 的個數。

準備方向

• Quicksort 與 quick sort 第一趟 partition（115 第 1、14 題），107、108、109、110、112、113 也有。
• LSD radix sort（115 第 14 題），112 第 4 題、114 第 3 題也有。
• DP 與 LCS（115 第 3 題），114 第 12、19 題也有，106、107、108、111、113 也有 DP。
• Greedy（115 第 4、19 題），114 第 8–10 題也有 greedy 加 heap。
• NP 理論（115 第 5 題），106、107、109、110、111、112、114 也有。
• asymptotic notation（115 第 6 題），113、114 也有。
• shortest path 與 Floyd–Warshall（115 第 8 題），107、108、112、113、114 也有。
• Branch-and-bound 與 A（115 第 9 題），114 第 20 題也有 A 與 branch and bound。
• recurrence 求解與 prune-and-search（115 第 10 題），107、110、113 也有 recurrence 求解。
• AOV／AOE network（115 第 11 題），110、111 也有 AOE network。
• Hash 的反推插入順序（115 第 12 題），114 第 1 題同型。
• MST（115 第 13 題），107、109、111、113、114 也有。
• Red-black tree（115 第 15 題），114 第 6 題同型。
• 運算式轉換（115 第 16 題），114 第 2 題同型。
• 由 inorder 與 postorder 重建 binary tree（115 第 18 題），114 第 4 題同型。