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

題型與配分

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

第 1、12、13、14 題是 C/C++ 語法與程式題，合計 50 分。

逐題考點

第 1 題（25%）｜C++ 語法，11 個小題，選最適當的答案

• 第 1.1 題（2%）｜cout 是什麼
• 第 1.2 題（2%）｜哪一個是布林型別 bool 的正確用法
• 第 1.3 題（2%）｜類別的 private 成員在哪裡可以存取
• 第 1.4 題（2%）｜四個函式（reference、pointer、const reference）哪些能讓傳入的 double 遞增
• 第 1.5 題（2%）｜new int[100] 對應的 delete 寫法
• 第 1.6 題（2%）｜三個含預設引數的函式宣告哪些正確
• 第 1.7 題（2%）｜copy constructor 在哪些情況下被呼叫
• 第 1.8 題（2%）｜pure virtual function 的定義寫法
• 第 1.9 題（3%）｜cin >> i >> d >> c >> str 搭配輸入 30 40 King Dome（開頭有空白），cout << str 的結果
• 第 1.10 題（3%）｜兩個 reference 參數的函式 f(int& p1, int& p2) 以同一個變數呼叫，判斷輸出
• 第 1.11 題（3%）｜ifstream 讀整數時檔案內容是字元 x，哪一段程式碼能正確偵測錯誤

資料結構與演算法

• 第 2 題（8%）｜依序插入 65, 50, 80, 70, 60, 62, 90, 10 建 BST，節點多一個 leftSize 欄位（左子樹節點數加 1）。(a) 3%：畫出樹並標出每個節點的 leftSize。(b) 5%：說明如何用 leftSize 在 O(log n) 找到第 k 小的元素
• 第 3 題（6%）｜依序插入 7, 16, 49, 82, 5, 31, 6, 2, 44 建 max heap。(a) 3%：插入完成後的狀態。(b) 3%：heap sort 第 5 次迭代後的 heap 與已排序 array
• 第 4 題（4%）｜給一張有邊權的 directed graph。(a) 2%：Dijkstra 從頂點 0 出發處理頂點的順序。(b) 2%：從頂點 0 做 BFS，遇到選擇時先選最小邊
• 第 5 題（2%）｜17 格 hash table，h(k) = k % 17，用 linear probing，依序插入 6, 12, 34, 29, 28, 11, 23, 7, 0, 33，填出最後的表
• 第 6 題（5%）｜(a) 2%：高度 h 的 k 元樹最多有幾個節點。(b) 3%：證明 (a) 的答案
• 第 7 題（6%）｜三個是非題，答錯要改正錯誤的部分，單純否定不給分。(a) 任意多條輸入序列的 LCS 是否為 P 問題。(b) 非負權圖上兩點間的 longest simple path 是否為 NP-hard。(c) BFS 是否能 traverse 並分類圖中所有的邊
• 第 8 題（5%）｜哪些排序演算法是 stable 的：counting sort、quicksort、mergesort、insertion sort、heapsort。每答錯一個選項額外倒扣 1 分，最多扣到 5 分
• 第 9 題（8%）｜bubble sort、quicksort、mergesort、heapsort 各自是不是漸進最佳（asymptotically optimal）
• 第 10 題（1%）｜給一個含負權值的矩陣，問這是 directed graph 的哪一種表示法
• 第 11 題（5%）｜承第 10 題的圖，Johnson 演算法對這張圖做了什麼、結果為何，要寫出過程

C 程式

• 第 12 題（10%）｜(a) 3%：if ... if ... else 的程式輸出。(b) 7%：含 struct node（char pointer、double、long long）的程式，輸出 sizeof(struct node)、sizeof(short) 與一個字串
• 第 13 題（7%）｜修正一段使用 strcpy 的程式，使輸出為 AppleAppleApple
• 第 14 題（8%）｜(a) 2%：指出 array A 宣告的錯誤。(b) 6%：迴圈執行後 A 的最終內容

作答時要注意的地方

1. 第 8 題每答錯一個選項額外倒扣 1 分，最多扣到 5 分，是這份卷子唯一標明倒扣的地方。
2. 第 7 題答錯時要改正錯誤的部分，單純否定不給分。
3. 第 11 題要寫出過程。
4. 第 2 題要求用額外的 leftSize 欄位，時間複雜度為 O(log n)。

準備方向

• C/C++ 語法與程式題佔 50 分（108 第 1、12、13、14 題）：reference 與 pointer、預設引數、copy constructor、pure virtual、cin 的行為、結構大小。
• 程式除錯（108 第 13 題），109 第 4 題、110 第 13 題、115 第 2 題也有。
• 排序的 stability 與漸進最佳（108 第 8、9 題），漸進最佳在 111 第 18 題、112 第 10(a) 題也有。
• Dijkstra 的頂點順序（108 第 4 題），107、110、111、113、115 也有。
• Johnson 演算法與 reweighting（108 第 11 題），107 第 12 題、110、111、112 也有。
• Max heap 與 heap sort（108 第 3 題），111 第 12 題、112 第 9(2) 題、114 第 3 題也有。
• Hash 的 linear probing（108 第 5 題），111 第 13 題、115 第 15 題也有。
• P、NP 與 NP-hard 的是非判斷（108 第 7 題），109 第 13(5) 題、114 第 6 題也有。
• BFS 與 DFS 的 traversal（108 第 4、7 題），110、111、115 有 DFS 與 articulation point，112 第 9(1) 題考 DFS traversal 序列。