113 成大資工所軟體考點分析

題型與配分

編號 197，系所「電機資訊學院－資訊聯招」，考試科目：程式設計，考試日期 113 年 2 月 1 日第 2 節，全卷 10 頁、15 題、100 分，不可使用計算機。

作答規定：Part I 同樣明訂「請在答案卷第一頁做表，將答案整理於該表中。否則，不予計分。」（111、112、113 連三年）

Part I 資料結構考點（1–10）

• 第 1 題（3%+2%）｜BST 依序插入 15, 8, 13, 18, 17, 6, 11, 14, 5：(i) 某節點的層數 (ii) 刪除 15 時，用左子樹最大或右子樹最小的哪個 key 替代
• 第 2 題（1%+1%+3%）｜同一組數字 20, 5, 10, 18, 4, 22, 11, 32, 21 分別建成：(i) max heap 時 5 的層數 (ii) min heap 的節點位置 (iii) symmetric min-max heap 的性質。第三小題的 symmetric min-max heap 是極冷門的結構
• 第 3 題（2%+3%）｜由 postfix 與 infix 走訪序列重建二元樹，再問 level-order 與 preorder
• 第 4 題（2%+3%）｜帶權無向圖：(i) DFS 與 BFS 的合法走訪順序判斷 (ii) 最大成本生成樹（maximum cost spanning tree）的度數、成本、邊與路徑長度
• 第 5 題（3%+2%）｜Bloom filter：給三個具體雜湊函式與一張 15 格 filter，(i) 判斷插入／刪除／查詢的結果（注意 Bloom filter 不支援刪除） (ii) 元素數為 5 時，最小化偽陽性的最佳雜湊函式個數（公式 (m/n)·ln2）
• 第 6 題（5%）｜Height-based leftist tree（HBLT） 刪除最小元素後的結構判斷
• 第 7 題（5%）｜Fibonacci heap 連續操作：decrease key 14 by 5、decrease key 21 by 14、delete key 12、insert 14、delete min，判斷過程中是否發生 cascading cut 與最終的 min tree 個數
• 第 8 題（5%）｜紅黑樹插入 62 後的結果是哪一棵（與 111 年第 3 題是同一棵樹、同一個插入值）
• 第 9 題（5%）｜**B\*-tree（order 4，即 2-3-4 tree）**的插入與刪除後各節點的 key
• 第 10 題（5%）｜給一棵 binary trie，問轉換成 Patricia 後哪一個是正確結果

Part II 演算法考點（11–15，各 10 分）

• 第 11 題｜Strassen 的變形：一個矩陣分塊遞迴程序，但 C₂₂ 只呼叫一次（少了一次遞迴），共 7 次遞迴呼叫，求 T(n) 的緊界 Θ。答案是 Θ(n^log₂7)
• 第 12 題｜神經網路包裝的矩陣鏈相乘：n 層全連接網路，各層神經元數為 ⟨10, 6, 12, 5, 50, 3⟩，求從輸入層算到輸出層的最少乘法次數。這就是 matrix-chain multiplication 換皮
• 第 13 題｜寫出 LCS 的遞迴式 c[i,j]
• 第 14 題｜以比較與交換為基礎的排序其下界是多少（與 107 年第 7 題完全相同）
• 第 15 題｜差限制系統求可行解集合或判定無解（與 111 年第 16 題同型）

這份考卷的難點

1. Part I 的冷門結構密度是十年最高。 Symmetric min-max heap、height-based leftist tree、Fibonacci heap 的 cascading cut、B\*-tree、Patricia —— 五個主題合計 25 分，都不是必修課會細講的。
2. 第 7 題的 Fibonacci heap 要跑完五個連續操作，任何一步的 cut／cascading cut 判斷錯誤，後面全錯。
3. 第 12 題的偽裝：題面講神經網路與權重矩陣，實際上就是求 ⟨10,6,12,5,50,3⟩ 的最佳矩陣相乘順序。認不出來會以為要算神經網路的參數量。
4. 第 11 題的變形 Strassen：要注意 C₂₂ 只呼叫一次，總共 7 次遞迴，所以是 T(n) = 7T(n/2) + Θ(n²)。

準備建議

• 成大的冷門樹結構是必守範圍：leftist tree、min-max heap、symmetric min-max heap、Fibonacci heap、B\*-tree、Patricia、trie 家族 —— 建議直接讀 Horowitz《Fundamentals of Data Structures》而非只讀 CLRS
• Bloom filter 連三年出現（109、111、113），最佳雜湊函式個數 k = (m/n)·ln2 要記住，也要知道標準 Bloom filter 不支援刪除
• 差限制系統（111 第 16 題、113 第 15 題）與排序下界（107 第 7 題、113 第 14 題）都是成大的重複題
• 看到情境包裝（神經網路、基因序列）先想「這是哪個經典 DP 換皮」—— 113 第 12 題就是 matrix chain