師大資工所軟體考古題六年大統整（110–115）
考試形式（六年不變）
- 全卷 4–7 頁、7–13 題
- 全部手寫，作答於答案卷
- 卷面固定註明：「請依序在答案卷上作答，並標明題號，不必抄題」「答案必須寫在指定作答區內，否則依規定扣分」
- 沒有倒扣
- 頁數與題數逐年趨於整齊：115 年已固定為 10 題、每題 10 分
題型演變
| 年度 | 題數 | 頁數 | C 程式比重 | 最大單題 |
|---|---|---|---|---|
| 110 | 11 | 6 | 10% | Johnson 演算法（20 分） |
| 111 | 7 | 4 | 0% | Knapsack 四問（20 分）、BFS/DFS 辨認（20 分） |
| 112 | 10 | 6 | 25% | LCS 四問（20 分） |
| 113 | 13 | 7 | 45% | 二分圖與最大匹配（30 分） |
| 114 | 8 大題 | 5 | 20% | TSP 2-近似證明（20 分） |
| 115 | 10 | 6 | 0% | 每題均為 10 分 |
113 年是 C 語言比重最高的一年（45%），而且偏向實務與安全（
gets()的風險、字串常數唯讀、函式指標陣列、container_of巨集）。115 年則完全沒有 C 程式題，改為全部演算法分析。
師大的兩個固定出題模式
1. 「一個主題，四到五問」
這是師大最鮮明的特色 —— 把一個經典問題從暴力解一路問到理論極限：
| 年度 | 主題 | 問法 |
|---|---|---|
| 111 第 6 題（20 分） | 0-1 Knapsack | 暴力解＋複雜度 → DP 遞迴式 → 填表 → 哪些貪婪可行 |
| 112 第 8 題（20 分） | LCS | 暴力解＋複雜度 → DP 遞迴式 → 填表 → 為何這個最長路徑實例是多項式 |
| 112 第 9 題（15 分） | Huffman | 為何是貪婪 → 實際建碼 → 最大碼長 |
| 113 第 13 題（30 分） | 二分圖／最大匹配 | DFS → 是否二分圖 → 判斷演算法 → max flow／min cut → 如何解最大匹配 |
| 114 第八題（20 分） | TSP 2-近似 | w(C) ≤ 2w(T) → w(T) ≤ w(C\*−e) → 合併得證 |
| 110 第 11 題（20 分） | Johnson 演算法 | 為何用 Bellman-Ford → 幾趟 → 重新配權 → 跑 Dijkstra → 為何簡單做法不行 |
準備策略：把經典問題的「四種問法」一起練 —— 暴力、DP/貪婪、實際操作、理論界限。
2. 「給你程式碼／結構，辨認它是什麼」
| 年度 | 題目 | 其實是 |
|---|---|---|
| 111 第 3 題（20 分） | 兩個用陣列實作的資料結構 X、Y | queue（BFS）與 stack（DFS） |
| 113 第 1 題 | 遞迴印 a % 2 | 十進位轉二進位 |
| 113 第 2 題 | 函式指標陣列 + enum | 有限狀態機 |
| 113 第 3 題 | 字元範圍判斷與加法 | 大寫轉小寫 |
| 113 第 6 題 | 兩個巨集 | Linux 的 container_of |
| 115 第 1 題 | 五層巢狀迴圈 | 1-D 卷積神經網路 |
主題出現年度一覽
| 主題 | 出現年度 |
|---|---|
| 最短路徑（Dijkstra／Bellman-Ford／Floyd／Johnson） | 110、111、113、115 |
| 圖走訪與生成樹（DFS／BFS／dfn-low／雙連通元件） | 110、111、112、113、114、115 |
| 複雜度分析與遞迴式 | 110、111、114、115 |
| Huffman／最佳合併樹 | 112、114、115 |
| Heap 與優先佇列 | 110、111、112、115 |
| 排序演算法的分治拆解 | 110、112、114、115 |
| DP（knapsack／LCS／matrix chain） | 111、112、115 |
| C 程式填空（stack／queue／linked list／稀疏矩陣） | 112、113、114 |
| AVL 樹 | 113 |
| 最大流／最小割／二分匹配 | 113 |
| 近似演算法（TSP 2-近似） | 114 |
| 字串比對（Rabin-Karp） | 115 |
| 漸進記號的猜想判斷 | 115 |
必守的五個主題
- 圖的走訪與 dfn／low —— 六年全中。DFS／BFS 生成樹、關節點、雙連通元件，而且師大是照 Horowitz 的
dfnlow()程式碼出題 - 最短路徑四演算法 —— 特別是 Johnson 演算法（110 年 20 分）與 Floyd-Warshall（111、115），要能解釋每一步為什麼這樣做
- 經典 DP 的四種問法 —— knapsack（111）、LCS（112）各 20 分，暴力／遞迴式／填表／理論都要會
- Huffman 及其延伸 —— 為何是貪婪、最大碼長 n−1、最佳合併樹、解碼，三年出現
- Horowitz 課本的程式碼 —— 稀疏矩陣轉置、環狀串列、threaded tree 的 inorder successor、adjacency multi-list、用串列實作 queue
給 116 年考生的策略
- 沒有倒扣，每一題都要寫。 就算只答得出部分觀念，申論題也可能拿到部分分數
- 「不必抄題」但要「標明題號」，且答案必須寫在指定作答區內，否則扣分 —— 作答格式要注意
- 把 CLRS 與 Horowitz 兩本都讀：CLRS 負責演算法分析與證明（近似演算法、Johnson、TSP），Horowitz 負責程式填空與課本角落結構
- 練習「把一個演算法的每一步講清楚」 —— 師大不考機械式計算，考的是「為什麼這樣做」「為什麼別的做法不行」
- 邊權加常數對 MST 與最短路徑的不同影響（110 第 11(d)、114 第七題）連兩次出現，是師大最愛的對比題
- 115 年改為「10 題、每題 10 分」的整齊結構，若延續，時間分配會比前幾年好掌握
本頁的題型、配分均直接取自各年度試卷標示（來源：臺灣師範大學圖書館考古題）；主題出現年度為逐題比對後的整理。若發現有誤，歡迎來信指正。