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

核心觀念

C++ 的參考（reference）必須直接參照一個物件，不能被指標指向。因此，C++ 不允許「指向參考的指標」；但允許「指標的參考」，例如 int *&。

解題方法

從變數 a1 往外讀宣告符號：

int &* a1;

* 表示 a1 是指標，接著的 & 表示它指向 int 的參考，也就是「指向參考的指標」。此型別不合法，因為參考不是可供指標指向的物件。

合法的「指標的參考」寫法是：

int* p = nullptr;
int*& a1 = p;   // a1 是 p 的別名

核心觀念

int *& a2; 宣告的是「指向 int 的指標之參考」：a2 必須參考一個已存在的 int* 變數。C++ 的參考在宣告時必須立即綁定到有效物件，不能只宣告而不初始化。

解題方法

先由右向左讀型別：a2 是參考（&），參考的對象是 int*。這行宣告沒有提供任何要綁定的指標變數，因此違反參考必須初始化的規則，無法編譯。

例如，先建立指標，再讓參考綁定它：

int* p = nullptr;
int*& a2 = p;

核心觀念

這題考查指標的型別，以及 const 限定在哪一層。已知 cip 的型別是 const int*，也就是「指向 const int 的指標」：

• *cip 是 const int，不能透過 cip 修改整數值。
• cip 本身不是常數指標，因此可以改指向另一個整數。

對 cip 取址後，型別會多一層指標：

解題方法

將宣告左側與初始值的型別逐層對照：

const int* cip = nullptr;
const int** b1 = &cip;

b1 的型別是 const int**，而 &cip 的型別也是 const int**，兩者完全相同，因此可以編譯。

核心觀念

這題考指標的 const 修飾位置，以及多層指標之間能否隱式轉換。

const int* cip 表示 cip 是可改指向的指標，但不能透過它修改所指的 int。而 int* const* b2 表示 b2 指向一個「不可改指向的 int*」；b2 本身仍可改指向。

解題方法

先比較兩邊的型別：

• &cip 的型別是 const int**：指向「可改指向的 const int*」。
• b2 的型別是 int* const*：指向「不可改指向的 int*」。

兩者的內層指標型別不同：來源指向 const int，目標卻是指向 int。若允許這種轉換，就能經由 b2 把 const 限制繞過：

核心觀念

本題考查多層指標的 const 限定，以及指標初始化時的型別相容性。

• const int* cip：cip 是「指向唯讀 int 的指標」，指標本身可以改指向其他位置。
• &cip 的型別是 const int**：它指向一個「指向唯讀 int 的指標」。
• int ** const b3：b3 是「不可改指向位置的指標」，但它所指向的是一般的 int*。

因此，b3 要求的初始值型別是 int**；實際提供的 &cip 型別則是 const int**，兩者不相容。

解題方法

逐層由變數往外讀型別：

const int* cip;

cip 指向 const int，所以取址後：

&cip  // 型別為 const int**

再看宣告：

int ** const b3 = &cip;

這裡的 const 限定的是最外層的 b3：b3 本身不能改指向，但其目標型別仍是 int**。

核心觀念

這題考查建構子的呼叫順序，以及透過基底類別指標刪除衍生類別物件時，解構子是否為虛擬函式。

B 繼承自 A。程式沒有自行宣告建構子與解構子，因此編譯器會產生隱含的預設建構子與解構子。A 的解構子不是虛擬函式；A::f2() 雖然是虛擬函式，與解構子的虛擬性無關。

解題方法

執行 new B 時，先建構基底類別，再建構衍生類別，因此建構順序確定為：

1. A::A()
2. B::B()

接著，ap 的靜態型別是 A*，實際指向的物件型別是 B。執行 delete ap 時，基底類別 A 的解構子不是虛擬函式。

核心觀念

這題考兩件事：編譯時依指標的靜態型別查找成員函式，以及執行時對虛擬函式進行動態繫結。

