成大資工所軟體考古題十年大統整（106–115）
題型演變
| 年度 | 結構 | 題數 | 頁數 | 倒扣 |
|---|---|---|---|---|
| 106 | 全手寫 | 9 | 2 | 無 |
| 107 | 全手寫（十題各 10 分） | 10 | 3 | 無 |
| 108 | 全手寫 | 8 | 2 | 無 |
| 109 | 全手寫 | 8 | 2 | 無 |
| 110 | 全手寫 | 9 | 3 | 無 |
| 111 | 資結 12 題組＋演算法 5 題 | 17 | 16 | 無 |
| 112 | 資結 10 題複選＋演算法 5 題 | 15 | 7 | 無 |
| 113 | 資結 10 大題複選＋演算法 5 題 | 15 | 10 | 無 |
| 114 | 單選 4＋複選 7＋問答 2＋演算法 5 | 18 | 11 | 無 |
| 115 | 問答 4＋單選 8＋複選 3＋是非 5＋問答 4 | 24 | 11 | 單選 −1、是非 −1 |
111 年是分水嶺。 從這一年起，成大的卷子從 2–3 頁暴增到 7–16 頁，題型從純手寫轉為大量複選與填空。
成大最實用的發現：重複出題
這是整份統整最該先看的部分 —— 成大有非常明顯的重複出題習慣，同一題隔幾年就原封不動再考一次：
| 題目 | 出現年度 | 備註 |
|---|---|---|
| O(V) 判斷無向圖有無環（與 |E| 無關） | 106 第 7 題、108 第 5 題 | 敘述幾乎一字不差 |
| T(n) = 27T(n/3) + Θ(n3/lg n)（Master 不適用） | 109 Part II 第 5 題、112 第 11 題 | 完全相同 |
| 最佳二元搜尋樹（Optimal BST） | 106 第 5 題、111 第 14 題、112 第 14 題 | 規模逐年變大（6→5→7 個鍵） |
| 排序的比較下界 Ω(n log n) | 107 第 7 題、113 第 14 題 | 完全相同 |
| Floyd-Warshall 遞推式填空 | 110 第 9 題、114 第 18 題 | 完全相同 |
| 差限制系統求可行解 | 111 第 16 題、113 第 15 題 | 只換數字 |
| MST 上的路徑是否為最短路徑（是非） | 108 第 1(2) 題、109 第 1(3) 題 | 完全相同 |
| DFS 用 adjacency matrix／list 的複雜度（是非） | 108 第 1(1) 題、109 第 1(4) 題 | 只換表示法 |
| 高度 h 的 heap 最多／最少元素數 | 106 第 3 題、107 第 5 題、110 第 7(5) 題 | 三次 |
| 紅黑樹插入 62 | 111 第 3 題、113 第 8 題 | 同一棵樹、同一個插入值 |
| 最大流（給圖求最大流值） | 107 第 8 題、112 第 15 題 | 只換圖 |
| Bloom filter | 109 第 2 題、111 第 4 題、113 第 5 題、115 題組 A | 連四次 |
| 近似比計算 | 107 第 10 題（vertex cover, ρ=2）、111 第 17 題（set cover, ρ=ln n） | 成對 |
練成大考古題時務必跨年度比對 —— 106–110 的手寫題有很高機率在 111–115 以選擇題形式重現。
冷門樹結構清單（成大的招牌）
這是成大和其他學校差異最大的地方。以下結構在 CLRS 裡多半沒有，但成大十年反覆出現：
| 結構 | 出現年度 |
|---|---|
| Leftist tree（HBLT） | 113、114 |
| Binomial heap | 114 |
| Fibonacci heap（DecreaseKey／cascading cut） | 106、111、113、115 |
| Min-Max heap／Symmetric min-max heap | 112、113、115 |
| Patricia trie | 111、112、113 |
| Compressed trie／Digital search tree | 112、113、115 |
| Winner tree／Loser tree | 108 |
| **2-3-4 tree／B\*-tree** | 111、112、113 |
| Bloom filter | 109、111、113、115 |
建議直接讀 Horowitz《Fundamentals of Data Structures》，這些主題在該書都有完整章節；只讀 CLRS 會在成大的 Part I 大量失分。
主題出現年度一覽
| 主題 | 出現年度 |
|---|---|
| 遞迴式與 Master theorem | 106、107、108、109、110、111、112、113、114、115 |
| 平衡樹（AVL／紅黑樹／B-tree／B+ tree） | 106、108、110、111、112、113、114、115 |
| Heap 家族 | 106、107、110、111、112、113、114、115 |
| MST（Prim／Kruskal／最大成本生成樹） | 107、109、110、111、112、113、114、115 |
| Hash（linear／quadratic probing、碰撞設計） | 106、108、109、110、111、112、114、115 |
| NP 理論與近似演算法 | 106、107、108、110、111、115 |
| DP（LCS、最佳 BST、matrix chain、knapsack） | 106、109、110、111、112、113、114、115 |
| 圖走訪（DFS／BFS／拓撲／SCC） | 106、108、111、113、114、115 |
| 最短路徑（Floyd-Warshall／Bellman-Ford） | 110、113、114、115 |
| 最大流 | 107、112 |
| 攤銷分析 | 107 |
| 差限制系統 | 111、113 |
| AOE network | 108 |
| 排程（區間排程／Smith 規則） | 114 |
必守的五個主題
- 遞迴式與 Master theorem —— 十年全中。 而且成大特別愛考「不適用」的情況（109、110、112 三年），三種 case 的邊界與 gap 要非常清楚
- 最佳二元搜尋樹 —— 考過三次（106、111、112），是成大最高頻的手寫大題，DP 表要能穩定填完
- 冷門樹結構 —— 見上表。 這是成大 Part I 的主戰場，也是最容易和其他考生拉開差距的地方
- Bloom filter —— 連四年（109、111、113、115）。三種答案（「不在」確定、「可能在」、永遠不能說「在」）與最佳雜湊函式個數 k = (m/n)·ln2 都要記
- 近似比與歸約方向 —— vertex cover 是 2、set cover 是 ln n；「要證明新問題是 NPC，要從已知 NPC 歸約到新問題」這個方向在 115 年還是考了
給 116 年考生的策略
- 先把 106–110 的手寫題全部寫過一遍，成大重複出題的機率極高，這五年的題目很可能在 116 年以選擇題形式再出現
- Part I 要求「在答案卷第一頁做表整理答案」（111、112、113 連三年明訂，否則不予計分），進考場記得先看作答規定
- 115 年首次出現倒扣（單選 −1、是非 −1），若 116 年延續，單選題要有把握才填
- 111 年起題型全面情境化（神經網路、排課、防火牆、MRI、影像去背），但底層都是標準題 —— 練習「剝掉情境找出經典問題」
- 科目名稱是「程式設計」但不考語法；系所班別十年不變是「電機資訊學院－資訊聯招」，全卷不可使用計算機
本頁的題型、配分、倒扣規則均直接取自各年度試卷標示；主題出現年度與重複題比對為逐題整理。若發現有誤，歡迎來信指正。