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

題型與配分

全卷 6 頁、20 題、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。

第 2–9 題是 C/C++ 題，合計 48 分。

逐題考點

• 第 1 題（2%）｜2,000 個元素的 array 做 binary search，最多需要幾次比較
• 第 2 題（2%）｜哪一個運算式給出 int r[] 的元素個數
• 第 3 題（2%）｜pointer bPtr 指向 array b 時，b[3] 對應哪一個 pointer 運算式
• 第 4 題（2%）｜在 4 byte 的 int 上做 x <<= 1; x >>= 1; 的效果
• 第 5 題（2%）｜遞迴函式 mystery(4) 的回傳值
• 第 6 題（15%）｜用 C 手寫 int reverse(int x)，把 32 位元有號整數的各位數反轉，反轉後超出 [−2³¹, 2³¹−1] 就回傳 0。題目給 123、−123、120 三個範例
• 第 7 題（14%）｜把 constructor、destructor、data member、member function、private、public、recursive 七個名詞與九段描述配對
• 第 8 題（10%）｜string 物件與動態配置的 char* 字元 array，各判斷五項性質的真假：能否含有 null 字元、記憶體是否自動釋放、字元能否修改、能否在常數時間存取第 k 個字元、= 是否做 deep copy
• 第 9 題（1%）｜C++ template 讓程式碼可以做什麼，選一個答案
• 第 10 題（3%）｜依序插入 51, 26, 11, 6, 8, 4, 7 建 AVL tree，選出對應的 array 表示
• 第 11 題（3%）｜給 post-order 序列 E D A C G F B H 與各節點的子節點數，問樹是否唯一，並求 pre-order
• 第 12 題（3%）｜把 45, 83, 7, 61, 12, 99, 44, 77, 14, 29 建成 max heap，問 heap sort 第二階段（連續輸出前兩大的數）之後 array 的樣子
• 第 13 題（2%）｜表長 11（索引從 0 開始）、除法 hash、linear probing，依序插入 25, 42, 96, 101, 102, 162, 197, 201，選出對應的表
• 第 14 題（3%）｜給一棵以 P(C1, C2) 格式表示的樹，畫出樹並轉成 binary tree，問 binary tree 的 post-order
• 第 15 題（3%）｜把給定的運算式轉成 prefix 形式
• 第 16 題（4%）｜給一張八個頂點（A–H）的圖，從頂點 B 開始 DFS，同層選字母順序最小的先走，dfn 從 1 開始。16.1（1%）深度優先 spanning tree 的邊；16.2（2%）各頂點的 low；16.3（1%）articulation point
• 第 17 題（4%）｜給一張有 10 個事件、14 個活動的 directed graph。17.1（2%）critical path；17.2（2%）以邊上時間為權重，從頂點 1 跑 Dijkstra 的頂點選取順序
• 第 18 題（4%）｜論證 (a) quicksort、(b) mergesort 是不是漸進最佳，並寫出理由
• 第 19 題（17%）｜給一張 directed graph。(a) 2%：指定起點跑 Dijkstra 的輸出，寫出理由。(b) 4%：reweighting。(c) 8%：用 Floyd-Warshall 推出距離矩陣與前驅矩陣，寫出推導過程。(d) 3%：給另一張圖 G，怎麼判斷 Floyd-Warshall 與 Johnson 演算法哪個在理論上比較快
• 第 20 題（4%）｜給七個符號與機率（0.25、0.2、0.15、0.14、0.13、0.08、0.05），求最佳的三元 Huffman 編碼

作答時要注意的地方

1. 第 6 題是手寫程式，題目指定用 C 寫 int reverse(int x)。
2. 第 7 題要把 A–G 與 0–8 的描述配對，每格填一個 0 到 8 的數字。
3. 第 16 題的 DFS 從頂點 B 開始。
4. 第 18 題與第 19(a)(c) 要寫出理由或推導過程。

準備方向

• C/C++ 觀念題：sizeof、pointer 與 array、位元移位（111 第 2、3、4 題），位元運算在 114 第 13 題、115 第 5 題也有。
• 手寫 C 程式（111 第 6 題），109 第 5–7 題、110 第 14 題、115 第 25 題也有。
• 物件導向名詞配對（111 第 7 題），113 第 14 題、114 第 14 題也有配對題。
• template（111 第 9 題），115 第 9 題也有。
• articulation point 的 dfn 與 low（111 第 16 題），110 第 3 題、115 第 17–19 題也有。
• AOE 網路的 critical path（111 第 17.1 題），115 第 21 題用同一張圖。
• Dijkstra 的頂點選取順序（111 第 17.2 題），107、108、110、113、115 也有。
• 負權圖與 reweighting（111 第 19 題），107 第 12 題、110 第 5、11 題、112 第 11 題也有，108 第 11 題考 Johnson。
• 排序是否漸進最佳（111 第 18 題），108 第 9 題、112 第 10(a) 題也有。
• Hash 與 linear probing（111 第 13 題），108 第 5 題、115 第 15 題也有。
• Heap sort 的逐階段 array（111 第 12 題），108 第 3 題、112 第 9(2) 題、114 第 3 題也有。
• Huffman 編碼（111 第 20 題，三元），106 第 10(d) 題問建 Huffman 編碼該用哪一種演算法。