110 成大資工所軟體考點分析｜國立成功大學

資料結構 50%＋演算法 50%、全卷 9 題手寫。第 6 題一次考五條遞迴式（含 Master theorem 不適用的情況），第 8 題是 shuffle 字串的 DP 填空。

題型與配分

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

區段	題號	配分
Part I 資料結構	1–5	50%（每題 10 分）
Part II 演算法	6–9	50%

第 1 題（10%）｜由 preorder 50, 15, 11, 3, 2, 22, 84, 80, 77, 90, 95 重建 BST，寫出樹的層數（題目定義根為 level 1）
第 2 題（10%）｜給字元與其出現頻率，求 Huffman code 編碼後的總位元數
第 3 題（10%）｜四個字串 abcdef、bcdefa、cdefab、defabc 存入雜湊表：
(1) 5%｜雜湊函式為「ASCII 值總和 mod 11」時發生幾次碰撞（這四個字串是彼此的旋轉，總和相同，所以全部碰撞）
(2) 5%｜改為「ASCII 值乘上在字串中的位置後加總 mod 11」時發生幾次碰撞
這題的設計非常巧妙 —— 展示了位置加權如何解決 anagram 型碰撞
第 4 題（10%）｜給一段雙迴圈程式：(1) 5% n = 4 時的輸出 (2) 5% 時間複雜度 T(n)
第 5 題（10%）｜給一張帶權圖，求 MST 的成本

第 6 題（15%，5 小題各 3%）｜用 Master method 求緊界，若不適用要指出並說明：
(1) T(n) = 2T(n/4) + √n（case 2）
(2) T(n) = T(n−1) + n lg n（不是分治形式，Master theorem 不適用）
(3) T(n) = 3T(n/4) + n lg n（case 3）
(4) T(n) = 4T(n/2) + n² lg n（case 2 與 case 3 之間的 gap，不適用）
(5) T(n) = 7T(n/2) + Θ(n²)（case 1）
五題裡有兩題是「不適用」，這是成大最愛的陷阱
第 7 題（15%，5 小題各 3%）｜是非題並說明理由：
(1) NPC 問題可多項式歸約到 L，L 是否必為 NPC（假，只能推出 NP-hard）
(2) A 可歸約到 B 且 A ∈ P，是否 B ∈ P（假，方向錯了）
(3) A ∈ P 是否必有 A ∈ NP（真）
(4) P ≠ NP 時，一般 TSP 是否有 2-近似演算法（假，一般 TSP 無常數近似；有三角不等式的 metric TSP 才有）
(5) 高度 h 的 heap 最多元素數是否為 2^h − 1
第 8 題（10%）｜Shuffle 字串的 DP：判斷 z 是否為 x 與 y 的 shuffle（例如 NioCKsiUe 是 NCKU 與 csie 的 shuffle）。要填 isShuffle pseudo-code 的三個空格 —— 兩個邊界初始化與一個轉移式
第 9 題（10%）｜Floyd-Warshall：(1) 2% 時間複雜度 (2) 3% 補完 D^k 由 D^k−1 遞推的公式 (3) 5% 對給定的有向圖計算 dist(1,5)+dist(2,5)+dist(3,5)+dist(4,5)+dist(6,5)

第 6 題的五條遞迴式（15 分）是全卷重點。 其中兩條 Master theorem 不適用（一條不是分治形式、一條落在 case 2 與 3 的 gap），要能指出並解釋。
第 7(4) 的一般 TSP 沒有常數近似是很多人的盲點 —— 課本只教了 metric TSP 的 2-近似，一般 TSP 在 P ≠ NP 下連任何常數近似都沒有。
第 3 題的四個旋轉字串是精心設計的：ASCII 總和完全相同，所以第一種雜湊函式會全部碰撞。要看出這個結構才算得快。
第 9(3) 要跑完整的 Floyd-Warshall 才能得到五個距離值，計算量大且禁用計算器。

Master theorem「不適用」的辨識是成大的招牌（109 第 5 題、110 第 6 題連兩年），要能說出是哪一種不適用
一般 TSP vs metric TSP 的近似性差異務必分清楚
Shuffle 字串 DP（110 第 8 題）與 LCS 是同一族的二維 DP，轉移式要能推導
Floyd-Warshall 的遞推式 d^k[i][j] = min(d^k−1[i][j], d^k−1[i][k] + d^k−1[k][j]) 要能默寫，成大 110 直接考填空