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

題型與配分

全卷 4 頁、10 題、100 分，沒有選擇題，全部寫在答案卷上。

計分規定：卷面第一行寫明「NO partial score will be given for partially correct answer」，每個子題答對才給分。另外註明「除非特別說明，只需要最終答案」。

逐題考點

• 第 1 題（10%）｜1..n 經過 stack 後可以產生幾種 permutation b_n。(a) recurrence　(b) closed form
• 第 2 題（5%）｜把 (a/(c*(b+d)))/(e-a)*c 轉成 postfix
• 第 3 題（10%）｜依序 insert 7、4、3、1、delete min、insert 9、2、5、delete min、delete min，畫出最終的 min-heap
• 第 4 題（8%）｜說明如何在 O(n) 時間建 heap，可用 n = 15 舉例（不必證明複雜度）
• 第 5(a) 題（6%）｜Quicksort 的三個是非：輸出是否非遞增、是否為 stable sort、是否為 in-place sort
• 第 5(b) 題（4%）｜n 個元素全部相同時的最壞複雜度
• 第 5(c) 題（10%）｜補完 PARTITION_THREE() 的 (A)(B)(C) 三個空格，讓三路分割版本在全等輸入下跑出 O(n)
• 第 6(a) 題（3%）｜寫出 linear probing 的 h(k,i)
• 第 6(b) 題（5%）｜double hashing，h₁(k)=k mod 16、h₂(k)=1+(k mod 15)、m=16，依序插入 {16, 3, 35, 67, 51, 1, 15, 31, 19, 17}，畫出最終表格
• 第 6(c) 題（5%）｜Alpha 教授改用 h₂(k)=2·(k mod 8)，舉例說明這個設計為何有問題
• 第 7 題（6%）｜三個是非：Dijkstra 能否處理負權（無 negative cycle）、Bellman–Ford 是否解全點對、Floyd–Warshall 在有 negative cycle 時是否仍正確
• 第 8 題（8%）｜給一段 Cycle-Removal(G,u) 的 pseudo-code，節點分成 Type-0/1/2 三色，要填出第 8、10、11、14 行的 A、B、C、D 四個值使它能正確輸出 acyclic graph
• 第 9 題（10%）｜14 艘船要到對岸，同字母的船才能停同字母的碼頭，航線交叉的船必須等 15 分鐘。(a) 9 點能出發的最大船數　(b) 寫出那些船的編號
• 第 10 題（10%）｜給一串圖形與一張替換規則表（含替換前後成本），求總成本最小的替換方式。(a) 最小總成本　(b) 由左至右列出使用的規則

作答時要注意的地方

1. 沒有部分分數。第 5(c) 的三個空格、第 8 題的四個值、第 6(b) 的整張 hash 表，錯一格整個子題沒分。
2. 第 9、10 題的題面沒有提到經典問題的名字。
3. 第 5 題 20 分，是全卷配分最高的一題。
4. 第 6(c) 問新的 h₂ 設計有什麼問題，115 年第 16 題又考了同一個觀念。

準備方向

• Stack permutation 數的計數，108 年考過，同類的計數場景有 binary tree 形狀、括號序列。
• Quicksort 的三路分割，第 5(c) 要補程式。
• Double hashing 對第二個 hash function 的條件，108 第 6(c) 與 115 第 16 題都考。
• 情境題：109 的 SNP 題、110 的 snake sequence、114 的球隊淘汰題，都是經典問題換了說法。