114 師大資工所軟體考點分析
前半是 20 分的 C 程式填空與選擇，後半連考三題證明：邊權加常數對 MST 與最短路徑的影響、以及 TSP 的 2-近似完整證明（20 分）。
題型與配分
科目「軟體基礎」，適用系所：資訊工程學系，全卷 5 頁、8 大題、100 分。
| 大題 | 主題 | 配分 |
|---|---|---|
| 一 | C 程式填空（12 格） | 20% |
| 二 | 排序問題 | 8% |
| 三 | 選擇題（4 題） | 12% |
| 四 | Adjacency multi-list 與雙連通元件 | 10% |
| 五 | 未知長度陣列的 O(log n) 搜尋 | 7% |
| 六 | 模反元素演算法 | 8% |
| 七 | 邊權加常數的影響（證明） | 15% |
| 八 | TSP 的 2-近似證明 | 20% |
逐題考點
一、填充題（20%，12 格）
- (一) 4%｜用陣列實作 stack 的
isEmpty／push／pop填 4 格 - (二) 6%｜用 stack 檢查括號是否配對的
isBalanced填 3 格 - (三) 10%｜合併兩條已排序串列（用 dummy head）的
mergeSortedLists填 5 格
二、排序問題（8%）
- (一) 4%｜7 個已排序檔案（大小 1200, 900, 2500, 3200, 800, 1800, 1500）要做多次 2-way merge，決定合併順序使總 I/O 最小。這就是 Huffman／最佳合併樹
- (二) 4%｜給 9 個數字的陣列與四個中間狀態，判斷哪個是 insertion sort 的可能中間結果、哪個是 iterative merge sort 的可能中間結果
三、選擇題（12%，4 題各 3%）
- (一) adjacency matrix 下取得某頂點所有邊的複雜度
- (二) 求 n 節點二元樹高度的最壞複雜度（O(n)，與 113 年第 8(a) 題相同）
- (三) 在 max heap 中找特定元素的複雜度（O(n)）
- (四) 多選：BST 的哪些走訪可以重建出相同的樹結構（preorder、postorder、level-order 都可以；單獨的 inorder 不行）
四、Adjacency multi-list（10%）
給圖 G 的 adjacency multi-list 結構：(一) 3% 從 V3 出發的 BFS 生成樹 (二) 4% 從頂點 3 出發求各頂點的 dfn 與 low (三) 3% 畫出雙連通元件
五、O(log n) 搜尋（7%）
陣列 A[1:N] 前 n 個位置（n < N/2）是遞增整數，其餘都是很大的數 M。輸入只有 y，不知道 n 與 N，要設計 O(log n) 演算法找出 A[k] = y 或回報不存在。標準解：先用指數倍增（1, 2, 4, 8…）找出邊界，再二分搜尋
六、模反元素（8%）
輸入 a 與 n，設計有效率的演算法求 a 在 Z_n 中的反元素（擴展歐幾里得演算法）
七、邊權加常數（15%）
圖中有負權邊，若把所有邊權加上同一個固定常數使其非負：
- (一) 7%｜是否仍能得到原圖正確的 MST？（可以 —— 要證明：MST 的邊數固定為 |V|−1，所有生成樹都增加同樣的量）
- (二) 8%｜最短路徑是否也可以？（不行 —— 要舉反例：不同路徑的邊數不同，增加量不同）
八、TSP 的 2-近似（20%）
在滿足三角不等式的完全圖上，用「求 MST → 對 T 做 DFS 列出頂點 → 輸出該環」得到的 Hamiltonian cycle C，要證明 **w(C) ≤ 2w(C\*)**，分三步：
- (一) 9%｜證明 w(C) ≤ 2w(T)（DFS 走訪每條樹邊兩次，再用三角不等式抄捷徑）
- (二) 8%｜證明 **w(T) ≤ w(C\* − {e})**（從最佳環刪掉任一邊會得到一棵生成樹，其權重不小於 MST）
- (三) 3%｜合併得出 **w(C) ≤ 2w(C\*)**
這份考卷的難點
- 第八題（20 分）的 TSP 2-近似證明是全卷核心，三步驟環環相扣，是 CLRS 第 35 章的完整定理證明。
- 第七題（15 分）的對比很漂亮：同樣是「所有邊加常數」，MST 不變但最短路徑會變。要能分別給出證明與反例。
- 第五題的「不知道 n 與 N」是關鍵限制 —— 必須先用指數倍增找邊界，直接二分搜尋是不行的。
- 第二(一) 題的最佳合併順序要認出是 Huffman，用 min heap 每次取兩個最小的合併。
準備建議
- TSP 的 2-近似證明（114 第八題 20 分）與近似演算法在師大、台大 113、成大 107/111 都出現，CLRS 第 35 章務必讀
- 「所有邊加常數」對 MST 與最短路徑的不同影響是跨校高頻對比（師大 114、台大 112、交大 114、師大 110）
- 擴展歐幾里得求模反元素是數論內容，但在軟體考科出現，建議補一下
- 師大的 C 程式填空每年都有（112、113、114），而且都是課本的標準實作（stack、queue、linked list merge）