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

題型與配分

全卷 9 頁、16 個題組、38 小題、100 分，不可使用計算機，請使用答案卡作答。

計分規則：「For each problemset, if your answer is correct for all the questions in the problemset, you receive the full points; or otherwise ... you receive 0 point.」一個題組內只要錯一小題，整個題組就是零分。第 9 題組有 3 小題共 10 分、第 13 題組有 3 小題共 8 分。

題號旁有 † 記號的題組，每一小題可能有一個以上的答案，必須全部選到才算對。

交大軟體從這一年起改為全選擇題。

逐題考點

基礎程式與資料結構（1–5，各 5%）

• 第 1 題組｜queue 與 stack 各推入四個數後，輸出 que.front()、que.back()、stk.top()
• 第 2 題組｜給一段操作 prev、next pointer 的 pseudo-code，判斷它的功能是插入、刪除還是交換
• 第 3 題組（†）｜heap 的五個敘述哪些為真：heap sort 的複雜度、最壞情況與 quick sort 的比較、array 實作時節點 i 的右子節點位置、max heap 的父節點與子節點大小關係、樹高
• 第 4 題組｜int x[5][5]，已知 &x[0][0] 與 &x[0][1] 的位址，推出 &x[3][2]
• 第 5 題組｜給一棵 binary max heap，移除根節點並重整後，array 的第 4 個數字是多少

樹與圖（6–9）

• 第 6 題組（5%，3 小題）｜同一張圖問三件事：MST 的總成本、Kruskal 最後加入的邊權、從 F 出發的 Prim 最後加入的邊權
• 第 7 題組（6%，3 小題）｜依序插入 20, 30, 40, 50, 60, 70, 10, 5, 25, 45 到空 AVL tree：最左節點的值、根節點的值、最後兩次旋轉的型態（LL、RR、LR、RL）
• 第 8 題組（6%，3 小題）｜同一組數字插入 order-3 的 B-tree：最右節點的數字總和、根節點的數字總和、共發生幾次節點分裂
• 第 9 題組（10%，3 小題）｜給一支完整的 C 程式（START = 4、N = 8、用 1000 代表無限大），問 array d 的最小值、最大值，以及程式的時間複雜度。這是配分最高的題組，三小題全對才給 10 分

演算法分析（10–13）

• 第 10 題組（6%，3 小題）｜Quicksort 的變形：不斷重做隨機 partition 直到較大的一半不超過 subarray 的 2/3。問平均複雜度、repeat 迴圈恰好執行一次的機率，以及平均執行次數
• 第 11 題組（†，6%，3 小題）｜n 個正數要加 n−1 對括號，最小化所有中間和的總和。給輸入 4, 4, 8, 5, 4, 3, 5，問最小總和 X 的 X mod 10、⌊X/10⌋，以及關於此問題的敘述何者正確
• 第 12 題組（†，6%，3 小題）｜Scaling max flow 演算法（K 從 2^{⌊lg C⌋} 開始逐次減半）：min cut 的唯一性、演算法的執行時間，以及 max flow 與 min cut 的性質判斷
• 第 13 題組（†，8%，3 小題）｜Maximum adjacency ordering（卷上稱 Magic Order）：補完演算法第 5 行缺少的 key 更新式、判斷用 array、binary heap、Fibonacci heap 實作各行的成本，以及整體 amortized 複雜度

BFS、Knapsack 與 reduction（14–16）

• 第 14 題組（†，6%，3 小題）｜BFS tree 的深度性質：若 (x,y) 是 G 的邊且 x 深度為 2，y 可能的深度有哪些；兩個深度都是 2 的節點，其 shortest path 可能有幾條邊；根節點在 G 中 degree 為 5 時，在 T 中可能的 degree
• 第 15 題組（8%，3 小題）｜Knapsack 在三種特例下的最佳已知複雜度：m = Θ(n²)、m = Θ(n²) 且所有 w_i = 1、m = Θ(n²) 且 w_i ∈ {1,2}
• 第 16 題組（†，8%，3 小題）｜給 HamC(G) 當黑盒子，補完 HamC3(G,x,y,z) 演算法（判斷是否存在讓 x、y、z 連續出現的 Hamiltonian cycle）的三個空格。與 107 第 10 題、109 第 3 題組同系列

作答時要注意的地方

1. 一個題組錯任何一小題整組零分。第 9 題組 10 分、第 7、8 題組各 6 分，都是三小題全對才給分。
2. † 題組是複選，必須選全。† 題組共六個（3、11、12、13、14、16），其中第 11、12、13、14、16 五個題組合計 34 分。
3. 第 10 題組要自己推導機率與平均次數。

準備方向

• AVL 的旋轉與 B-tree 的分裂，106、108、109 三年都考（107 年只考 red-black tree）。
• Dijkstra 的程式碼追蹤（108 第 9 題組）與 Johnson 演算法（107 第 7 題）。
• 最佳合併與加括號最小化：106 第 11 題是順序不拘的 greedy 合併，108 第 11 題組的數字順序固定，只能相鄰合併，要用 DP。
• Hamiltonian cycle、path 的 reduction：107、108、109 三年都有。
• Scaling max flow、maximum adjacency ordering、k-coloring 的複雜度（108、109 的進階題組）。