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

題型與配分

全卷 5 頁、16 題、100 分。卷面沒有倒扣規定。第 10 題的是非題答錯要改正錯誤的部分，單純否定不給分。

第 1、2、3、14、15、16 題是 C/C++ 題，合計 50 分。

逐題考點

C/C++

• 第 1 題（8%）｜八個敘述，各自判斷是 (a) 沒有錯誤、(b) 編譯錯誤或 (c) undefined behavior，每小題 1 分：int *p = 0;、cout << *p << endl;、p = new int [10];、int *q = p + 3;、cout << p - q << endl;、p[10] = 0;、q = 4;、delete p;
• 第 2 題（2%）｜單選，每小題 1 分。2.1：關於類別的敘述哪一項為真（資料成員與方法、private 與 public、constructor 名稱、方法原型）。2.2：null terminator 是什麼（換行、'\0'、字串結尾）
• 第 3 題（15%）｜十五個是非題，每小題 1 分：derived class 能否存取 inheritance 來的 private 成員、derived class constructor 是否該初始化 inheritance 的成員、不是 virtual 能不能 override、derived class 預設的 assignment operator、空的 virtual destructor、override 的參數、base class pointer 指向 derived 物件、derived class constructor 是否 override base class constructor、virtual 是否增加每個物件的大小、純 virtual function 與 abstract class、abstract class B 的物件、B& 參數與 B* pointer、類別 A 宣告為類別 B 的成員時 B 是不是 base class、A 能不能存取 B 的 protected 成員
• 第 14 題（9%）｜char A[9] 全部設 0，A[0]='a' 後印出；迴圈 A[i] = A[i-1] + i（i = 1 到 4）後印出；p = &A[2]，reverse(p, 5) 後印出 p。reverse(char s[], int n) 的迴圈是 for (i=1; i<n/2; i++)，交換 s[i] 與 s[n-i-1]
• 第 15 題（8%）｜程式名為 prog，以 prog 1 2 3 4 5 執行，text[] = "sweetapplepie"，迴圈 strcat(text, argv[argc-i-1])，再 text[len<<1] = '\0'，以 "%s\t%d\t%s\n" 輸出 argv[0]、argc、text
• 第 16 題（8%）｜A = 500、B = 300，寫出 swap 函式並填入呼叫的引數，使輸出為 300, 500

資料結構與演算法

• 第 4 題（2%）｜卷上的 BST：根 5，左子 3（3 的右子 4），右子 9（9 的左子 7、右子 12，7 的左右子 6、8，12 的右子 20），五個插入序列中哪一個建不出這棵樹
• 第 5 題（3%）｜array {50, 35, 40, 25, 20, 33, 27} 組成 max heap，做兩次 deleteMax 之後的 array
• 第 6 題（6%）｜directed graph：A→B 2、A→D 8、B→C 3、B→E 5、D→C 1、C→F 6、E→F 4。(a) 2%：從 A 跑 Dijkstra，列出處理頂點的順序。(b) 2%：從 A 做 DFS，有選擇時先走最小的邊。(c) 2%：topological sort，要說明做法
• 第 7 題（3%）｜十個頂點 A–J、19 條邊的 undirected graph，用 Kruskal 求 minimum spanning tree，依找到的順序列出邊
• 第 8 題（2%）｜((2+2)3)((3−1)*2) 的 postfix
• 第 9 題（9%）｜依序插入 50, 80, 20, 100, 60, 95, 52, 90, 62, 70, 120, 66, 85, 68, 87, 64。(a) 4%：畫出 BST。(b) 5%：刪除 80，在樹上標出操作、簡述過程，再畫出刪除後的樹
• 第 10 題（6%）｜三個是非題，每題 2 分，答錯要改正錯誤的部分，單純否定不給分。(a) X 可以 reduction 到已知的 NP-hard 問題，X 是否一定是 NP-hard。(b) T(n) = 8T(n/2) + Θ(n²√n) 的解是否為 Θ(n³)。(c) 用 DFS 探索圖是否也能得到從起點出發的 shortest path
• 第 11 題（3%）｜Fig. 11 是 a、b、c、d 四個點、邊雙向的正方形，找 a 到 d 邊數最多的 simple path，問這個問題有沒有 optimal substructure，要證明或舉反例
• 第 12 題（6%）｜Fig. 12：a→b 6、a→c 3、b→d 2、c→d 5、d→c −3、d→a −7。(a) 4%：在不改變原本 shortest path 性質的前提下，把 negative-weight edge 轉成非負。(b) 2%：a、b、c、d 各代表一群頂點與邊、整張圖是 sparse graph 時，哪一種方法偵測 negative cycle 比較有效率
• 第 13 題（10%）｜Fig. 13.1 是已標上部分 discovery time 的六點 directed graph，Fig. 13.2 是以 a 為起點、其餘距離為 ∞ 的六點 undirected graph。(a) 4%：接續兩張圖的 traversal，畫出產生的樹。(b) 2%：兩種 traversal 方法的名稱。(c) 4%：兩張圖各做 topological sort，能做就寫出結果，不能做要說明原因

作答時要注意的地方

1. 卷面沒有倒扣規定。
2. 第 10 題答錯要改正錯誤的部分，單純否定不給分。
3. 第 6(b) 題有選擇時先走最小的邊，第 6(c) 題要說明做法。
4. 第 9(b) 題要在樹上標出操作、簡述過程，再重畫刪除後的樹。
5. 第 11 題要證明或舉反例，第 13(c) 題不能做 topological sort 時要說明原因。

準備方向

• C/C++ 題佔 50 分（107 第 1、2、3、14、15、16 題）：pointer 與 undefined behavior、inheritance 與存取權限、virtual function 與 abstract class、字串操作、命令列參數。
• 編譯錯誤與 undefined behavior 的判斷（107 第 1 題），115 第 2 題也要找出造成錯誤輸出或 undefined behavior 的原因。
• swap 函式（107 第 16 題），106 第 6 題也有。
• 負權圖 reweighting（107 第 12 題），108 第 11 題考 Johnson，110 第 11 題、111 第 19 題、112 第 11(d) 題也有 reweighting。
• Dijkstra 頂點順序（107 第 6(a) 題），108、110、111、113、115 也有。
• topological sort（107 第 6(c)、13(c) 題），112、113、114 也有。
• 是非題答錯要改正（107 第 10 題），108 第 7 題、109 第 13 題也有同樣的規定。
• optimal substructure（107 第 11 題），110 第 10、12 題、114 第 9 題也有；longest simple path 在 108 第 7(b) 題、114 第 7 題也有。
• BST 的建立與刪除（107 第 4、9 題），108 第 2 題、110 第 14 題也有 BST。
• Kruskal（107 第 7 題），113 第 23 題、114 第 10 題也出現 Kruskal。
• 運算式轉 postfix（107 第 8 題），109 第 8 題也有，113、115 考 prefix 與 expression tree。
• Max heap（107 第 5 題），108 第 3 題、111 第 12 題、112 第 9(2) 題、114 第 3 題也有。