• 非虛擬函式依指標的靜態型別決定呼叫哪個版本。
• 虛擬函式若由衍生類別重新定義，則依物件的動態型別決定呼叫哪個版本。
• 呼叫某個函式時，函式名稱必須先能透過指標的靜態型別找到；動態繫結不會讓基底類別指標取得它沒有宣告的成員。

本題中，A::f1 和 B::f1 都是非虛擬函式；C::f1 雖宣告為虛擬函式，但不會讓 A::f1 變成虛擬函式。f2 在 A 宣告為虛擬函式，C::f2 重新定義它。f3 在 B 宣告為虛擬函式，C 沒有重新定義它。

解題方法

先確認每個指標的靜態型別與所指物件的動態型別：

接著逐項判斷：先用靜態型別確認成員函式是否可見，再判斷該函式是否為虛擬函式；若是，才依動態型別決定執行版本。

各列分析

（甲）bp1->f1();

bp1 是 B*，可找到 B::f1。它是非虛擬函式，因此呼叫 B::f1。

輸出：B::f1,

（乙）bp1->f2();

B 沒有重新定義 f2，所以可呼叫繼承自 A 的虛擬函式。物件動態型別為 B，因此執行 A::f2。

輸出：A::f2,

（丙）bp2->f2();

讀圖

題組附圖（原卷）的無向圖共有 9 條邊：$A\!-\!B$、$A\!-\!C$、$A\!-\!D$、$B\!-\!D$、$B\!-\!E$、$D\!-\!E$、$C\!-\!F$、$C\!-\!G$、$F\!-\!G$。

核心觀念

深度優先搜尋（DFS）從起點出發，每次走向「尚未拜訪」的相鄰頂點；無路可走時回溯。題目規定從 A 開始、有多個未拜訪鄰點時先走字母最小的。DFS 過程中實際走過的邊構成深度優先生成樹（DFS spanning tree），其餘的邊是回邊（back edge）。

解題方法

1. 從 A 出發，鄰點 B、C、D 中先走 B：邊 $(A,B)$。
2. B 的未拜訪鄰點 D、E，先走 D：邊 $(B,D)$。
3. D 的鄰點 A、B 已拜訪，走 E：邊 $(D,E)$。
4. E 的鄰點 B、D 都已拜訪 → 回溯到 D、B、A。
5. A 還有未拜訪的 C：邊 $(A,C)$。
6. C 的未拜訪鄰點 F、G，先走 F：邊 $(C,F)$。

讀圖

題組附圖（原卷）的無向圖共有 9 條邊：$A\!-\!B$、$A\!-\!C$、$A\!-\!D$、$B\!-\!D$、$B\!-\!E$、$D\!-\!E$、$C\!-\!F$、$C\!-\!G$、$F\!-\!G$。

核心觀念

dfn(v)（depth-first number）是 DFS 中頂點被第一次拜訪的次序編號（從 1 開始）。

解題方法

依 3.1 的 DFS（從 A 開始、字母小的優先），拜訪順序為

所以

讀圖

題組附圖（原卷）的無向圖共有 9 條邊：$A\!-\!B$、$A\!-\!C$、$A\!-\!D$、$B\!-\!D$、$B\!-\!E$、$D\!-\!E$、$C\!-\!F$、$C\!-\!G$、$F\!-\!G$。

由 3.1、3.2：DFS 樹邊為 $(A,B),(B,D),(D,E),(A,C),(C,F),(F,G)$；回邊為 $(A,D)$、$(B,E)$、$(C,G)$；dfn 為 A1、B2、D3、E4、C5、F6、G7。

核心觀念

也就是：從 $v$ 出發，沿著子孫往下走、最後最多再走一條回邊，能到達的最小 dfn。要由葉子往上算。

解題方法

• E（無子節點）：回邊 $E\!-\!B$，$dfn(B)=2$ → $low(E)=\min(4,2)=2$。
• D：子節點 E 的 low 為 2；回邊 $D\!-\!A$，$dfn(A)=1$ → $low(D)=\min(3,2,1)=1$。
• B：子節點 D 的 low 為 1 → $low(B)=\min(2,1)=1$。

