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

題型與配分

全卷 5 頁、13 題、100 分。卷面沒有倒扣規定。

第 1–8 題是 C/C++ 題，合計 50 分；第 13 題用 C 手寫 BST，15 分。

逐題考點

C/C++

• 第 1 題（5%）｜哪一個 C 敘述能產生 10 到 15 之間的整數亂數，選項是 (rand() % 15)+11、(rand() % 16)+10、(rand() % 5)+11、(rand() % 6)+10 與以上皆非
• 第 2 題（5%）｜for 迴圈跑 i = 0 到 32，i%3==0 時 continue，否則 count++，輸出 count
• 第 3 題（5%）｜全域變數 int x=1，函式 func(int x) 回傳 x++，輸出 func(x) 與 x
• 第 4 題（5%）｜int s[5]={5,4,3,2,1}，p=s、ptr=s+2，輸出 *p+2、*ptr、s[0]、*p++、*p
• 第 5 題（5%）｜Tower of Hanoi 函式 hanoi(N, from, to, using) 內有 static int count，輸出 hanoi(5, A, C, B)
• 第 6 題（5%）｜交換兩個整數。(a) 2%：寫出符合 swap(&a, &b) 呼叫的 C 函式。(b) 3%：改成 C++ 的 swap(a, b) 呼叫，寫出對應的 C++ 函式
• 第 7 題（5%）｜10×10 的 double array 原地 transpose，外迴圈 i 從 1 到 9、內迴圈 j 從 0 到 i−1，填入迴圈內的程式碼，不能新增區塊
• 第 8 題（15%）｜class A 的 constructor 設 a = 1，B、C 都 public inheritance A，constructor 分別做 a += 2、a *= 3，D inheritance B 與 C，main 輸出 d->a。(a) 2%：編譯器拒絕這段程式的原因。(b) 4%：只改類別宣告、不拿掉 inheritance 關係，修正問題。(c) 4%：修正後的輸出。(d) 5%：A 加上 virtual int get()，再加 class X : public A 與 class Y : public D, public X，新的 main 以 B *b = y 指派 b->a 後 assert(b->a == y->get())，只能在 class Y 內加程式碼，讓程式通過編譯且 assert 成立

資料結構與演算法

• 第 9 題（12%）｜給參數 k、固定成本的亂數產生函式 RDG(k) 與輸入大小 n，pseudo-code SEGMENT(n, k) 共 9 行：第 1–2 行 if n < 1 return NIL；第 3–5 行 for i = 1 to n、for j = 1 to ∛n 呼叫 RDG(k)；第 6–9 行 if n ≥ 1 時 for i = 1 to 100 呼叫 SEGMENT(⌈n/10⌉, k)。(a) 7%：寫出 recurrence（含 base case）。(b) 5%：用 Θ 表示解
• 第 10 題（8%）｜從 Dijkstra、DFS、greedy 法、Bellman-Ford、DP 中，為下列問題各選最合適的一個，每小題 2 分。(a) 含 negative-weight edge 的 single-source shortest path。(b) topological sort。(c) fractional knapsack。(d) 建 Huffman 編碼
• 第 11 題（5%）｜證明或舉反例否定：給 n 個相異的數，任何 comparison sort 在最壞情況下至少要 n log n 次比較
• 第 12 題（10%）｜時間複雜度簡答，每小題 2 分。(a) quicksort 的最壞情況。(b) heapsort 的平均情況。(c) selection sort 的最佳情況。(d) 在已排序的 linked list 中搜尋的平均情況。(e) 在 2-3 tree 中搜尋的最壞情況
• 第 13 題（15%）｜用 C 寫程式，以 fgets(char *line, int MaxLine, stdin) 逐行讀入關鍵字建 BST，再用 InorderTraversal 印出。例子是輸入 banana、apple、day、candy。提示要宣告 BST 節點的資料結構，程式可以包含 main()、BST_Insert()、InorderTraversal() 三個函式

作答時要注意的地方

1. 卷面沒有倒扣規定。
2. 第 7 題指定不能新增區塊，只填迴圈內的程式碼。
3. 第 8(b) 題限定只改類別宣告、不能拿掉 inheritance 關係，第 8(d) 題限定只能在 class Y 內加程式碼。
4. 第 9 題的 recurrence 要包含 base case。
5. 第 13 題要自己宣告節點結構，輸入用 fgets 讀取。

準備方向

• C/C++ 題佔 50 分，另有 15 分的手寫程式（106 第 1–8、13 題）：rand() 的範圍、pointer 與 array、static 區域變數、函式參數與同名全域變數、C 與 C++ 的 swap 寫法、multiple inheritance。
• swap 函式（106 第 6 題），107 第 16 題也要寫 swap 並補上呼叫的引數。
• 手寫 BST 程式（106 第 13 題），110 第 14 題手寫 BST 搜尋函式；109 第 7 題也指定用 fgets() 從 stdin 讀資料。
• recurrence 求解（106 第 9 題），110、113、114 也有。
• comparison sort 的下界（106 第 11 題），112 第 8 題的是非題也有。
• 時間複雜度與排序（106 第 11、12 題），108–115 每年都有排序題。
• 為問題選演算法（106 第 10 題）：fractional knapsack 在 110 第 12 題也有，111 第 20 題考三元 Huffman 編碼。
• 2-3 tree（106 第 12(e) 題），114 第 2 題考 2-3-4 tree 與 B-tree 的關係。