110 中興資工所軟體考點分析
甲組「資訊概論」首度明確切成兩半：PART II（50%）就是資料結構與演算法，21 個小題全選擇、不倒扣，最後 16 分是多重選擇。
題型與配分
系所「資訊科學與工程學系 甲組」，科目：資訊概論，全卷 10 頁、100 分，不得使用計算機，卷首註明「請依序作答」。
110 年是格式的分水嶺：卷子第一次明確寫出「PART I（50%）作業系統與計算機組織」「PART II（50%）資料結構與演算法」，軟體與硬體各半。111 年沿用同一結構，只是把兩個 PART 對調。
| 區段 | 題組 | 內容 | 配分 |
|---|---|---|---|
| PART I 作業系統與計算機組織 | 1–5 | 每題組 4 個單選小題 | 50%（每題組 10%） |
| PART II 資料結構與演算法 | 6 | 3 小題 | 6% |
| 7 | 5 小題 | 10% | |
| 8 | 4 小題 | 8% | |
| 9 | 5 小題 | 10% | |
| 10 | 多重選擇 4 小題 | 16% |
全卷都是選擇題，而且卷上沒有任何倒扣的標示（與同年「基礎數學 A」的是非題答錯 −1 不同）。不倒扣就代表每一格都要填，不要留空白。
PART II：資料結構與演算法（50%）
第 6 題組（6%）
- A｜給一段操作 doubly linked list 的 C 函式（交換每個節點的
prev與next），問1↔2↔3↔4↔5↔6呼叫後變成什麼（答案是整串反轉） - B｜雜湊表開放定址＋線性探測，
h(k) = k mod 10，插入 6 個值後得到指定的表，問哪一個插入順序是可能的 - C｜依序插入 40, 60, 55, 15, 20, 5, 25, 30 到紅黑樹，求紅色節點的數字總和。要完整做完每一步的旋轉與重新著色
第 7 題組（10%）
- A｜四個演算法各該配哪個資料結構：BFS → Queue、DFS → Stack、Prim → Priority Queue、Kruskal → Union-Find
- B｜給一棵二元樹，判斷關於後序走訪序列的五個敘述哪一個正確
- C｜依序把 34, 44, 62, 29, 56, 61, 100 插入陣列式 max heap，問最後的陣列內容（每插入一個就要上浮）
- D｜遞迴函式
f(n) = n − 10 (n > 100); f(f(n+11)) (n ≤ 100)，求f(91)。這是 McCarthy 91 函式，答案對所有 n ≤ 100 都是 91 - E｜中序式與後序式的對應關係，哪個敘述正確（運算元順序相同、括號數量不同、求值用 stack 而非 priority queue）
第 8 題組（8%）
- A｜activity network 的關鍵路徑長度
- B｜哪個排序的最壞情況是 O(n log n)（bubble／quick／merge／insertion／selection → merge sort）
- C｜給一個流網路，求 s 到 t 的最小割容量
- D｜Huffman 編碼：100 個字元的檔案只有 a–f 六種字元，頻率 40、12、13、9、16、10，問編碼後需要幾個 bit
第 9 題組（10%）
- A｜0/1 背包（非分數）：7 個物品、容量 16，求最大價值
- B｜矩陣鏈乘法：A1(10×5)、A2(5×20)、A3(20×10)、A4(10×5)，求最少純量乘法次數
- C｜給一張圖，問哪條邊不會出現在最小生成樹裡
- D｜最短路徑的錯誤敘述：DAG 可用拓撲排序、Bellman-Ford 是單源、Floyd-Warshall 是全點對（不是單源）、DAG 可在 O(V+E) 完成、Dijkstra 與環的關係
- E｜NP 理論的正確敘述：NP-hard 不一定是 NP-complete、NP 問題的驗證需要 certificate、歸約方向、P = NP 與整數分解、能歸約到 SAT 不代表是 NP-complete
第 10 題組：多重選擇（16%，每小題 4%）
- A｜哪個度數序列不可能是任何圖的度數序列（用 handshaking lemma 與 Erdős–Gallai 判斷；有一組出現「度數 ≥ 頂點數」的矛盾）
- B｜哪些是貪婪演算法——選項橫跨 Prim、Dijkstra、Kruskal、Bellman-Ford、Floyd-Warshall 五個演算法，要能分辨哪些屬於貪婪、哪些屬於動態規劃
- C｜把 N、N!、N log N、N log(log N)、N log2N、N log(N2)、2n、√N log N、N2 等函數依漸近成長速度由大到小排序，再判斷敘述
- D｜加權圖的性質——五個敘述涵蓋 每條邊加一個常數後最短路徑會不會改變、MST 上的路徑是不是最短路徑、樹是不是二分圖、二分圖最大匹配能不能用最大流求、增加任一條邊的容量能不能增加最大流
這份考卷的難點
- 第 10 題組 16 分是多重選擇，五個選項要逐一判斷。以 D 為例，五個敘述橫跨最短路徑、MST、二分圖、最大流四個主題，任何一個沒把握就整題有風險。
- 第 7-D 的 McCarthy 91 函式是遞迴裡最出名的陷阱：
f(f(n+11))的雙層遞迴看起來會爆炸，但實際上對所有 n ≤ 100 都收斂到 91。沒看過就只能硬展開，會耗掉大量時間。 - 第 6-C 的紅黑樹要插入 8 個節點並全程維持性質，中間任何一次旋轉或著色錯了，最後的紅色節點總和就錯。這是整份卷子單題最花時間的一格。
- 第 10-C 的漸近排序有九個函數，其中
N log(N²) = 2N log N、N log²N、√N log N三個最容易排錯。 - PART I 的 20 個小題涵蓋整個 OS 與計組（排程、分頁、TLB、虛擬記憶體、pipeline hazard、register renaming、中斷、DMA），佔一半分數，不能只準備軟體。
準備建議
- 110 與 111 的結構幾乎一樣（軟體 50 + 硬體 50、全選擇、不倒扣），這兩年並排練是投報率最高的做法
- 不倒扣就全部要填——這與同年數學科的是非題倒扣規則不同，同一天考的兩科規則相反，進場要分清楚
- 經典演算法的「該配哪個資料結構」與「屬於哪個演算法典範」（貪婪／DP／分治）是中興每年都出的送分題，整理成一張表
- Huffman 編碼的位元數計算（110 第 8-D 題）在中興數學科 113 年也考過，兩科都要練
- 矩陣鏈乘法在 110（第 9-B 題）與 112（PART 2 第 III 題）都出現，DP 表格要能手畫
- 紅黑樹、AVL、B-Tree 的旋轉規則要練到能默寫，110 考紅黑樹、113 考 AVL 最少節點數、114 考 B-Tree 分裂