讀圖

題組附圖（原卷）的無向圖共有 9 條邊：$A\!-\!B$、$A\!-\!C$、$A\!-\!D$、$B\!-\!D$、$B\!-\!E$、$D\!-\!E$、$C\!-\!F$、$C\!-\!G$、$F\!-\!G$。

由前三小題：dfn 為 A1、B2、C5、D3、E4、F6、G7；low 為 A1、B1、C5、D1、E2、F5、G5。DFS 樹：A 的子節點是 B、C；B→D→E；C→F→G。

核心觀念

用 DFS 判斷割點（articulation point）：

1. 根節點：在 DFS 樹中有兩個以上子節點時是割點。
2. 非根節點 $u$：存在某個子節點 $w$ 使 $low(w)\ge dfn(u)$ 時是割點（$w$ 的子樹無法繞過 $u$ 回到 $u$ 的祖先）。

解題方法

• A（根）：有兩個子節點 B、C → 割點。（拿掉 A，{B,D,E} 與 {C,F,G} 分開。）
• B：子節點 D 的 $low=1<dfn(B)=2$ → 不是割點。

核心觀念

二元樹的中序走訪順序為「左子樹、根、右子樹」，後序走訪順序為「左子樹、右子樹、根」，前序走訪順序則為「根、左子樹、右子樹」。

因此，後序序列的最後一個節點必定是整棵樹的根；在中序序列中找到根之後，其左側與右側分別是左子樹和右子樹的節點。依此規則遞迴重建，即可得到二元樹及其前序序列。

解題方法

給定的後序序列最後一個節點是 $A$，所以根為 $A$。在中序序列中，$A$ 前方沒有節點，後方所有節點都屬於右子樹：

因此，$A$ 沒有左子樹。右子樹的後序序列最後一個節點是 $B$，所以 $B$ 是右子樹的根。中序序列中 $B$ 後方仍是其右子樹，沒有左子樹。

依同樣方式繼續拆分：

• 接著的根為 $C$，其左子樹中序為 $(G,E,D,I,J,F,H)$。
• 左子樹的根為 $D$；其中序左子樹為 $(G,E)$，右子樹為 $(I,J,F,H)$。
• $D$ 的左子樹根為 $E$，而 $E$ 的左子節點為 $G$。
• $D$ 的右子樹根為 $F$；其左子樹根為 $I$，$I$ 的右子節點為 $J$，$F$ 的右子節點為 $H$。

依「根、左子樹、右子樹」產生前序序列：

選項分析

讀圖

題組附圖（原卷）的有向邊與權重：$A\to B\,(2)$、$A\to C\,(7)$、$A\to E\,(12)$、$C\to B\,(3)$、$B\to D\,(2)$、$C\to D\,(-5)$、$C\to E\,(2)$、$D\to F\,(2)$、$F\to G\,(4)$、$E\to G\,(-7)$。

核心觀念

Dijkstra 演算法每一輪從「尚未確定」的頂點中選出目前距離最小者，將它標記為已確定，再用它鬆弛（relax）相鄰的尚未確定頂點。它假設邊權非負：一個頂點一旦被選出就不再更新。圖中有負邊時，結果可能不是真正的最短路徑——本題就是要觀察這個現象。

解題方法（暫定距離逐輪更新）

讀圖

題組附圖（原卷）的有向邊與權重：$A\to B\,(2)$、$A\to C\,(7)$、$A\to E\,(12)$、$C\to B\,(3)$、$B\to D\,(2)$、$C\to D\,(-5)$、$C\to E\,(2)$、$D\to F\,(2)$、$F\to G\,(4)$、$E\to G\,(-7)$。

核心觀念

Dijkstra 演算法（教科書版本，如 Horowitz《Fundamentals of Data Structures in C》）只會更新尚未確定的頂點：頂點一旦被選出，距離就固定。邊權有負值時，這個假設會失效，演算法得到的值不一定是真正的最短距離。題目問的是「執行 Dijkstra 之後」的距離。

