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

題型與配分

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

逐題考點

• 第 1 題（9%）｜稀疏矩陣的快速轉置（Horowitz 課本的 fastTranspose）：(a) 6% 給定稀疏矩陣，寫出執行後 rowTerms[]、startingPos[] 與 b[] 的內容 (b) 3% m×n 矩陣有 k 個非零項時的時間複雜度（O(n+k)）
• 第 2 題（10%）｜環狀串列：(a) 6% 補完 insertFront 的三個空格（空串列與非空串列兩種情況） (b) 4% 如何只加一行指令就變成插入到尾端（答案：再加 *last = node;）
• 第 3 題（6%）｜由 postfix 運算式建運算式樹的 pseudo-code 填空三格（遇數字 push、遇運算子 pop 兩個接成子樹再 push、結束時 pop 出根）
• 第 4 題（9%）｜(a) 5% 用 Prim 求 MST，在給定的邊表上標出選取順序 (b) 4% 實作 Kruskal 時哪些資料結構能提高效率（min heap 與 disjoint set）
• 第 5 題（6%）｜heap sort：(a) 3% 初始調整後的 max-heap (b) 3% 最大的兩個數字換到 a[9]、a[8] 後的陣列
• 第 6 題（10%）｜給無向圖的 adjacency matrix：(a) 2% 寫出對應的 adjacency list (b) 6% 依據給定的 dfnlow() 程式碼執行 dfnlow(0, -1)，寫出 dfn[] 與 low[] (c) 2% 說明如何依據 dfn 與 low 判斷關節點
• 第 7 題（10%）｜相較於暴力排序（bubble／selection），(a) 5% merge sort 省下了哪些計算 (b) 5% quicksort 省下了哪些計算。關鍵：分治把「跨兩半的比較」整批省掉
• 第 8 題（20%）｜LCS 四問：
• (a) 5%｜暴力解法與複雜度（列舉 X 的所有子序列，O(2^m · n)）
• (b) 5%｜DP 表 L[i,j] 的遞迴式
• (c) 5%｜對 X = ATTGA、Y = CCTTAG 填出完整的 L 表
• (d) 5%｜LCS 可視為最長簡單路徑問題，一般而言最長簡單路徑是 NP-complete，為什麼這個實例能在多項式時間解決（因為對應的圖是 DAG）
• 第 9 題（15%）｜Huffman 三問：(a) 5% 為什麼 Huffman 是貪婪演算法 (b) 5% 對給定的 5 個字元機率求 Huffman 的輸出 (c) 5% n 個字元的 Huffman 編碼，碼字的最大可能長度是多少（n−1）
• 第 10 題（5%）｜若最大字元頻率小於最小頻率的兩倍，Huffman 編碼是否比 8-bit 定長碼更有效？要說明理由（此時所有碼長幾乎相同，優勢很小）

這份考卷的難點

1. 第 8(d) 是全卷最需要洞察的一問：要看出 LCS 對應的圖是 DAG，而最長簡單路徑的 NP-complete 是針對一般圖 —— DAG 上可以用 DP 在多項式時間解。
2. 第 1 題的稀疏矩陣快速轉置是 Horowitz 課本的內容，rowTerms 與 startingPos 的計算方式要熟。
3. 第 9(c) 的最大碼長 n−1需要想到「頻率呈 Fibonacci 分布時會退化成鏈狀樹」。
4. 第 6 題要照著給定的程式碼跑 dfnlow，而不是用自己記得的版本 —— 要注意 else if (w != v) 這個條件。

準備建議

• 師大的題材大量來自 Horowitz《Fundamentals of Data Structures in C》（稀疏矩陣、環狀串列、threaded tree、dfnlow），與只讀 CLRS 的準備方向不同
• LCS 的四種問法（暴力、遞迴式、填表、為何多項式）在師大 112 一次全考，與 111 年的 knapsack 四問是同一個出題模式
• Huffman 的三個延伸問題（為何是貪婪、最大碼長、何時不划算）值得一起準備
• Articulation point 的 dfn／low 在師大 112、中正 110/111/115 都考，是跨校高頻題