114 中正資工所軟體考點分析

題型與配分

系所組別「資訊工程學系－甲組」，科目名稱：軟體設計，全卷 5 頁、15 題、100 分。

前 10 題多為「Select multiple correct answers」，依中正慣例為全對才給分。

逐題考點

選擇題部分（1–10，各 5%）

• 第 1 題｜100 個節點的 AVL 樹可能的高度有哪些（提示給了 log₁₀2 ≈ 0.3010）。要同時算出最小高度（⌈log₂101⌉）與最大高度（用 Fibonacci 遞迴 N(h)）
• 第 2 題｜樹的性質：2-3-4 tree 是否為 order 5 的 B-tree、紅黑樹是否為 2-3 tree 的二元形式、B-tree 的外部節點是否同層、order m 的 B-tree 內部節點的子節點數下界。與成大 112 第 6 題幾乎相同
• 第 3 題｜{52, 21, 40, 33, 88, 57, 46, 71} 用 bottom-up O(n) heapify 成 max heap 的結果
• 第 4 題｜依序插入 40, 60, 55, 15, 20, 5, 25, 30 到紅黑樹，求紅節點的數字總和
• 第 5 題｜{52, 21, 40, 88, 33, 57, 46, 71} 用雙指標版 quicksort，pivot 52 移到正確位置後的陣列
• 第 6 題｜理論綜合：稠密圖上 Johnson 是否快於 Floyd-Warshall（否）、NP 是否包含多項式時間可解的問題（是，P ⊆ NP）、停機問題是否為 NP-hard（是）、Ford-Fulkerson 能否求最大匹配、該圖的最大匹配數
• 第 7 題｜insertion sort 是否 in-place、無權圖的最長簡單路徑能否用分治解（否）、遞迴樹是否為 full binary tree、quicksort 是否非漸進最佳、程式碼行數少是否複雜度就低（明顯為否）
• 第 8 題｜五條遞迴式的解，包含 T(n) = 2T(√n) + √(log n)（要換元）與 T(n) = T(n−1) + 1/n（調和級數，解是 O(log n)）
• 第 9 題｜多階段圖（multistage graph）的最短路徑：貪婪是否適用（否）、DP 是否適用（是）、是否具最佳子結構、最小權重是多少
• 第 10 題｜給一張圖：Kruskal 是否適用、Floyd-Warshall 與 Bellman-Ford 的執行時間比較、指定 A 為源點 D 為匯點時 Edmonds-Karp 的回傳值、拓撲排序是否適用、B/C/E/F 是否構成強連通元件

C／C++ 部分（11–15，共 50%）

• 第 11 題（5%）｜int num1 = 025;（八進位，值為 21），求 printf("%X", num2) 的輸出（15）
• 第 12 題（10%）｜const int *p1（指向常數的指標）與 int *const p2（常數指標）傳入函式後 *ptr2 *= 2，求 a 與 b 的值（10, 40）。考的是兩種 const 的差別
• 第 13 題（10%）｜unsigned int a = 0xFFFF0101，取 (unsigned char)a、用 char* 指向 a、再透過 unsigned int* 做 *p <<= 6，求 printf("%x,%x", b, *c) 的輸出。要同時掌握型別轉換、小端序（little-endian）與位移
• 第 14 題（9%）｜概念配對：overloading（同名多物）、coercion（自動轉型）、aliasing（同物多名）、polymorphism（處理多型別）
• 第 15 題（16%，8 小題各 2%）｜類別 B 有 virtual void m(int) 與 virtual void m(double) 兩個多載，衍生類別 D 只覆寫 m(int)。對 D* dP、B* bP、B& br、B bo（物件切片）四種存取方式各呼叫 m(1) 與 m(2.0)，問八行各印出什麼。
• 關鍵三點：(1) D 覆寫 m(int) 會隱藏（hide） B 的 m(double)，所以 dP->m(2.0) 會呼叫 D 的 m(int) (2) 透過 B*／B& 呼叫是動態繫結，m(double) 仍會走 B 的版本 (3) B bo = *dP 發生物件切片，全部走 B 的版本

這份考卷的難點

1. 第 15 題（16 分）是全卷最硬的一題，同時牽涉名稱隱藏、函式多載解析、虛擬函式的動態繫結、物件切片四個 C++ 機制，任何一個沒掌握就會大量失分。
2. 前 10 題全對才給分，每題 5 分，而且多數是五選項複選 —— 50 分的區塊容錯率極低。
3. 第 13 題的位元題需要知道 x86 的小端序：char *c = (char*)&a 指向的是最低位元組。
4. 第 1 題的 AVL 高度範圍要同時算上下界，下界用滿樹、上界用 Fibonacci 型遞迴 N(h) = N(h−1) + N(h−2) + 1。

準備建議

• C++ 的名稱隱藏（name hiding）是最常被忽略的機制：衍生類別只要定義了同名函式，基底類別的所有同名多載都會被隱藏
• 兩種 const 指標（const int* vs int* const）在中正 110、112、114 連三次出現，務必分清楚
• AVL 樹的最大高度（Fibonacci 型遞迴）與最小高度要能算，114 第 1 題直接考
• 「NP 包含 P」「停機問題是 NP-hard 但不是 NP-complete」這兩個結論在中正 114 與成大 115 同時出現