解題方法

依 5.1 的執行過程：

關鍵兩步：

• C 在 D 之後才被選出。雖然經 C 到 D 的路徑 $A\to C\to D$ 長度 $7-5=2<4$，但 D 已確定，不再更新，所以 *D 維持 4

讀圖

題組附圖（原卷）的有向邊與權重：$A\to B\,(2)$、$A\to C\,(7)$、$A\to E\,(12)$、$C\to B\,(3)$、$B\to D\,(2)$、$C\to D\,(-5)$、$C\to E\,(2)$、$D\to F\,(2)$、$F\to G\,(4)$、$E\to G\,(-7)$。

核心觀念

Dijkstra 演算法以前驅（predecessor）記錄每個頂點的最短路徑來源；頂點被選出後距離與前驅都固定。邊權有負值時，所得路徑不一定是真正的最短路徑。

解題方法

依 5.1、5.2 的執行過程：

• 選出 A 後，B 的暫定距離為 2（前驅 A）。
• 選出 B 後，D 的暫定距離為 $2+2=4$，前驅為 B。
• 接著 D 以距離 4 被選出並固定。之後 C（7）才被選出，雖然 $7+(-5)=2<4$，但 D 已確定，前驅不再改變。

題目字串

原卷的字串是 acacabacacabacacac，共 18 個字元（索引 0～17）：

核心觀念

KMP 的失敗函數 $f(j)$：$p_0\ldots p_j$ 中「既是前綴、又是後綴」的最長真子字串，其最後一個字元的索引 $k$；不存在時為 $-1$。可遞迴計算：已知 $f(j-1)=k$，若 $p_{k+1}=p_j$ 則 $f(j)=k+1$；否則令 $k\leftarrow f(k)$ 繼續比較，直到 $k=-1$ 時再比 $p_0$。

解題方法

核心觀念

本題考「代入法」（substitution method）：先猜測遞迴式的漸近界，再用數學歸納法驗證。題目要求緊確的漸近上界，因此除了證明 $T(n)=O(n)$，也要確認 $T(n)=\Omega(n)$，才能得到緊確界。

解題方法

遞迴式為

假設 $T(n)$ 對充分大的 $n$ 為非負，且小於某個固定門檻時的基本情況皆有界。由於每層遞迴子問題的規模總和是

小於原問題規模的一半，線性項 $6n$ 將主導遞迴成本。因此猜測 $T(n)=O(n)$，並設歸納假設為 $T(m)\le cm$，其中 $m<n$。

代入遞迴式：

核心觀念

這題考遞迴式的漸近下界，以及代換法（substitution method）的數學歸納證明。

遞迴式為

每層的遞迴子問題數量乘上子問題規模平方後，總成本與 $n^2$ 同階。遞迴深度約為 $\log_2 n$，因此預期下界為 $\Omega(n^2\log n)$。

解題方法

假設 $n$ 是 2 的冪，且基底值 $T(1)\ge 0$。以數學歸納法證明：

基底情況： 當 $n=1$ 時，右側為 $1^2\log_2 1=0$，而 $T(1)\ge 0$，命題成立。

歸納步驟： 假設對 $n/2$ 命題成立，即

代入原遞迴式：

核心觀念

本題考查比較式排序的決策樹下界。比較式排序只能透過比較元素大小來決定輸出順序；每次比較只有兩種結果，因此可用二元決策樹表示演算法的執行過程。

以下依排序演算法通常採用的定義，將「時間複雜度」解讀為最壞情況時間複雜度，並假設輸入包含 $n$ 個互異元素。

解題方法

要證明最壞情況至少需要 $\Omega(n\lg n)$ 次比較，可計算決策樹必須有多少個葉節點，再由二元樹的高度推得比較次數下界。

$n$ 個互異元素共有 $n!$ 種可能排列。演算法必須能區分這些排列，才能對每種輸入都正確排序，因此決策樹至少需要 $n!$ 個葉節點。

