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

題型與配分

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

複選題（1–6）考點

• 第 1 題｜給定一張圖，哪些是從節點 1 出發的 DFS traversal 序列
• 第 2 題｜給定 Min-Heap 的 array（索引 0–10 的內容為 6, 8, 15, 10, 17, 16, 23, 20, 22, 18, 40），在 array 末端插入 9 並重建，9 最後落在 A[0]、A[1]、A[2]、A[5] 的哪一個
• 第 3 題｜給定一棵 binary tree 做成 threaded binary tree，節點 3 的 thread 指向哪些節點
• 第 4 題｜哪些序列是給定 directed graph 的 topological sorting
• 第 5 題｜Quick sort 第一次 partition 的結果為 3 9 1 14 20 24 22 21，問 pivot 是 14、20 還是兩者
• 第 6 題｜Hash table 11 個 bucket、每個 bucket 2 個 slot，h(n) = n % 11，用 linear probing 依序插入 6 16 22 44 53 24 45 7 74 4 109 78 12，問滿的 bucket 內數字總和

是非題（7–11）考點

• 第 7 題｜postfix 運算式 bcd+*/aefg*+* 是否合法
• 第 8 題｜directed graph 的 adjacency matrix，row sum 是 in-degree 還是 out-degree
• 第 9 題｜任意圖 G(V, E) 只要 |E| = |V| − 1，是否必為 binary tree
• 第 10 題｜DFS 能否用 stack 實作
• 第 11 題｜V(G′) ⊆ V(G) 且 E(G′) ⊆ E(G) 的 subgraph G′ 是否就是 G 的 connected component

申論題（1–4）考點

• 第 1 題（10%）｜兩個 stack（stack 0 與 stack 1）共用同一個 array mem[MEMORY_SIZE]，只要兩個 stack 的總項目數小於 MEMORY_SIZE − 1，PUSH(item, i) 就能把項目放進 stack i。要求完成 PUSH 演算法
• 第 2 題（5%）｜產生集合所有 permutation 的 perm 演算法，填兩個空格
• 第 3 題（25%）｜MST：(a) 15% 描述一個有效率的演算法，並分析時間複雜度、說明使用的資料結構 (b) 10% 設計演算法求次佳 spanning tree 的成本（可能與最佳相同），題目以 3 個頂點的兩個例子說明
• 第 4 題（25%）｜n 個實數的集合 S 與實數 M，判斷 S 中是否有 3 個數的和恰為 M（窮舉要 O(n³)，題目說不可接受）：(a) 10% 設計更有效率的演算法並分析複雜度 (b) 5% 推廣成 k 個數的和為 M，證明這個問題是 NP-Complete (c) 10% 當 M 夠小時，設計 O(nkM) 時間的演算法

作答時要注意的地方

1. 複選題全對才給分，答錯倒扣 1.25 分。
2. 是非題答錯倒扣 0.5 分。
3. 第 3(a) 要同時分析時間複雜度並說明資料結構。
4. 第 4 題三小題連動，從 3-SUM 到 k-SUM 的 NP-Complete 證明，再到 M 有界時的演算法。

準備方向

• DFS 序列、topological sort、圖的 adjacency matrix（109 第 1、4、8 題），106 第 6 題、112 問答第 1 題、115 第 11 題也有圖的 traversal。
• Min-Heap 的插入重建（109 第 2 題），106、107、108、112、114、115 也有 heap。
• Threaded binary tree（109 第 3 題），106 第 3 題也有樹的 array 表示。
• Quick sort 第一趟 partition（109 第 5 題），與 108 第 1 題同型。
• Hash table 一個 bucket 多個 slot（109 第 6 題），與 108 第 6 題同型。
• Postfix 運算式（109 第 7 題），110、111、112、113、114、115 也有運算式轉換。
• 兩個 stack 共用 array（109 申論第 1 題）。
• permutation 的遞迴產生（109 申論第 2 題），與 108 第 4、5 題是同一支程式。
• MST 與次佳 spanning tree（109 申論第 3 題），107、111、113、114、115 也有 MST。
• 3-SUM、k-SUM 與 subset sum 型 DP（109 申論第 4 題），106 第 8 題、107 第 19 題也有 subset sum。