交大資工所軟體考古題十年大統整（106–115）
題型演變
| 年度 | 結構 | 選擇題 | 手寫 | 頁數 |
|---|---|---|---|---|
| 106 | 手寫 17 題 | 0% | 100% | 3 |
| 107 | 手寫 10 題 | 0% | 100% | 5 |
| 108 | 16 題組、38 小題 | 100% | 0% | 9 |
| 109 | 15 題組、36 小題 | 100% | 0% | 7 |
| 110 | 30 題多選 | 100% | 0% | 8 |
| 111 | 40 題多選 | 100% | 0% | 12 |
| 112 | 選擇 16＋手寫 10 | 50% | 50% | 9 |
| 113 | 選擇 8 題組＋手寫 4 | 50% | 50% | 9 |
| 114 | 選擇 14 題組＋手寫 7 | 51% | 49% | 7 |
| 115 | 單選 8＋簡答 3＋除錯 3＋手寫 3 | 24% | 76% | 9 |
115 年是十年來結構變動最大的一次：新增「程式碼除錯題」25 分，並把手寫比重拉到 76%。
計分規則逐年對照
| 年度 | 計分方式 | 該不該猜 |
|---|---|---|
| 106 | 全手寫，無倒扣 | — |
| 107 | 全手寫，第 10 題漸進較慢不給部分分數 | — |
| 108 | 題組全對才給分，錯一小題整組 0 分 | 全填，但重點是「確保會的題組零失誤」 |
| 109 | 同上 | 同上 |
| 110 | 多選，全對才給分、答錯不倒扣 | 全填 |
| 111 | 同上（40 題每題 2.5 分） | 全填 |
| 112 | 多選須全選到，無倒扣 | 全填 |
| 113 | 題組全對才計分，無倒扣 | 全填 |
| 114 | 同上 | 全填 |
| 115 | 單選答錯倒扣 1 分；非選擇題可答 PASS 得 1 分 | 單選要有把握；不會的手寫題寫 PASS |
結論：交大十年只有 115 年有倒扣，但「全對才給分」貫穿了八年。 準備方向不是「多做幾題」，而是「把會的題目做到零失誤」。
主題出現年度一覽
| 主題 | 出現年度 |
|---|---|
| MST（Kruskal／Prim／cut property／次佳生成樹） | 106、107、108、109、110、111、112、113、114、115 |
| 平衡樹（AVL／紅黑樹／B-tree／B+-tree） | 106、107、108、109、110、111、112、113、114、115 |
| Max flow／最小割／匹配 | 106、107、108、109、110、111、112、113、114 |
| Hash（linear／quadratic／double hashing） | 106、107、110、111、112、113 |
| 最短路徑（Dijkstra／Bellman-Ford／Floyd／Johnson） | 106、107、108、109、111、112、113、114、115 |
| 程式碼追蹤／填空 | 106、107、108、109、111、112、113、114、115（除錯） |
| 複雜度與遞迴式 | 106、107、108、110、111、112、114 |
| Heap（建堆、插入刪除、heapsort） | 106、108、109、110、111、112、114、115 |
| NP 理論與歸約 | 106、107、108、109、110、111、115 |
| DP（LIS、knapsack、區間切段、雙峰子序列） | 108、110、111、112、113、114 |
| Stack／queue／linked list 實作 | 106、107、108、111、112、113、115 |
| Disjoint set | 109、110 |
| Huffman／最佳合併樹 | 106、108、110 |
| Median of medians | 110、112 |
| 拓撲排序 | 110、115 |
| 攤銷分析 | 110、112 |
| 2-SAT | 106、115 |
| 計算幾何（凸多邊形） | 113 |
交大最鮮明的三個特色
1. 題組全對制
這是交大和其他學校最大的差異。108、109、113、114 四年明文寫著：
「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.」
一個題組動輒 6–13 分，錯一小題全數歸零。 108 年第 9 題組（Dijkstra 程式追蹤）10 分、109 年第 3 題組（Hamiltonian 歸約）13 分，都是三到四小題全對才給。
策略上，交大的考卷不該「每題都猜一點」，而是要挑會的題組做到完全正確。
2. 給程式碼，問它是什麼
交大十年幾乎每年都有這類題目，而且越來越進階：
| 年度 | 題目 | 其實是 |
|---|---|---|
| 106 第 3 題 | 對 linked list 做條件式交換 | 帶條件的氣泡排序 |
| 107 第 5、6 題 | 兩支遞迴函式 | 鏡射二元樹／反轉串列 |
| 108 第 9 題組 | 8×8 矩陣與雙層迴圈 | Dijkstra |
| 111 第 5 題 | 一段 pseudo-code | Dijkstra |
| 112 第 9 題 | 兩個指標掃描 | 合併排序的 merge 步驟 |
| 113 第 2 題組 | 遞迴排序函式 | Quicksort（Hoare partition） |
| 113 第 6 題組 | 兩支數字處理函式 | 求最小加數使數字和 ≤ target |
| 114 第 14 題 | foo1 / foo2 / foo3 | Bellman-Ford／Dijkstra／Floyd-Warshall |
| 115 第 12–14 題 | 三支有 bug 的程式 | 找出 bug 並修正 |
這類題目背演算法名字沒有用，必須能逐行讀懂程式。
3. Hamiltonian 歸約三連發
107、108、109 連續三年考同一系列的題目 —— 給你一個 HamP(G) 或 HamC(G) 當黑盒子，要你在指定的複雜度內用它解一個變形問題：
- 107 第 10 題（15%）｜由 HamP 建構 HamEx（路徑端點不能是 x），並證明正確性
- 108 第 16 題組（8%）｜補完 HamC3（x、y、z 三點連續）的三個空格
- 109 第 3 題組（13%）｜補完 HamP2x3（從 a1/a2 出發、停在 z1/z2/z3）的四個空格
這三題建議一起練，做法都是「加幾個輔助節點並接上適當的邊」。
必守的五個主題
- MST 與平衡樹 —— 十年全中。 Kruskal／Prim 的加入順序、AVL 的四種旋轉、紅黑樹的著色與節點數界、B-tree 的分裂與 minimum degree，每年都考，而且經常是題組全對制
- Max flow 的建模 —— 十年考九年。二分圖匹配（106）、雙處理器排程的最小割（109）、邊／點互斥路徑（114）都是同一套工具
- 最短路徑的三支演算法 —— 要能從程式碼認出 Dijkstra／Bellman-Ford／Floyd-Warshall（114 第 14 題），也要能手動追蹤（108 第 9 題組、115 第 1–3 題）
- 程式碼閱讀能力 —— 見上表。這是交大和其他學校最大的差別，需要實際寫過程式，不能只看講義
- Median of medians 的分組大小 —— 110 第 30 題、112 第 18 題連兩年考「為什麼是 5、能不能改成 3 或 7」
給 116 年考生的策略
- 優先練 112–115，這四年都是「選擇 50＋手寫 50」（115 年手寫更重）；108–111 的全選擇題可以拿來練判斷精確度
- 題組全對制下，寧可少答也不要半猜。 把時間花在確認每個選項，而不是多掃幾題
- 115 年新增的程式碼除錯題很可能延續，建議在紙上練習找 bug：
free()的順序、索引從 0 或 1、(cur-1)/2vscur/2、變數打錯（rightChild(1)vsrightChild(i)） - 115 年的 PASS 規則如果延續，記得「不會就寫 PASS 拿 1 分，不要硬掰」
- 交大有重複前一年題目的習慣（111 第 6 題與 110 第 7 題一字不差、113 與 112 的殘餘網路圖相同），練考古題時相鄰兩年建議一起看
- 科目代號 110–112 年是
1101、113 年起改為8101，系所班別一直是「資訊聯招」
本頁的題型、配分、計分規則均直接取自各年度試卷標示；主題出現年度為逐題比對後的整理。若發現有誤，歡迎來信指正。