若決策樹高度為 $h$，最多只能有 $2^h$ 個葉節點，所以：

取以 $2$ 為底的對數，可得：

核心觀念

不一定。 動態規劃的「最佳子結構」表示：原問題的最佳解，能由其子問題的最佳解組成。它保證了把子問題解到最佳有助於構造原問題的最佳解，但不保證每一步選擇眼前看起來最好的局部決策，就能得到全域最佳解。

最佳子結構常以遞迴式表示。若原問題的最佳值為 $F(x)$，可能需比較多種決策 $a$：

其中 $A(x)$ 是當前可選決策，$c(x,a)$ 是採取決策 $a$ 的成本，$x_a$ 是決策後的子問題。關鍵在於：動態規劃會比較所有可行決策，再選出總成本最低者；只挑當下成本最低的決策，未必能使「當前成本加後續成本」最小。

解題方法

以硬幣找零為例，硬幣面額為 $1、3、4$，目標金額為 $6$，目標是使用最少硬幣。

若採用局部策略，每次都選不超過剩餘金額的最大面額，會先選 $4$，剩下 $2$，再選兩枚 $1$：

共使用 $3$ 枚硬幣。

但全域最佳解是：

核心觀念

Johnson 重加權把可能含負權重的邊改成非負權重，讓 Dijkstra 演算法可以使用。對每個頂點 $v$ 設一個勢能 $h(v)$，並定義新權重：

若 $h(v)$ 是從新增超級源點 $q$ 到 $v$ 的最短距離，則最短路徑的三角不等式保證：

所以 $w'(u,v)\ge 0$，可用 Dijkstra 求最短路徑。重加權只會讓同一起點、終點的所有路徑增加相同的量，因此不改變最短路徑；求得新圖距離後，可以還原原圖距離。

解題方法

標準 Johnson 作法：不會比 Bellman-Ford 快。 標準流程以 Bellman-Ford 計算勢能，時間為 $O(VE)$；再以 Dijkstra 求單一起點距離，時間約為 $O((V+E)\log V)$。總時間為：

對單一起點問題而言，這比直接使用 Bellman-Ford 多了額外步驟，漸近時間也沒有改善。

利用 DAG 結構計算勢能：可以更快。 新增超級源點 $q$，並從 $q$ 向每個頂點連一條權重為 $0$ 的邊。新增後的圖仍是 DAG。先做拓樸排序，再依拓樸順序鬆弛邊，即可在 $O(V+E)$ 時間內求出所有 $h(v)$，不必用 Bellman-Ford。

接著以 $w'(u,v)=w(u,v)+h(u)-h(v)$ 重加權。由於 $h$ 是最短距離，所有新權重都非負。對新圖從指定起點 $s$ 執行 Dijkstra；

核心觀念

本題比較背包問題的三種演算法性質：

• 最佳子結構：整體最佳解可以由較小子問題的最佳解組成。
• 貪婪選擇性質：存在一個局部最佳選擇，使得某個最佳解一定包含這項選擇。
• 重疊子問題：遞迴分解會反覆遇到相同子問題，可用動態規劃儲存並重用結果。

題目給定

因此，對任意 $i<j$，物品 $j$ 比物品 $i$ 重量更輕、價值更高。在標準背包設定中，假設重量與價值為正，背包容量記為 $C$。

解題方法

（a）分數背包

分數背包允許取物品的一部分。其貪婪策略是依單位重量價值 $v_i/w_i$ 由高至低取用。

由題目的排序可得，若 $i<j$，則

因為 $v_i<v_j$ 且 $w_i>w_j$。所以物品 $k$ 的單位重量價值最高，物品 $k-1$ 次之，依此類推。依此順序裝入物品，最後一件若無法全部裝入，就取其可裝入的部分。

分數背包也有最佳子結構：先取完單位價值最高的部分後，剩餘容量上的問題仍是相同型態的分數背包問題。

（b）0-1 背包

