106 交大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 3 頁、17 題、100 分，不可使用計算機。

全部是手寫題，題數多，多數單題 5 分。

逐題考點

• 第 1 題（5%）｜給 pattern abcabcacab，依題目給的 failure function 定義寫出 f(4)…f(8)
• 第 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 與 postorder ADFECB，畫出 binary tree
• 第 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 tree 插入 15、60 後畫結果 (c) 6% 依序插入 1, 3, 5, 2, 4, 6 到空 red-black tree，紅節點畫圓、黑節點畫方
• 第 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
• 第 10 題（10%）｜證明 Quicksort 的平均時間複雜度是 O(n log n)
• 第 11 題（10%）｜設計 greedy 演算法產生最佳 2-way merge tree（輸入 m 條長度 n_i 的已排序 linked list）
• 第 12 題（3%）｜三個 NP 敘述判斷對錯：任一 NPC 問題可多項式時間解則 NP = P、NP 問題是否必存在 NP 演算法、2-SAT 是否因 SAT 為 NPC 而也是 NPC
• 第 13 題（2%）｜T(n) = aT(n/c) + bn，求 a = 3、c = 2 時的 Θ 表示式
• 第 14 題（10%）｜證明 MST 的 cycle property：邊權互異時，任一 cycle 上權重最大的邊必不屬於 MST
• 第 15 題（5%）｜圖的邊被塗成紅或藍，設計最快的演算法求出藍邊數量最少的 spanning tree
• 第 16 題（5%）｜從頂點 A 執行 Dijkstra，依序列出離開 priority queue 的頂點與各自的最短距離（平手時字母小的優先）
• 第 17 題（5%）｜給一張 residual graph，找出最短 augmenting path，並畫出推進 max flow 量後的新 residual graph

作答時要注意的地方

1. 第 10、14 題是證明題，各 10 分，合計 20 分。
2. 第 1 題的 failure function 依題目給的定義計算。
3. 第 6 題兩段字母對應到同一組索引，要逐字計算位址。
4. 17 題共 100 分，含兩題各 10 分的證明（第 10、14 題）與多張手繪樹。

準備方向

• AVL、red-black tree、B-tree、heap、hash、MST、Dijkstra、max flow，106 年各有一題。
• Quicksort 平均複雜度證明與 MST 的 cycle property 證明（106 第 10、14 題）。
• Fibonacci heap 的操作複雜度，106 第 9 題、107 第 7(a) 題、108 第 13 題組都考。
• 2-SAT 不會因為 SAT 是 NP-complete 就也是 NP-complete（106 第 12 題的第三個敘述）。