114 年 國立中正大學資訊工程學系碩士班甲組《軟體設計》

核心觀念

AVL 樹中，任一節點的左右子樹高度差至多為 $1$。題目採用葉節點高度為 $1$，因此高度為 $h$ 的 AVL 樹，其最少節點數 $N(h)$ 滿足：

$$N(0)=0,\qquad N(1)=1$$ $$N(h)=1+N(h-1)+N(h-2)$$

高度為 $h$ 的二元樹最多有 $2^h-1$ 個節點。

解題方法

先算出 AVL 樹各高度的最少節點數：

高度 $h$	$N(h)$：最少節點數	最多節點數 $2^h-1$
5	12	31
6	20	63
7	33	127
8	54	255
9	88	511
10	143	1023

高度為 $5$ 或 $6$ 的樹最多分別只有 $31$、$63$ 個節點，無法容納 $100$ 個節點。高度為 $10$ 的 AVL 樹至少需要 $143$ 個節點，超過題目給定的 $100$ 個。

因此只需確認高度 $7$、$8$、$9$ 都能容納恰好 $100$ 個節點。固定高度的 AVL 樹可達成從最少節點數到最多節點數之間的每個整數節點數；以下各高度的子樹配置也能直接構成 $100$ 個節點：

核心觀念

本題考查 2-3-4 樹、紅黑樹與 B-tree 的對應關係，以及 B-tree 的階數與平衡性質。

採用常見定義：階數為 $m$ 的 B-tree，單一節點最多有 $m$ 個子節點。因此，除根節點外，每個內部節點至少有 $\lceil m/2\rceil$ 個子節點；所有外部節點都在同一層。

解題方法

逐項套用定義即可：

• 先由最大子節點數判斷 2-3-4 樹的階數。
• 再確認紅黑樹對應的是 2-3 樹還是 2-3-4 樹。
• 最後檢查 B-tree 的葉節點平衡性與非根內部節點的最小子節點數。

選項分析

(A) 錯誤。
2-3-4 樹的節點最多有 $4$ 個子節點，因此按 B-tree 階數的常見定義，它是階數為 $4$ 的 B-tree，不是階數為 $5$ 的 B-tree。

核心觀念

Max Heap（最大堆積）是一種完全二元樹，且每個父節點的值都大於或等於其子節點。陣列以層序儲存時，若採 1 起始索引，索引 $i$ 的左右子節點分別是 $2i$、$2i+1$。

題目指定使用自底向上的建堆法：從最後一個非葉節點 $\lfloor n/2 \rfloor$ 開始，依序對每個節點執行向下調整（sift-down），直到根節點。此方法的時間複雜度為 $O(n)$。

解題方法

原陣列共有 $8$ 個元素，最後一個非葉節點的索引為 $\lfloor 8/2 \rfloor=4$。依序調整索引 $4$ 到 $1$：

1. 調整索引 $4$：值為 $33$，子節點索引 $8$ 的值為 $71$。交換後，陣列為 $\{52,21,40,71,88,57,46,33\}$。
2. 調整索引 $3$：值為 $40$，子節點為 $57$、$46$。與較大的子節點 $57$ 交換，陣列為 $\{52,21,57,71,88,40,46,33\}$。
3. 調整索引 $2$：值為 $21$，子節點為 $71$、$88$。與較大的子節點 $88$ 交換，陣列為 $\{52,88,57,71,21,40,46,33\}$。
4. 調整索引 $1$：值為 $52$，子節點為 $88$、$57$。

核心觀念

紅黑樹插入（CLRS 版本）：新節點一律塗紅色；若父節點也是紅色就要修正：

• 叔叔為紅：父、叔改黑，祖父改紅，再以祖父繼續往上檢查。
• 叔叔為黑：以旋轉修正。新節點與父節點「同側」做一次旋轉；「異側」先旋轉父節點變成同側，再旋轉祖父；最後新的子樹根塗黑、兩個子節點塗紅。

解題方法（R＝紅，B＝黑）