0-1 背包每件物品只能完整取用或不取用。一般情況下，0-1 背包不一定能用貪婪法求得最佳解；但本題的排序條件使後面的物品同時更輕且更有價值。

考慮物品 $k$。若 $C\ge w_k$，任何不含物品 $k$、但含有其他物品的可行解，都可將其中任一物品 $i<k$ 換成物品 $k$。替換後重量下降、價值上升。因此，存在一個最佳解包含物品 $k$。

核心觀念

本題考查 C 語言的輸入輸出、指標與位址、運算子優先順序，以及偶數與奇數的判斷。

• scanf 需要接收變數的位址，才能把讀入的值存進變數。整數變數 X 的位址寫成 &X。
• 在 C 語言中，== 的優先順序高於位元 AND 運算子 &。因此，X&2 == 0 會先計算 2 == 0，而不是先計算 X & 2。
• 判斷整數是否為偶數，可使用餘數運算：若 $X \bmod 2 = 0$，則 $X$ 是偶數，否則是奇數。
• 標準 C 的主程式應使用 int main(void)，並以 return 0; 表示正常結束。

解題方法

逐行檢查程式中的型別、參數與條件式：

1. 將 void main() 改為標準寫法 int main(void)。
2. 將 scanf("%d", X) 改為 scanf("%d", &X)，傳入 X 的位址。
3. 原條件 X&2 == 0 因運算子優先順序，等同於 X & (2 == 0)。由於 2 == 0 為假，結果為 0，條件實際上等同於 X & 0，永遠為零。改用 (X % 2) == 0 明確判斷奇偶。
4. 檢查 scanf 的回傳值，確保成功讀入一個整數後才進行判斷。

修正後的程式如下：

核心觀念

二元搜尋樹（BST）的每個節點包含一個鍵值與左右子樹指標。依照 BST 的排序性質，對任一節點：

• 左子樹中的鍵值小於該節點的鍵值。
• 右子樹中的鍵值大於該節點的鍵值。

本題的鍵值是字串，因此使用 C 標準函式庫的 strcmp 比較字串。若 strcmp(a, b) 小於 $0$，代表 $a$ 的字典序小於 $b$；若等於 $0$，代表兩者相同；若大於 $0$，代表 $a$ 大於 $b$。

解題方法

從根節點開始比較目標字串與目前節點的鍵值：

1. 若目前指標為 NULL，表示搜尋到樹的空位置仍未找到，回傳 NULL。
2. 若字串相同，回傳目前節點的位址。
3. 若目標字串較小，依 BST 性質只需搜尋左子樹。
4. 若目標字串較大，只需搜尋右子樹。

使用迴圈逐層搜尋，額外空間不隨樹高增加。

核心觀念

本題考查 C 字串函式的用途、參數與回傳型別，以及字串記憶體的比較與配置。C 字串是以 '\0' 結尾的字元序列；字串函式通常以 char * 或 const char * 傳遞字串。

解題方法

判讀每個函式時，分別確認它是否修改字串、是否配置新記憶體，以及失敗時如何回報。這能釐清回傳值的型別與呼叫端的記憶體管理責任。

(a) strcmp()

strcmp() 比較兩個以 '\0' 結尾的字串，依字典序判斷大小；它不會修改字串內容。

int strcmp(const char *s1, const char *s2);

參數 s1、s2 都是指向唯讀字串的指標，型別為 const char *；回傳值型別是 int：

• 回傳值小於 0：s1 的字典序小於 s2。
• 回傳值等於 0：兩字串內容相同。
• 回傳值大於 0：s1 的字典序大於 s2。

比較會從第一個字元開始，直到遇到第一組不同的字元，或兩字串都到達結尾。標準只保證回傳值的正負與零，不保證結果恰好是 -1、0 或 1。字元的比較依其 unsigned char 值進行。

strcmp("cat", "car")  // 正值：第一個不同字元 't' 大於 'r'
strcmp("cat", "cat")  // 0
strcmp("car", "cat")  // 負值

(b) strdup()