110 師大資工所軟體考點分析
科目是「軟體基礎」，全卷 11 題手寫。前半是複雜度與資料結構操作的短答，後半用 40 分完整拆解 merge/quick sort 的分治步驟與 Johnson 演算法的每一步。
題型與配分
科目「軟體基礎」，適用系所：資訊工程學系，全卷 6 頁、11 題、100 分。
卷面註明：「請依序在答案卷上作答，並標明題號，不必抄題」「答案必須寫在指定作答區內，否則依規定扣分」。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | 三段程式的最壞複雜度 | 5% |
| 2 | 四種資料結構操作的緊上界 | 5% |
| 3 | 選擇題（5 題） | 15% |
| 4 | Hash（linear probing） | 5% |
| 5 | Heap 的兩次 deleteMax | 5% |
| 6 | 強連通元件 | 5% |
| 7 | Linked list 反轉的指標追蹤 | 5% |
| 8 | Threaded binary tree 的 inorder successor | 5% |
| 9 | Merge sort 與 quick sort 的分治步驟 | 20% |
| 10 | Dijkstra 與 Prim 的差異 | 10% |
| 11 | Johnson 演算法逐步拆解 | 20% |
逐題考點
- 第 1 題（5%）｜三段 pseudo-code 的最壞複雜度，答案必須從題目給的 11 個選項中挑（O(n2)、O(n log n)、O(n)、O(n2 log n)、O(2n)…）。(a) 雙層迴圈含累加 i (b) 每次 n−2 的遞迴 (c) 每次除以 2 的迴圈
- 第 2 題（5%）｜四個操作的最緊上界：(a) 用 BST 實作的 priority queue 找最小值 (b) 用 linked list 實作的 stack 做 pop (c) binary min heap 的 delete min (d) binary min heap 找最大值（O(n) —— 這是陷阱）
- 第 3 題（15%，5 小題各 3%）｜
- (3-1) adjacency matrix 下走訪某頂點所有邊的操作數（O(n)）
- (3-2) adjacency list 下的操作數（O(m)）
- (3-3) 陣列
5 3 8 9 1 7 0 2 6 4以 5 為 pivot 做 partition 後的結果 - (3-4) 哪一種排序最壞情況不需要 O(n2)（heap sort）
- (3-5) BST 刪除雙子節點時，若從左子樹挑替代節點，該找哪一個（左子樹的最大值）
- 第 4 題（5%）｜9 格雜湊表、h(k) = k % 9、linear probing，插入 5, 29, 20, 0, 27, 18 後的結果
- 第 5 題（5%）｜陣列
10 8 6 2 1 4 5組成 heap 後，做兩次 deleteMax 的陣列狀態 - 第 6 題（5%）｜給 8 節點 13 條邊的有向圖，列出所有強連通元件
- 第 7 題（5%）｜給一段 while 迴圈（反轉 linked list），畫出執行後的串列，並標出 Head、middle、trail 分別指向誰
- 第 8 題（5%）｜Threaded binary tree 的
insucc()填空三格，找 inorder successor 而不需要 stack - 第 9 題（20%，4 小題各 5%）｜分別描述 merge sort 的 divide 與 conquer 步驟、quick sort 的 divide 與 conquer 步驟，以及各自的時間複雜度。重點是兩者「工作量放在哪一邊」正好相反 —— merge sort 的 divide 是 O(1)、conquer 是 O(n)；quick sort 的 divide 是 O(n)、conquer 是 O(1)
- 第 10 題（10%）｜(a) 5% Dijkstra 中
u.d的意義 (b) 5% Dijkstra 與 Prim 的確切差異（鬆弛條件一個是u.d + w(u,v)、一個只是w(u,v)） - 第 11 題（20%，4 小題）｜Johnson 演算法逐步拆解：
- (a)i 3%｜為什麼要用 Bellman-Ford 而不是 Dijkstra（有負權邊）
- (a)ii 2%｜這張圖（含新增頂點 q）需要幾趟
- (b) 5%｜依據 h(a)=0、h(b)=0、h(c)=−4、h(d)=−3 畫出重新配權後的圖
- (c) 5%｜以 a 為源點的最短路徑長度 δ(a,b)、δ(a,c)、δ(a,d)
- (d) 5%｜Smith 教授提議「所有邊權減去最小邊權 c」這種更簡單的重新配權，問題出在哪裡（不同長度的路徑被扣掉的量不同，會改變最短路徑）
這份考卷的難點
- 第 11 題（20 分）的 Johnson 演算法是全卷核心，四小題完整走過「為何用 Bellman-Ford → 重新配權 → 跑 Dijkstra → 為何簡單做法不行」。第 (d) 小題最能區分是否真的理解。
- 第 9 題（20 分）要精確描述分治的兩個步驟，而不只是說「merge sort 是 O(n log n)」—— 要講出 divide 與 conquer 各自做什麼、各自多少時間。
- 第 2(d) 的「min heap 找最大值」是常見陷阱，答案是 O(n)（只能掃所有葉節點）。
- 第 8 題的 threaded binary tree 是課本角落的內容，要理解 thread 指標如何取代 stack。
準備建議
- 師大的「軟體基礎」全部是手寫申論，沒有選擇題以外的機械式作答，要能用文字把演算法講清楚
- Johnson 演算法在師大 110 佔 20 分、交大 107 佔 15 分、中正 111、112 也考過 —— 是跨校高頻的進階主題，務必完整讀懂
- 「所有邊加／減同一個常數為何不行」（110 第 11(d) 題）是最短路徑的經典反例，台大 112、交大 114 也考過
- Threaded binary tree、強連通元件、heap 找最大值 —— 這幾個「課本角落」是師大偏好的題材