113 中興資工所考古題詳解｜軟體考點分析

題型與配分

全卷 7 頁、28 題、100 分，簡章規定不可使用計算機。

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

• 第 1 題｜binary tree 存在 array 中，節點索引為 i 時，左子節點的位置公式
• 第 2 題｜N_H 是高度 H 的 AVL tree 的最少節點數，求 (N₃ − N₅) 在 8 位元 two's complement 下的位元樣式
• 第 3 題｜字串 bcaadddccacacac（15 個字元）的 Huffman 編碼後大小，題目假設頻率 f 需要 f 個 bit 來表示
• 第 4 題｜doubly linked list 插入一個節點，需要更改幾個 Next 與 Prev pointer
• 第 5 題｜依序把 6、3、5、2、4、7、1、9、8 插入 BST，求最深節點的總和
• 第 6–8 題｜同一棵 14 個節點的樹 T：第 6 題求 preorder traversal 第 6、8、11 個節點的和；第 7 題求 inorder traversal 第 7、9、13 個節點的和；第 8 題求 postorder traversal 第 3、8、10 個節點的和
• 第 9 題｜BST 中存有 1 到 100，搜尋 46 時，哪個序列可能是被檢查的節點序列
• 第 10 題｜C 程式的遞迴函式 FN(n)，n ≤ 3 回傳 n，否則回傳 FN(n−1) FN(n−2) FN(n−3)，輸出 FN(6)<2>2（卷面印的就是這個式子，兩個比較運算子相連，不是位移）
• 第 11 題｜哪種資料結構的插入平均需要超過常數時間
• 第 12 題｜merge sort 的最壞時間

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

• 第 13 題｜在未排序的 array 中找第 k 小的元素，哪個方法最有效率
• 第 14 題｜邊權為非負的 directed graph，從單一來源到其他所有頂點的 shortest path，哪個演算法最適合
• 第 15 題｜遞迴函式 mysteryFunction(n) 的時間複雜度，n ≤ 1 回傳 n，否則回傳 mysteryFunction(n−1) + mysteryFunction(n−2)
• 第 16 題｜幾乎已排序、只有兩個元素被交換過的 array，哪個排序演算法最有效率
• 第 17 題｜掛布條的地點各有時間窗，要讓時間窗不重疊的地點數最大，哪個 greedy 或 DP 策略適當
• 第 18 題｜3×7 的格子，機器人只能向下或向右移動，從左上到右下有幾條不同路徑
• 第 19 題｜隨機順序的整數清單，哪個排序演算法的時間複雜度最好
• 第 20 題｜Python 函式 maxSubArray 求整數 array 中連續 subarray 的最大和，填入兩個空格

B 申論題（26% + 10%，寫在答案卷）

資料結構（6 題）：

• 第 1 題（4%）｜int *ptr, a = 15; ptr = &a; *ptr += 2; 之後 printf("%d", *ptr * ++a) 的輸出
• 第 2 題（4%）｜三層 pointer int p = 3; int *q = &p; int **r = &q;，求 printf("%d", ++p * ++*q * ***r) 的輸出
• 第 3 題（4%）｜用 stack 求後置運算式 10, 7, 9, −, /, 6, 8, 5, +, *, % 的結果，運算子有加、減、乘、除、取餘數
• 第 4 題（4%）｜給一個 flow network，每條邊標示 flow/[capacity]，source 為 A、sink 為 J，求可行流 f 的值
• 第 5 題（4%）｜congruence equation 組 x ≡ 4 (mod 9)、x ≡ 7 (mod 15)，解為 x = at + b（t 為整數），求 a + b
• 第 6 題（6%）｜從節點 A 出發用 Prim's algorithm 求 MST，依加入順序列出所有邊，格式為 [node1, node2]

演算法（2 題）：

• 第 1 題（5%）｜依序把 [5, 3, 8, 2, 4, 7, 9] 插入 BST，求 postorder traversal 的結果
• 第 2 題（5%）｜假設 P ≠ NP，判斷五個問題屬於 P（答 1）、NP-hard 或 NP-complete（答 2）、兩者皆非（答 3）：graph coloring、矩陣乘法、traveling salesman problem、質數判定、數獨的決策版

作答時要注意的地方

1. 第 1–12 題答錯倒扣 0.5 分，第 13–20 題答錯不倒扣，同一份卷子兩種規則。
2. 第 6–8 題共用同一棵樹，各問一種 traversal 的指定位置。
3. 第 2 題要先求 AVL 最少節點數，再換成 8 位元 two's complement。
4. B-1 第 5 題是 congruence equation 組，要求的是 a + b。
5. 申論題寫在答案卷上。

準備方向

• binary tree 的 array 表示：113 第 1 題。
• AVL 的最少節點數：113 第 2 題，114 第 16–18 題有 B-Tree 與 red-black tree。
• Huffman 編碼：113 第 3 題，110 第 8-D 題、113 數學第 7 題也有。
• BST 的插入、traversal 與搜尋路徑：113 第 5–9 題與 B-2 第 1 題，111 第 3-VI 題、112 B 第 1 題、114 Part 2 第 3 題也有。
• 遞迴函式求值：113 第 10 題，109 第 6 題、110 第 7-D 題、111 第 3-VII 題、112 B 第 3、4 題也有。
• shortest path 演算法的選用：113 第 14 題，109 第 8 題、110 第 9-D 題、111 第 3-V 題、114 第 4 題也有。
• DP 與 greedy 法：113 第 17、18、20 題，110 第 9-A、9-B 題、114 第 3、8 題也有。
• 排序的複雜度與適用情形：113 第 12、16、19 題，109 第 9 題、110 第 8-B 題、111 第 1-I、1-II 題、114 第 1、2、7 題也有。
• C 語言的 pointer：113 B-1 第 1、2 題，108 第 1–5 題、110 第 6-A 題、112 PART 2-C 也有。
• flow network：113 B-1 第 4 題，110 第 8-C 題、112 D-II 題也有。
• congruence equation 組：113 B-1 第 5 題，115 數學第 5 題也有 Chinese remainder theorem。
• Prim 與 MST：113 B-1 第 6 題，110 第 7-A、9-C 題、111 第 2-III、3-IV 題、114 Part 2 第 4 題也有。
• P、NP-hard 的分類：113 B-2 第 2 題，111 第 1-IV、1-V 題、112 D-V 題、114 第 5 題也有。