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

題型與配分

全卷 7 頁、23 題、100 分。第 1 至第 9 題要在第一頁的選擇題作答區作答，否則不予計分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。

第 10–14 題是 C/C++ 題，合計 50 分。

逐題考點

• 第 1 題（3%）｜給一棵以 array 表示的 AVL tree（節點為 65、40、70、35、50、80、45、55），插入鍵值 43 後的 array 表示，空位用 _ 表示
• 第 2 題（3%）｜承第 1 題插入後的 AVL tree，postorder traversal 的節點序列
• 第 3 題（3%）｜承第 1 題插入後的 AVL tree，刪除鍵值 65 後的 array 表示
• 第 4 題（3%）｜給運算式 B - E/(A-D) + E + C*D - A*B，畫出 expression tree 並求 level-order traversal。運算子優先順序相同時，依出現的順序先算
• 第 5 題（3%）｜同一個運算式的 prefix 形式
• 第 6 題（3%）｜給 KMP 的 failure function 定義與長度 12 的字串 AAABAAAABAAA，求整串的 failure 值
• 第 7 題（3%）｜給 in-order（A, B, G, E, D, I, J, F, H, C）與 post-order（G, E, J, I, H, F, D, C, B, A），重建 binary tree 並寫出 pre-order
• 第 8 題（2%）｜給一張 directed graph，以邊上的值為權重，從頂點 A 跑 Dijkstra 的頂點選取順序
• 第 9 題（2%）｜同一張圖的 topological sort，有多個選擇時先選字母順序最小的節點
• 第 10 題（10%）｜num = 250，printf("%X\n", num) 與 printf("%.2f\n", (float)num) 兩項輸出，各 5 分
• 第 11 題（10%）｜array {10,20,30,40,50}，迴圈中令 ptr = &arr[i]，i 為偶數時累加 *ptr，求輸出的 sum
• 第 12 題（5%）｜fun1(char *str) 用兩個 pointer 把字串反轉，主程式用 "13579" 呼叫後 atoi(str)，輸出 number % 10
• 第 13 題（5%）｜補完一段求「某整數的最大因數」的 C++ 程式，只能填空，不可新增區塊。(A) 2%：讀入整數的敘述。(B) 3%：while 迴圈條件
• 第 14 題（20%）｜把 function declaration、if-else statement、break statement、pass by value、local variable、void、float、cast、promotion、overloaded function 十個詞與十段描述配對，每格填 1 到 10 的數字
• 第 15 題（2%）｜recurrence T(n) = 3T(n/5) + n 的解，五個選項
• 第 16 題（2%）｜recurrence T(n) = 4T(n/4) + n log n 的解，五個選項
• 第 17 題（2%）｜recurrence T(n) = 4T(n/2) + n³ 的解，五個選項
• 第 18 題（2%）｜是非題：directed graph 中 s-t min cut 的值是否沒有多項式時間演算法
• 第 19 題（2%）｜是非題：merge sort 的 Merge 與 quicksort 的 Partition 是否都是線性時間
• 第 20 題（2%）｜是非題：在 comparison model 下，找 n 個元素的 median 是否需要 Ω(n log n) 時間
• 第 21 題（2%）｜是非題：T 是圖 G 的 minimum spanning tree 時，任兩點 s、t 之間的 shortest path 是否就是 T 上 s 到 t 的路徑
• 第 22 題（3%）｜給一張六個頂點的 flow network 與目前的流量分配（x/y 表示容量 y 的邊上有 x 單位的流），判斷是否已達 max flow。是的話說明如何得到這個流，不是的話算出 max flow
• 第 23 題（8%）｜給一張有五個頂點、含 negative-weight edge 的圖，判斷下列演算法（a）Kruskal、（b）Dijkstra、（c）Ford-Fulkerson、（d）Johnson、（e）Bellman-Ford、（f）Jarvis's march、（g）Floyd-Warshall、（h）Huffman 能不能用來找指定頂點對的 shortest path

作答時要注意的地方

1. 第 1 至第 9 題要在第一頁的選擇題作答區作答，否則不予計分。
2. 第 10、11、12 題是中文題目，要求寫出程式執行後螢幕上顯示的結果。
3. 第 13 題只能填空，不可新增區塊。
4. 第 4 題運算子優先順序相同時，依運算式中出現的順序先算。

準備方向

• AVL tree 的插入與刪除（113 第 1–3 題），109 第 10 題、111 第 10 題、112 第 9(3) 題、114 第 1 題也有 AVL。
• expression tree 與 prefix、postfix 轉換（113 第 4、5 題），107 第 8 題、109 第 8 題、111 第 15 題、115 第 20 題也有。
• KMP failure function（113 第 6 題），109 第 11 題、110 第 6 題、115 第 22 題也有。
• 由 in-order 與 post-order 重建 binary tree（113 第 7 題），110 第 4 題、115 第 23 題用同一組序列。
• Dijkstra 的頂點順序（113 第 8 題），107、108、110、111、115 也有。
• printf 格式與 pointer 輸出（113 第 10、11、12 題），112 第 1(a) 題、114 第 11、12、13 題也有。
• 名詞配對（113 第 14 題，20 分），111 第 7 題、114 第 14 題也有。
• recurrence 的解（113 第 15–17 題），110 第 7、8 題、114 第 8 題也有。
• min cut 與 flow network（113 第 18、22 題），109、112、114、115 也有 max flow。
• shortest path 演算法的適用條件（113 第 23 題），110、111、112 也有負權圖題目。