1. 40：根，塗黑。
2. 60：40 的右子，紅；父為黑，不需修正。
3. 55：60 的左子（紅），父 60 紅、叔叔（40 的左）為空（黑），異側 → 先對 60 右旋，再對 40 左旋：55B，子節點 40R、60R。
4. 15：40R 的左子；叔叔 60R 為紅 → 40、60 改黑，55 改紅後因是根再塗黑。樹：55B（40B（15R），60B）。
5. 20：15R 的右子；叔叔（40 的右）為空，異側 → 對 15 左旋、對 40 右旋：20B 成為 55 的左子，15R、40R 為其子。樹：55B（20B（15R, 40R），60B）。
6. 5：15R 的左子；叔叔 40R 為紅 → 15、40 改黑，20 改紅；20 的父 55 為黑，結束。樹：55B（20R（15B（5R）, 40B），60B）。

核心觀念

雙指標快速排序會先選定樞紐值（pivot），再從左右兩端掃描：左指標尋找大於樞紐的元素，右指標尋找小於樞紐的元素，找到後交換。當兩指標交錯，將樞紐與右指標停留處交換，樞紐便到達正確位置。

本題樞紐為 $52$，初始左指標位於 $21$，右指標位於 $71$。

解題方法

依照指標位置逐步掃描並交換：

1. 左指標由左向右跳過小於 $52$ 的元素 $21、40$，停在 $88$。

2. 右指標由右向左跳過大於 $52$ 的元素 $71$，停在 $46$。

3. $88>52$ 且 $46<52$，交換兩者：

   $\{52, 21, 40, 46, 33, 57, 88, 71\}$

4. 左指標繼續跳過 $46、33$，停在 $57$；右指標向左跳過 $88、57$，停在 $33$。此時兩指標交錯。

5. 將樞紐 $52$ 與右指標所在的 $33$ 交換：

   $\{33, 21, 40, 46, 52, 57, 88, 71\}$

讀圖

右側為二分圖，左側 $L_1\sim L_5$、右側 $R_1\sim R_4$（由上而下），邊為：$L_1R_1$、$L_2R_1$、$L_2R_3$、$L_3R_2$、$L_3R_3$、$L_3R_4$、$L_4R_3$、$L_5R_3$。

選項分析

• (A) 錯誤。 Johnson 演算法的時間為 $O(V^2\log V+VE)$（以 Fibonacci heap 實作 Dijkstra）。稠密圖 $E=\Theta(V^2)$ 時為 $O(V^3)$，與 Floyd–Warshall 的 $\Theta(V^3)$ 同階，不會比較快；Johnson 的優勢在稀疏圖。
• (B) 正確。 多項式時間可解的問題（P）都屬於 NP（$P\subseteq NP$），所以 NP 中包含多項式時間可解的問題。
• **(C) 正確。

核心觀念

本題考查排序演算法的空間與時間複雜度、最長簡單路徑問題的計算難度、遞迴樹的結構，以及程式碼長度與時間複雜度的差異。

題目未指定「漸近最優」採用哪種情況分析，也未說明「可用分治法解決」是否要求有效率的多項式時間演算法。以下依常見演算法考題慣例，以最壞情況分析快速排序，並將「分治法解決」解讀為能有效拆成較小子問題。

解題方法

逐項核對定義與複雜度：

• 原地排序主要使用常數額外空間。
• 最長簡單路徑是 NP-hard 問題，不能因為可以遞迴枚舉就視為有有效率的分治解法。
• 遞迴樹的形狀由遞迴式決定，不必然是滿二元樹。
• 漸近最優性須指定分析情況；快速排序最壞情況為 $\Theta(n^2)$。
• 程式碼行數不是時間複雜度的衡量方式。

選項分析

(A) 正確。 插入排序在原陣列中逐步移動元素並插入待排序項目，只需常數額外空間，因此屬於原地排序，額外空間複雜度為 $O(1)$。

