110 交大資工所考古題解答｜軟體考點分析

30 題全為多選題，全對才給分、答錯不倒扣，配分分四個級距。涵蓋 NP、Huffman、red-black tree、B-tree、max flow、radix sort、disjoint set 等章節。

題型與配分

全卷 8 頁、30 題、100 分，不可使用計算機，用答案卡作答。

計分規則：全卷 30 題為多選題，每題有一個以上的正確選項。各題填答必須完全符合正確選項，答錯沒有倒扣，若有任一選項不符則該題 0 分。

配分分四個級距：

理論與 NP（1–2，各 4 分）

第 1 題｜L₁ 可多項式時間 reduction 到 L₂，四個推論何者正確
第 2 題｜假設 NP ≠ P，哪些問題是 NP-hard：longest simple path、最小 cycle、最大 cycle、negative cycle 偵測、有 negative cycle 時的 shortest simple path

樹與編碼（3–4）

資料結構與複雜度（5–8）

第 5 題（4 分）｜各種結構的操作複雜度：有序 linked list 的插入、queue 逐一移除 n 個元素、deque 的加入與尋找、doubly linked list 給定節點的刪除
第 6 題（4 分）｜自訂的 O(f) > O(g) 關係下比較五組函數，包含 3^(log₄n) 與 n³、⌊n/2⌋^⌊n/2⌋ 與 n!
第 7 題（4 分）｜哪些圖演算法使用 DP：Kruskal、Dijkstra、LCS、Floyd-Warshall
第 8 題（4 分）｜BST 的 preorder 為 6, 2, 4, 3, 5, 9, 7, 8，判斷祖先關係、兄弟節點、postorder 的先後、兩棵子樹高度是否相同

排序（9、10、18）

第 9 題（3.5 分）｜LSD radix sort 逐趟追蹤：312, 256, 19, 713, 44, 608, 210, 909 在第一趟、第二趟後的位置
第 10 題（3.5 分）｜哪些排序用 divide and conquer（Quick、Heap、Selection、Insertion、Merge）
第 18 題（3.5 分）｜divide and conquer 排序的四種變體各自的複雜度，其中 (D) 把 n 個數切成 n/lg n 組、每組 lg n 個、各自 heap-sort 再合併，問是否為 O(n log log n)

max flow（11、17、28）

第 11 題（3.5 分）｜max cut 是否有多項式演算法、min cut 是否有、是否可能有多個不同的 max flow、不同的 min cut 是否可能有不同容量
第 17 題（3.5 分）｜給一張標了 x/y（流/容量）的 flow network，判斷四組 a、b、c、d 的值哪些是合法的流
第 28 題（2.5 分）｜給 flow network 與其 residual network，反推 a、b、c、d 的關係式

recurrence 與漸進（12、22、29）

第 12 題（3.5 分）｜五條 recurrence 的解，包含 T(n)=2T(n/2)+n/log n 與 T(n)=2T(n/2)+n/log²n
第 22 題（3 分）｜f=O(g) 能否推出 log f = O(log g)、反向是否成立、能否推出 2^f = O(2^g)、⌈log n⌉! 與 n 的關係
第 29 題（2.5 分）｜迭代對數 lg\n：f⁽ⁱ⁾ 的定義、lg\16 的值

圖論（13、15、23）

第 13 題（3.5 分）｜shortest path 距離 δ(v) 的性質：是否對每個 v 都存在邊使 δ(v)=δ(u)+l(e)、這些邊的集合是否構成 spanning tree、是否構成 MST、triangle inequality 的方向
第 15 題（3.5 分）｜給一張 weighted graph，x 為 MST 總權重、y 為次佳 spanning tree 總權重，判斷 x、y 的關係式
第 23 題（3 分）｜有向 weighted graph 的 topological sort 與 Dijkstra：加一條權重 0 的邊後 topological sort 是否仍合法、Dijkstra 找到的路徑是否改變

樹結構（14、16、19、25）

第 14 題（3.5 分）｜minimum degree 3 的 B-tree，依序插入 5, 6, 4, 2, 1, 7, 8, 10 後，再分別插入 9 或 3 時樹高是否改變、哪些 key 在同一節點
第 16 題（3.5 分）｜BST 的節點關係推論
第 19 題（3 分）｜Max-Heap 的 array 表示：線性時間建 heap 的結果、刪除最大值後的 array、插入 10 後的 array、兩個 max-heap 能否線性時間合併
第 25 題（2.5 分）｜空 red-black tree 依序插入 5, 3, 8, 2 後的性質（外部節點數、紅節點數、旋轉次數）

其他（20、21、24、26、27、30）

第 20 題（3 分）｜C++ STL 的 vector：是否連續記憶體、push_back 的擴張策略、amortized cost 能否達 Θ(n)、單次 push_back 是否可能 Θ(n)
第 21 題（3 分）｜把 Huffman 推廣到三元編碼（符號 0、1、2），選出不可能的編碼樹。與第 3 題成對出現
第 24 題（3 分）｜h(key)=key mod 5，插入 1, 2, 4, 6, 8：chaining 與 linear probing 下 key 8 的位置，以及「load factor < 0.5 是否就不碰撞」
第 26 題（2.5 分）｜一串 Make-Set 與 Union 操作後，有幾個集合、哪些 Find-Set 回傳同一節點
第 27 題（2.5 分）｜活動選擇問題的五種 greedy 策略，哪些能得到最佳解
第 30 題（2.5 分）｜median of medians：改成分 3 組或分 7 組是否仍線性、heap sort 解法的複雜度，以及「因為 heap sort 下界是 Ω(n log n) 所以此問題下界也是」這個推論

NP 與 reduction（110 第 1、2 題）。
Huffman 樹的結構（110 第 3、21 題）。
recurrence，包含 Master theorem 以外的形式（110 第 12 題）。
活動選擇問題的 greedy 策略（110 第 27 題）、median of medians 的分組大小（110 第 30 題，112 第 18 題也考）。
max flow（110 第 11、17、28 題）、red-black tree、B-tree、disjoint set、radix sort、C++ vector amortized。