113 中興資工所軟體考點分析

題型與配分

系所「資訊工程學系甲組」，科目：資料結構與演算法，全卷 7 頁、28 題、100 分，不可以使用計算機。

同一份考卷裡有兩種倒扣規則：前 12 題（2 分題）答錯倒扣 0.5 分，後 8 題（5 分題）不倒扣。進場要看清楚哪一區能猜。

A-1 資料結構選擇題（1–12，各 2 分，倒扣 0.5）

• 第 1 題｜二元樹存在陣列（索引 i）時左子節點的公式
• 第 2 題｜N_h 為高度 h 的 AVL 樹最少節點數，求 (N₅ − N₃) 在 8-bit 二補數下的位元樣式。同時考 AVL 的 Fibonacci 遞迴與二補數表示
• 第 3 題｜字串 bcaadddccacacac（15 字元）的 Huffman 編碼後大小（題目定義頻率 f 需要 f 個 bit 表示）
• 第 4 題｜雙向串列插入節點需要改幾個 Next 與 Prev 指標（2 Next, 2 Prev）
• 第 5 題｜依序插入 6, 3, 5, 2, 4, 7, 1, 9, 8 到 BST，求最深節點的總和
• 第 6–8 題｜同一棵 14 節點的樹，分別問 pre-order 的第 6、8、11 個節點、in-order 的第 7、9、13 個、post-order 的第 3、8、10 個節點值之和。三題共用一棵樹，走訪算錯就連錯三題
• 第 9 題｜BST 中存 1 到 100，搜尋 46 時哪個序列可能是被檢查的節點序列
• 第 10 題｜三重遞迴 FN(n) = FN(n-1)*FN(n-2)*FN(n-3)，求 FN(6) >> 2
• 第 11 題｜哪種資料結構的插入平均需要超過常數時間（search tree）
• 第 12 題｜merge sort 的最壞複雜度

A-2 演算法選擇題（13–20，各 5 分，不倒扣）

• 第 13 題｜找第 k 小元素最有效率的方法（用大小 k 的 max heap）
• 第 14 題｜非負權有向圖的單源最短路徑該用哪個演算法（Dijkstra）
• 第 15 題｜mysteryFunction 是 Fibonacci 遞迴，時間複雜度（O(2ⁿ)）
• 第 16 題｜「幾乎已排序、只有兩個元素交換過」的陣列，哪種排序最有效率（Bubble Sort —— 這題的答案在近乎有序時 bubble/insertion 才是 O(n)）
• 第 17 題｜掛布條的時間區段不重疊、要最大化數量 —— 哪種貪婪策略正確（最早結束時間優先）
• 第 18 題｜3×7 格子的機器人唯一路徑數（C(8,2) = 28）
• 第 19 題｜隨機順序整數清單哪種排序時間複雜度最好（Quick Sort）
• 第 20 題｜Kadane's algorithm 的填空（最大連續子陣列和）

B 申論題（26% + 10%）

資料結構（6 題）

1. （4%）｜*ptr += 2 後 printf("%d", *ptr * ++a) 的輸出 —— 指標與前置遞增的交互作用
2. （4%）｜三層指標 int **t = &q，求 ++p * ++*q * ***t 的輸出
3. （4%）｜用 stack 求後綴運算式 10,7,9,-,1,6,8,5,+,*,% 的值
4. （4%）｜給流網路（標示 flow/[capacity]），求可行流 f 的值
5. （4%）｜解同餘方程組 x ≡ 4 (mod 9)、x ≡ 7 (mod 15)，解為 x = at + b，求 a + b。這是中國剩餘定理
6. （6%）｜從 A 出發用 Prim 求 MST，依加入順序列出所有邊

演算法（2 題）

1. （5%）｜依序插入 [5, 3, 8, 2, 4, 7, 9] 到 BST，求 post-order
2. （5%）｜五個問題各屬於 P／NP-hard／兩者皆非：圖著色、矩陣乘法、TSP、質數判定（P，AKS 演算法）、數獨（決策版，NP-complete）

這份考卷的難點

1. 第 6–8 題共用一棵 14 節點的樹，而且問的是「第 n 個被走訪的節點值之和」，要完整寫出三種走訪序列再對照位置。合計 6 分，錯一個走訪就丟 6 分。
2. 第 2 題同時考兩個主題：AVL 最少節點數的 Fibonacci 遞迴（N_h = N_h−1 + N_h−2 + 1），再轉成 8-bit 二補數。
3. B-1 第 5 題的中國剩餘定理不是資料結構課的內容，屬於數論。
4. B-1 第 2 題的三層指標（++p * ++*q * ***t 全都指向同一個變數）要非常小心求值順序。

準備建議

• 注意兩種倒扣規則：前 12 題（2 分）倒扣 0.5、後 8 題（5 分）不倒扣 —— 後半一定要全部作答
• AVL 樹最少節點數的遞迴（N_h = N_h−1 + N_h−2 + 1）是高頻考點，中興 113、中正 114 都考
• 中國剩餘定理與二補數顯示中興會把離散數學／計算機組織的內容放進軟體考科
• 三種走訪的「第 n 個節點」問法是中興特有，練習時要習慣寫出完整序列