(B) 錯誤。 最長簡單路徑要求路徑上的頂點不得重複；在一般圖上，判斷是否存在長度至少為指定值的簡單路徑是 NP-complete 問題，求最長路徑則是 NP-hard 問題。將圖切成子圖時，子問題間會受共用頂點及「不可重複使用頂點」的限制牽連，無法把子問題的解直接合併成原問題的解——這正是分治法成立的前提（子問題獨立、可合併）不成立；

核心觀念

遞迴式常用主定理、遞迴樹與調和級數求漸近成長率。主定理適用於 $T(n)=aT(n/b)+f(n)$，比較 $f(n)$ 與臨界項 $n^{\log_b a}$；若兩者同階，解為 $\Theta(n^{\log_b a}\log n)$。判斷選項中的 $O(g(n))$ 時，只要實際解的成長率不快於 $g(n)$，敘述就成立；即使 $g(n)$ 比實際解寬鬆也可以。

解題方法

逐一求出遞迴式的漸近解，再與各選項宣稱的上界比較。對於參數不是 $n$ 的冪次形式的遞迴式，可先換變數；對不等分割的遞迴式，則用遞迴樹追蹤每層工作量。

選項分析

(A) 錯誤。

$$T(n)=16T(n/4)+n^2$$

主定理中 $a=16$、$b=4$，因此

$$n^{\log_b a}=n^{\log_4 16}=n^2$$

非遞迴成本 $n^2$ 與臨界項同階，所以

$$T(n)=\Theta(n^2\log n)$$

這比 $O(n^2)$ 成長得快，故選項錯誤。

(B) 正確。

$$T(n)=4T(n/5)+n^{4/3}$$

臨界項為

$$n^{\log_5 4}$$

因為 $\log_5 4<1<4/3$，所以 $n^{4/3}$ 多項式地大於臨界項。再檢查正則條件：

$$4(n/5)^{4/3} =\frac{4}{5^{4/3}}n^{4/3}$$

其中 $\frac{4}{5^{4/3}}<1$，符合主定理第三種情形，得到

$$T(n)=\Theta(n^{4/3})$$

因此 $T(n)=O(n^{4/3})$，選項正確。

(C) 錯誤。

$$T(n)=T(n/4)+T(n/2)+n^2$$

在遞迴樹中，每個子問題的大小分別是父問題的 $1/4$ 與 $1/2$。若某層節點的問題大小為 $x$，它們的非遞迴工作量總和是各節點大小的平方和。從一層到下一層，這個總和的倍率為

讀圖

右側為四階段（stage）有向圖，邊由左向右：

• Stage 0→1：$V_0\to V_{1,1}$（3）、$V_0\to V_{1,2}$（1）、$V_0\to V_{1,3}$（5）、$V_0\to V_{1,4}$（7）
• Stage 1→2：$V_{1,1}\to V_{2,1}$（2）、$V_{1,1}\to V_{2,2}$（3）、$V_{1,2}\to V_{2,1}$（9）、$V_{1,2}\to V_{2,2}$（16）、$V_{1,3}\to V_{2,1}$（5）、$V_{1,3}\to V_{2,3}$（7）、$V_{1,4}\to V_{2,1}$（10）、$V_{1,4}\to V_{2,2}$（2）、$V_{1,4}\to V_{2,3}$（4）
• Stage 2→3：$V_{2,1}\to V_3$（13）、$V_{2,2}\to V_3$（1）、$V_{2,3}\to V_3$（2）

核心觀念

多階段圖（multistage graph）的最短路徑是動態規劃的經典例題：令 $d(v)$ 為 $v$ 到終點 $V_3$ 的最短距離，則

$$d(v)=\min_{(v,w)}\{\,c(v,w)+d(w)\,\}.$$

這個遞迴成立是因為問題具有最佳子結構：最短路徑的任一段後綴，也必須是從該點出發的最短路徑。

解題方法（由後往前）

讀圖

