111 師大資工所軟體考點分析

題型與配分

科目「軟體基礎」，適用系所：資訊工程學系，全卷 4 頁、7 題、100 分。

逐題考點

• 第 1 題（5%）｜17 個節點的樹，給 post-order 與 in-order，求 pre-order
• 第 2 題（15%）｜insertion sort 平均複雜度的完整推導：已知時間複雜度取決於逆序對（inversion）數，t(n) 為所有長度 n 排列的逆序對總數，要填出 t(n) = a(n) + b(n)·t(n−1) 中的 a(n)、b(n)，以及 t(n)/n! 的封閉式。
• 題目明訂答案必須是封閉式，可用的運算只有四則運算、階乘與二項式係數
• 關鍵：a(n) = n!·C(n,2)/… 的組合推導，最終 t(n)/n! = n(n−1)/4
• 第 3 題（20%）｜給一支通用的 Search(G) 程序與兩個用陣列實作的資料結構 X、Y（只給 Initialize／Empty／Insert／Extract 的 pseudo-code），要辨認：
• (a) X 是什麼基礎資料結構（queue）
• (b) 用 X 得到的搜尋程序叫什麼（BFS）
• (c) Y 是什麼（stack）
• (d) 用 Y 得到的是什麼（DFS）
• 要從 to_insert／to_delete 兩個索引的增減方式反推出 FIFO 與 LIFO 的行為
• 第 4 題（10%）｜分析 Build-Max-Heap 的時間複雜度，必須說明推導過程（答案 O(n)，要用 Σ h/2^h 的級數論證，不能只說「因為是 bottom-up」）
• 第 5 題（15%，3 小題各 5%）｜解遞迴式：(a) T(n) = T(n/3) + 1（Θ(log n)） (b) T(n) = T(n/3) + T(2n/3) + 3n（Θ(n log n)，遞迴樹） (c) T(n) = T(n−2) + T(n−1) + 1（指數，Fibonacci 型）
• 第 6 題（20%）｜0-1 Knapsack 完整四問：
• (a) 7%｜描述暴力解法並分析複雜度（O(2ⁿ·n)）
• (b) 5%｜寫出 DP 表 F[i,j] 的遞迴式
• (c) 5%｜對給定的 4 個物品（W=6）填出完整的 F 表
• (d) 3%｜哪些貪婪策略能得到最佳解（取最高價值／取最輕／取最高單位價值）—— 答案要看這個特定實例
• 第 7 題（15%）｜Floyd-Warshall：(a) 5% 解釋 d^k_ij 的意義 (b) 5% 給定權重矩陣 W，寫出 D⁰ (c) 5% 負權（無負環）時是否仍正確，並簡述理由（正確）

這份考卷的難點

1. 第 2 題（15 分）要求封閉式推導，而不是漸進界。要能算出「所有 n! 個排列的逆序對總和」，是全卷最數學的一題。
2. 第 3 題（20 分）的資料結構辨認很巧妙：X 的 Extract 是 to_delete++（FIFO，queue），Y 的 Insert 會把 to_delete 拉到 to_insert（LIFO，stack）。要逐行讀懂索引的變化。
3. 第 4 題明訂「必須說明推導過程」，寫 O(n) 沒有推導不給分。
4. 第 6(d) 的貪婪策略要針對題目給的實例判斷，而不是講一般結論 —— 0-1 knapsack 的貪婪一般不最佳，但這個實例可能剛好可行。

準備建議

• insertion sort 的平均複雜度 = 平均逆序對數 = n(n−1)/4 這個結論與推導都要會，師大 111 給了 15 分
• Build-Max-Heap 是 O(n) 的證明（Σ_h ⌈n/2^h+1⌉·O(h) 的級數）是 CLRS 經典，要能寫出來
• 0-1 knapsack 的四種問法（暴力、DP 遞迴式、填表、貪婪反例）在師大 111 一次全考，建議整套練熟
• 師大喜歡「給你程式碼／資料結構，要你辨認出它是什麼演算法」（111 第 3 題），這需要真的讀懂 pseudo-code