106 台大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 2 頁、5 大題、100 分，全部手寫，沒有選擇題。

第 4、5 題的作答規定

卷面對第 4、5 題訂了三條規定，違反的該題不計分：

1. 不要書寫任何程式碼或代碼，以文字、圖表、數學符號陳述概念。
2. 一個子題的回答以一頁為限，並按順序寫在完整的一頁。字太小、太潦草或英文 grammar 問題導致閱卷者無法理解，該題不計分。
3. 每題的 (a) 是觀念陳述，佔 10 分；(b) 是觀念的證明，佔 15 分。證明部分答對得 15 分，答錯倒扣 10 分，不答得 0 分。

卷面另寫了「知之為知之，不知為不知，是知也。瞎掰不能解決問題，珍惜分數，遠離倒扣。」台大軟體 106–115 只有這一年對申論題設倒扣。

逐題考點

• 第 1 題（20%）｜recurrence 求 big-O 上界，要求 as tight as possible 並說明理由。四小題分別是 T(n)=T(n/3)+1、T(n)=3T(n/3)+1、T(n)=T(n/10)+T(9n/10)+n、T(n)=2T(√n)+lg n
• 第 2 題（15%）｜BST 中存放 1 到 1000 的數字、要搜尋 400，判斷給定的三個序列能不能是被檢查過的節點序列，並說明理由
• 第 3 題（15%）｜給定 LCS_LENGTH 與 LCS_OUTPUT 兩支 pseudo-code，填 3A、3B、3C 三個空格
• 第 4 題（25%）｜給一張 DAG，節點有參觀天數 c(v)、邊有交通天數 r(u,v)，求從首都到每個城市的最少天數 M(v)。(a) 10%：設計最佳演算法　(b) 15%：分析時間複雜度並證明它是最佳的
• 第 5 題（25%）｜C 個班級、R 間教室，給定可分配的 (c,r) 配對集合 M，求最多能分配幾個班級。(a) 10%：說明如何轉成 network flow 問題　(b) 15%：證明 Ford–Fulkerson 用你的轉換能正確求解，題目追問是否任何一個 maximum flow 都會給出正確答案

作答時要注意的地方

1. 第 4(b)、5(b) 答錯各扣 10 分，兩小題證明合計 30 分。
2. 第 4(b) 要求證明最佳性，只寫複雜度分析不夠。
3. 第 4、5 題不能寫程式碼，每個子題限一頁。

準備方向

• recurrence 要練 Master theorem 以外的解法，第 1 題的第 4 小題就是例子。
• LCS 的 DP 表與 backtracking 輸出，106 年只考填空，同一組觀念在後來的年度還會出現。
• Max flow 與 bipartite matching 的轉換，在 106 第 5 題、110 第 16 題、114 第 7 題都出現過。
• 證明題的版面限一頁，練習時也限一頁寫完。