108 交大資工所軟體考點分析
交大改為全選擇題的第一年。16 個題組、38 小題，規則是「同一題組全對才給分、錯一小題整組零分」，是十年間最嚴苛的計分方式。
題型與配分
科目「資料結構與演算法（1101）」，系所班別資訊聯招，考試日期 108 年 2 月 13 日第 1 節，全卷 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 | Queue／stack 程式輸出 | 1 | 5 |
| 2 | Linked list pseudo-code 判讀 | 1 | 5 |
| 3 † | Heap 性質 | 1 | 5 |
| 4 | 二維陣列記憶體位址 | 1 | 5 |
| 5 | Max heap 刪除根節點 | 1 | 5 |
| 6 | MST（Kruskal／Prim） | 3 | 5 |
| 7 | AVL 插入 | 3 | 6 |
| 8 | B-tree（order 3）插入 | 3 | 6 |
| 9 | Dijkstra 程式追蹤 | 3 | 10 |
| 10 | Quicksort 變形的機率分析 | 3 | 6 |
| 11 † | 加括號最小化中間和 | 3 | 6 |
| 12 † | Scaling max flow | 3 | 6 |
| 13 † | Maximum adjacency ordering | 3 | 8 |
| 14 † | BFS tree 性質 | 3 | 6 |
| 15 | Knapsack 特例複雜度 | 3 | 8 |
| 16 † | Hamiltonian cycle 歸約 | 3 | 8 |
逐題考點
基礎程式與資料結構（1–5，各 5%）
- 第 1 題組｜
queue與stack各推入四個數後，輸出que.front()、que.back()、stk.top() - 第 2 題組｜給一段操作
prev／next指標的 pseudo-code，判斷它的功能是插入、刪除還是交換 - 第 3 題組（†）｜heap 的五個敘述哪些為真：heap sort 是否 O(n log n)、最壞情況是否快於 quick sort、陣列實作時節點 i 的右子節點是否在第 2i 個位置、max heap 的父節點是否小於子節點、樹高是否 O(log n)
- 第 4 題組｜
int x[5][5]，已知&x[0][0]與&x[0][1]的位址，推出&x[1][2]—— 考的是 row-major 記憶體配置 - 第 5 題組｜給一棵 binary max heap，移除根節點並重整後，陣列的第 4 個數字是多少
樹與圖（6–9）
- 第 6 題組（5%，3 小題）｜同一張圖問三件事：MST 的總成本、Kruskal 最後加入的邊權、從 F 出發的 Prim 最後加入的邊權
- 第 7 題組（6%，3 小題）｜依序插入 20, 30, 40, 50, 60, 70, 10, 5, 25, 45 到空 AVL 樹：最左節點的值、根節點的值、最後兩次旋轉的型態（LL／RR／LR／RL）
- 第 8 題組（6%，3 小題）｜同一組數字插入 order-3 的 B-tree：最右節點的數字總和、根節點的數字總和、共發生幾次節點分裂
- 第 9 題組（10%，3 小題）｜給一支完整的 C 程式（其實是 Dijkstra，START = 4、N = 8、用 1000 代表無限大），問陣列
d的最小值、最大值、以及程式的時間複雜度。這是配分最高的題組，且三小題全對才給 10 分
演算法分析（10–13）
- 第 10 題組（6%，3 小題）｜Quicksort 的變形：不斷重做隨機 partition 直到較大的一半不超過子陣列的 2/3。問平均複雜度、repeat 迴圈恰好執行一次的機率（答案 1/3）、以及平均執行次數（答案 3）
- 第 11 題組（†，6%，3 小題）｜n 個正數要加 n−1 對括號，最小化所有中間和的總和。給輸入 4, 4, 8, 5, 4, 3, 5，問最小總和 X 的
X mod 10、⌊X/10⌋，以及關於此問題的敘述何者正確。這其實是 Huffman／最佳二元合併樹 - 第 12 題組（†，6%，3 小題）｜Scaling max flow 演算法（K 從 2⌊lg C⌋ 開始逐次減半）：最小割的唯一性、演算法的執行時間、以及最大流與最小割的性質判斷
- 第 13 題組（†，8%，3 小題）｜Maximum adjacency ordering（Magic Order）：補完演算法第 5 行缺少的 key 更新式、判斷用陣列／binary heap／Fibonacci heap 實作各行的成本、以及整體攤銷複雜度。這是最小割演算法（Stoer-Wagner）的核心步驟，超出一般課本範圍
BFS、Knapsack 與歸約（14–16）
- 第 14 題組（†，6%，3 小題）｜BFS tree 的深度性質：若 (x,y) 是 G 的邊且 x 深度為 2，y 可能的深度有哪些；兩個深度都是 2 的節點，其最短路徑可能有幾條邊；根節點在 G 中度數為 5 時，在 T 中可能的度數
- 第 15 題組（8%，3 小題）｜Knapsack 在三種特例下的最佳已知複雜度：m = Θ(n2)、m = Θ(n2) 且所有 wi = 1、m = Θ(n2) 且 wi ∈ {1,2}
- 第 16 題組（†，8%，3 小題）｜給
HamC(G)當黑盒子，補完HamC3(G,x,y,z)演算法（判斷是否存在讓 x、y、z 連續出現的 Hamiltonian cycle）的三個空格。與 107 第 10 題、109 第 3 題是同一系列的歸約題
這份考卷的難點
- 題組全對制放大了一切錯誤。 第 9 題組（Dijkstra，10 分）要手動追蹤 8 個節點的完整鬆弛過程，三小題全對才有分；第 7、8 題組要各建一次 AVL 與 B-tree，也是全對才給分。
- † 題組是複選且必須選全。 第 11、12、13、14、16 五個題組（合計 34 分）都是這種計分，漏選一個正確選項就整組零分。
- 第 13 題組的 maximum adjacency ordering 屬於進階圖論演算法，一般資料結構課本不會教。
- 第 10 題組的機率分析要算出「pivot 落在中間 1/3 的機率」，需要一點推導而不是背誦。
準備建議
- 交大 108 起採題組全對制，策略上要「先確保會的題組全對」，而不是每個題組都填一點。不確定的題組本身沒有倒扣，但也拿不到分
- AVL 的四種旋轉、B-tree 的分裂規則要練到能穩定手繪，交大 106、108、109 連三年都考
- Dijkstra 的程式碼追蹤（108 第 9 題組）與 Johnson 演算法（107 第 7 題）顯示交大很愛把最短路徑以「看程式」的方式出題
- Huffman／最佳合併樹的變形（106 第 11 題、108 第 11 題組）連兩年出現，要能認出來
- 107、108、109 連三年的 Hamiltonian cycle／path 歸約題是同一位出題者的風格，建議三年一起練