右側為有向加權圖：$A\to B$（16）、$A\to F$（13）、$B\to F$（10）、$F\to B$（4）、$B\to C$（12）、$C\to F$（9）、$F\to E$（14）、$E\to C$（7）、$C\to D$（20）、$E\to D$（4）。（這是 CLRS 最大流章節的範例網路，$A$ 為源點、$D$ 為匯點。）

選項分析

• (A) 錯誤。 Kruskal 演算法求的是無向圖的最小生成樹；本圖是有向圖，題目要的答案（最短路徑或最大流）也不是生成樹問題，Kruskal 不適用。
• (B) 正確。 在 $|V|=6$、$|E|=10$ 的圖上，Floyd–Warshall 是 $\Theta(V^3)$（約 216 次鬆弛），Bellman–Ford 是 $O(VE)$（約 60 次），前者花的時間較多。
• (C) 錯誤。 以 $A$ 為源點、$D$ 為匯點的最大流是 23，不是 24。

核心觀念

這題考 C 語言整數常數的進位判讀，以及 printf 的格式指定符。

• 以 0 開頭的整數常數採用八進位表示，因此 025 是八進位數。
• %X 會將整數以十六進位大寫字母格式輸出。

解題方法

先將 num1 的八進位值換算成十進位：

$$(025)_8 = 2 \times 8 + 5 = 21$$

num2 = num1，所以 num2 的值也是十進位 $21$。再將 $21$ 換成十六進位：

$$21 = 1 \times 16 + 5 = (15)_{16}$$

核心觀念

本題考查 C 語言指標的 const 修飾位置，以及透過指標修改變數的效果：

• const int *ptr：指標可改指向其他位置，但不可透過此指標修改所指向的整數。
• int *const ptr：指標本身不可改指向其他位置，但可透過此指標修改所指向的整數。
• const int *const ptr：指標本身與所指向的整數都不可透過此指標修改。

解題方法

先看 main 中各變數與指標的對應關係：

• a 的初值為 10，p1 指向 a。p1 的型別是 const int *，但本題函式並未透過 ptr1 修改 a。
• b 的初值為 20，p2 指向 b。p2 的型別是 int *const：p2 不能改指向，但可以透過它修改 b。
• p3 指向 a，型別是 const int *const，本題沒有使用它。

核心觀念

本題考查 無號整數位移與溢位、位元組序、指標型別轉換，以及 printf 的格式指定。

• unsigned int 左移後若超出型別可表示範圍，結果依無號整數的模數規則保留低位元。
• char * 可用來逐位元組觀察物件的記憶體表示；哪個位元組位於最低位址，取決於系統的位元組序。
• printf 的 %x 要求對應引數型別為 unsigned int。可變參數函式不會依格式字串自動轉換引數型別。

解題方法

先看 b。unsigned char 只保留 a 的最低位元組；在一般 8 位元組元組環境中：

$$\texttt{0xFFFF0101} \bmod 2^8 = \texttt{0x01}$$

因此 b 的值是 0x01。

接著，p 指向 a，*p <<= 6 將整個 unsigned int 左移 6 位。若採用常見的 32 位元 unsigned int：

$$\texttt{0xFFFF0101} \times 2^6 = \texttt{0x3FFFC04040}$$

只保留低 32 位元後：

$$\texttt{0xFFC04040}$$

核心觀念

本題考查程式語言中的四個基本概念：

• Overloading（多載）：多個不同的函式、運算子或操作使用相同名稱，實際執行哪一個由參數型別或數量等條件決定。
• Coercion（強制轉型／自動轉型）：程式語言自動把值轉換成所需的型別。
• Aliasing（別名）：同一個物件或資料可透過多個名稱存取。
• Polymorphism（多型）：同一段操作能適用於多種型別的資料。

解題方法

依照關鍵詞配對定義：

• 「相同名稱」對應多載。
• 「自動轉換型別」對應強制轉型。
• 「同一事物有多個名稱」對應別名。
• 「適用多種型別」對應多型。

選項分析

核心觀念

本題考查 C++ 的函式多載解析與虛擬函式動態繫結：

