106 交大資工所軟體考點分析
全卷 17 題、3 頁，全部手寫且題數多、單題配分小。從 failure function、B-tree 到 Quicksort 平均複雜度證明，幾乎把課本掃過一遍。
題型與配分
科目「資料結構與演算法（1101）」，系所班別資訊聯招，考試日期 106 年 2 月 10 日第 1 節，全卷 3 頁、17 題、100 分，不可使用計算機。
全部是手寫題，但題數多、單題配分小（多數 5 分），是一份「廣度優先」的考卷 —— 不會在單一主題上挖很深，但涵蓋面極廣。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | KMP failure function | 5 |
| 2 | 前序／後序運算式 | 5 |
| 3 | Linked list 程式追蹤 | 5 |
| 4 | Min heap 定義與操作 | 5 |
| 5 | 由中序＋後序重建二元樹 | 5 |
| 6 | Hash（linear probing／chaining） | 5 |
| 7 | AVL 與紅黑樹 | 10 |
| 8 | B-tree | 6 |
| 9 | Fibonacci heap 複雜度 | 4 |
| 10 | Quicksort 平均複雜度證明 | 10 |
| 11 | 最佳 2-way merge tree 貪婪法 | 10 |
| 12 | NP 理論是非題 | 3 |
| 13 | 遞迴式求 Θ | 2 |
| 14 | MST cycle property 證明 | 10 |
| 15 | 紅藍邊生成樹演算法 | 5 |
| 16 | Dijkstra 逐步執行 | 5 |
| 17 | 殘餘圖與增廣路徑 | 5 |
逐題考點
- 第 1 題（5%）｜給 pattern
abcabcacab，依題目給的 failure function 定義寫出 f(4)…f(8)。注意這一年的定義多了pᵢ₊₁ ≠ pⱼ₊₁的條件，和標準 KMP 的 π 函數不完全一樣 - 第 2 題（5%）｜(a)
A+B*(C-D)↑E的 prefix (b) 同式的 postfix (c) 求 prefix 運算式*3-6+22的值 - 第 3 題（5%）｜追蹤一支對 linked list 做條件式氣泡排序的 C++ 程式（只在
q->value % 2 == 0時才交換），寫出最終輸出 - 第 4 題（5%）｜(a) 寫出 min heap 的定義 (b) 依序插入 18, 10, 4, 8, 2, 15, 6, 9 後再刪除兩次，畫出結果
- 第 5 題（5%）｜給 inorder
ABDCFE與 postorderADFECB，畫出二元樹 - 第 6 題（5%）｜13 格 hash table 存英文月份縮寫，以首字母決定位址（A–M 對應 0–12、N–Z 也對應 0–12）。(a) linear probing 下 MAR、AUG、DEC 的索引 (b) chaining 的最大鏈長 (c) 哪些槽達到最大鏈長
- 第 7 題（10%）｜(a)(b) 各 2% 在給定 AVL 樹插入 15、60 後畫結果 (c) 6% 依序插入 1, 3, 5, 2, 4, 6 到空紅黑樹，紅節點畫圓、黑節點畫方
- 第 8 題（6%）｜(a) 1% order 6 的 B-tree 三層最多可容納幾個項目（直接寫答案） (b) 5% 在 order-3 的 B-tree 依序插入 2, 4, 6，畫出結果
- 第 9 題（4%）｜Fibonacci heap 當 min priority queue 時，Insert／Extract-Min／Decrease-Key／Union 四個操作是否為 Θ(1)，各答 yes/no。Extract-Min 是唯一的否
- 第 10 題（10%）｜證明 Quicksort 的平均時間複雜度是 O(n log n)。要寫出期望值的遞迴式並求解
- 第 11 題（10%）｜設計貪婪演算法產生最佳 2-way merge tree（輸入 m 條長度 ni 的已排序串列）。這其實就是 Huffman 演算法
- 第 12 題（3%）｜三個 NP 敘述判斷對錯：任一 NPC 問題可多項式時間解則 NP = P、NP 問題是否必存在 NP 演算法、2-SAT 是否因 SAT 為 NPC 而也是 NPC（這是陷阱，2-SAT 在 P 中）
- 第 13 題（2%）｜T(n) = aT(n/c) + bn，求 a = 3、c = 2 時的 Θ 表示式
- 第 14 題（10%）｜證明 MST 的 cycle property：邊權互異時，任一環上權重最大的邊必不屬於 MST
- 第 15 題（5%）｜圖的邊被塗成紅或藍，設計最快的演算法求出藍邊數量最少的生成樹。關鍵是把紅邊優先排序後跑 Kruskal
- 第 16 題（5%）｜從頂點 A 執行 Dijkstra，依序列出離開 priority queue 的頂點與各自的最短距離（平手時字母小的優先）
- 第 17 題（5%）｜給一張殘餘圖，找出最短增廣路徑，並畫出推進最大流量後的新殘餘圖
這份考卷的難點
- 兩題純證明各 10 分（第 10、14 題），合計 20%。 Quicksort 平均複雜度與 MST cycle property 都是課本定理，必須能完整寫出論證而不是只講直覺。
- 第 6 題的 hash 設計很怪 —— A–M 和 N–Z 都對應到 0–12，所以
MAR和MAY會撞、JAN和JUN也會撞。要非常小心地逐字算。 - 第 1 題的 failure function 定義與標準 KMP 不同，照背標準 π 函數會全錯。
- 題數多、時間緊。 17 題要在一節課內寫完，且包含兩題證明與多張手繪樹。
準備建議
- 交大 106 是典型的「課本全面掃描」型考卷，AVL、紅黑樹、B-tree、heap、hash、MST、Dijkstra、max flow 一個都不能漏
- Quicksort 平均複雜度的證明與 MST 的 cut／cycle property 證明是交大反覆出現的主題，建議寫過一次完整版
- Fibonacci heap 的攤銷複雜度表（Insert O(1)、Decrease-Key O(1)、Extract-Min O(log n)、Union O(1)）要記熟，106、108、109 都考到
- 2-SAT 在 P 中、3-SAT 是 NPC —— 這個對比是常見陷阱