• 編譯時依照物件運算式的靜態型別與引數型別，決定呼叫哪個函式版本。
• 函式宣告為 virtual 時，執行時會依物件的動態型別，決定執行哪個覆寫版本。
• D 宣告了 m(int)，因此它覆寫 B 的虛擬函式 m(int)。

解題方法

Line A 是：

dP->m(1);

核心觀念

這題考查 C++ 繼承中的函式名稱隱藏，以及多載解析與虛擬函式呼叫的先後順序。

當衍生類別 D 宣告了名為 m 的成員函式，D::m 會隱藏基底類別 B 中所有同名的多載函式。透過 D* 呼叫 m 時，編譯器只在 D 的可見函式中進行多載解析。

解題方法

dP 的靜態型別是 D*。D 只宣告了：

void m(int i) {
    cout << "D" << endl;
}

核心觀念

本題考 C++ 的虛函式動態繫結。函式呼叫分兩步判定：

1. 編譯期依據指標的靜態型別與引數型別，決定呼叫哪個函式簽章。
2. 若該函式是虛函式，執行期再依據物件的實際型別，決定執行哪個類別的實作。

D 繼承自 B，且 D::m(int) 覆寫了 B::m(int)。即使 D::m(int) 沒有再次寫上 virtual，它仍沿用基底類別中的虛函式性質。

解題方法

Line C 為：

bP->m(1);

核心觀念

這題考查 C++ 的多載解析與虛擬函式動態繫結：

• 多載解析在編譯時依照運算式的靜態型別與引數型別，決定呼叫哪個函式版本。
• 若選中的函式是虛擬函式，執行時再依物件的動態型別決定使用哪個類別的實作。
• D 中的 m(int) 覆寫了 B 的 m(int)。即使沒有再寫 virtual，它仍是虛擬函式。
• D 宣告了自己的 m(int)，會在以 D 型別進行名稱查找時遮蔽 B 的其他 m 多載；但透過 B* 呼叫時，名稱查找依 B 的介面進行。

解題方法

Line D 是：

bP->m(2.0);

bP 的靜態型別是 B*，所以編譯器先從 B 的多載中選擇最適合 double 引數的函式：

核心觀念

本題考查 C++ 的虛擬函式動態繫結。呼叫虛擬函式時：

1. 編譯器依據運算式的靜態型別與引數型別，決定呼叫哪一個多載函式。
2. 執行時再依據物件的動態型別，決定執行哪個類別的覆寫版本。

解題方法

br 的宣告型別是 B&，因此 br.m(1) 先從 B 的多載函式中，依引數 1（型別為 int）選出 m(int)。

核心觀念

這題考查 C++ 的靜態型別、函式多載解析與虛擬函式動態繫結：

• 先依運算式的靜態型別與引數型別，決定呼叫哪個多載函式。
• 若選中的函式是虛擬函式，再依物件的動態型別決定執行哪個覆寫版本。
• br 的靜態型別是 B&，但它參照的是 D 物件；參照不會像物件複製那樣造成切割。

解題方法

Line F 是：

br.m(2.0);

br 的靜態型別為 B&，因此多載解析會在 B 可見的函式中進行：

核心觀念

本題考「物件切割（object slicing）」與「虛擬函式的動態繫結」。

B bo = *dP; 會將 D 物件的 B 基底部分複製到 bo。因此，bo 是一個獨立的 B 物件，原本 D 物件中新增或覆寫的部分不會留在 bo 裡。

呼叫虛擬函式時，會依實際物件型別決定執行哪個函式；但物件切割後，bo 的實際型別就是 B。

解題方法

核心觀念

這題考「物件切割（object slicing）」與「函式多載解析」。B bo = *dP; 會把 D 物件中的 B 基底部分複製成一個獨立的 B 物件；bo 不再是 D 物件，因此無法透過它呼叫 D 的成員函式。

呼叫多載函式時，編譯器先依照物件的靜態型別及參數型別選出函式；若函式是虛擬函式，再依實際物件型別決定執行哪個覆寫版本。

解題方法

Line H 是：

bo.m(2.0);