113 年國立中正大學資訊工程學系碩士班甲組《軟體設計》考古題與詳解

Question 1

After inserting a new node with the key "43" into the AVL tree, what does the array representation of the AVL tree look like? Please note that a "−" represents a null value in the array.

(A) $(65,40,70,35,50,−,80,−,−,45,55,−,43)$

(B) $(65,40,70,35,45,−,80,−,−,43,50,−,−,55)$

(C) $(65,45,70,40,50,−,80,35,43,−,55)$

(D) $(65,45,70,35,50,−,−,80,40,43,−,55)$

(E) None of the above

Accepted Answer

核心觀念 AVL 樹在每次插入後，都要檢查從新節點往根回溯的節點平衡因子： $$ BF(v)=h(	ext{左子樹})-h(	ext{右子樹}) $$ 若 $|BF(v)|1$，就依插入路徑進行旋轉。本題原圖中，根節點是 $65$；其左子節點 $40$ 的左右子節點為 $35$、$50$；$50$ 的左右子節點為 $45$、$55$；右子節點 $70$ 有右子節點 $80$。 解題方法 插入 $43$ 時，依二元搜尋樹規則往下比較：$43<65$、$4340$、$43<50$、$43<45$，因此 $43$ 成為 $45$ 的左子節點。 節點 $50$ 的平衡因子為 $+1$，仍平衡；節點 $40$ 的平衡因子為 $-2$，而插入路徑是從 $40$ 的右子樹進入其左子樹，因此屬於右左（RL）型。 先對 $50$ 右旋，再對 $40$ 左旋。旋轉後，$45$ 成為該子樹的新根，$40$ 與 $50$ 分別成為它的左右子節點： - $40$ 的左右子節點為 $35$、$43$。 - $50$ 的右子節點為 $55$。 - $65$ 的右子樹仍是 $70$，且 $70$ 的右子節點為 $80$。

Question 2

Perform the post-order traversal on the AVL tree constructed for the first question (Q1) after the insertion. What is the sequence of nodes in the post-order traversal of the AVL tree?

(A) $35\to43\to45\to55\to50\to40\to80\to70\to65$

(B) $35\to43\to55\to50\to45\to40\to80\to70\to65$

(C) $35\to43\to40\to55\to50\to45\to80\to70\to65$

(D) $65\to40\to35\to50\to45\to43\to55\to70\to80$

(E) None of the above

Accepted Answer

核心觀念 AVL 樹要求每個節點的左右子樹高度差至多為 $1$。插入節點後若失衡，依失衡節點與插入方向判斷旋轉方式。本題會用到「右左（RL）雙旋轉」。 後序走訪的順序是「左子樹、右子樹、根節點」，也就是先走完左右子樹，最後才記錄目前節點。 解題方法 圖中原樹的結構為：根節點 $65$ 的左右子節點是 $40$、$70$；$40$ 的左右子節點是 $35$、$50$；$50$ 的左右子節點是 $45$、$55$；$70$ 的右子節點是 $80$。將 $43$ 插入二元搜尋樹時，路徑是 $65	o40	o50	o45$，因此 $43$ 成為 $45$ 的左子節點。 插入後，節點 $40$ 的右子樹比左子樹高兩層，造成失衡；插入位置在 $40$ 的右子節點 $50$ 的左子樹，屬於右左（RL）情況。先對 $50$ 右旋，再對 $40$ 左旋，得到： - $45$ 成為 $65$ 的左子節點。 - $45$ 的左子節點為 $40$，其子節點為 $35$、$43$。 - $45$ 的右子節點為 $50$，其右子節點為 $55$。 - $65$ 的右子樹維持 $70$，而 $70$ 的右子節點為 $80$。 依後序規則，先走訪 $45$ 的左子樹，得到 $35	o43	o40$；再走訪右子樹，得到 $55	o50$；最後記錄 $45$。

Question 3

Remove the node with the key "65" from the AVL tree constructed for the first question (Q1) after the insertion. What does the array representation of the AVL tree look like?

(A) $(35,45,70,40,50,−,80,−,43,−,55)$

(B) $(55,45,70,40,50,−,80,43,35)$

(C) $(45,40,70,35,43,50,80,−,−,−,−,−,55)$

(D) $(45,40,70,55,43,50,80,35)$

(E) None of the above

Accepted Answer

核心觀念 AVL 樹除了符合二元搜尋樹的大小順序，還要求每個節點左右子樹高度差的絕對值不超過 $1$。刪除節點後，若某節點失衡，就要依失衡方向與子樹高度進行旋轉。 二元搜尋樹中，刪除有兩個子節點的節點時，可用其中序後繼（右子樹最小值）取代，再刪除後繼原本的位置。以下依此標準方式處理。 解題方法 圖中原樹的根節點是 $65$；其左子樹根為 $40$，右子樹根為 $70$。節點 $40$ 的左右子節點是 $35$、$50$；節點 $50$ 的左右子節點是 $45$、$55$；節點 $70$ 的右子節點是 $80$。 先依 Q1 插入 $43$：它會成為 $45$ 的左子節點，使節點 $40$ 右重，形成右左（RL）失衡。先對 $50$ 右旋，再對 $40$ 左旋，得到： 現在刪除根節點 $65$。其中序後繼是 $70$，以 $70$ 取代 $65$，再刪除原本的 $70$；此時 $80$ 留在根節點的右子樹：

Question 4

Please find the expression tree and answer the level-order traversal of the expression tree. When operators have the same precedence, please evaluate them sequentially in the order presented within the expression. For instance, in the expression "a + b + c," calculate "a + b" first before combining the result with "c."

(A) $-++-*ABB/E*E-CDAD$

(B) $+-+ -*E*B/ABCDE-AD$

(C) $-+* -+ABB/E*E-CDAD$

(D) $-+-+*AB/BE*E-CDAD$

(E) None of the above

Accepted Answer

核心觀念 運算式樹中，運算子是內部節點，運算元是葉節點。層序走訪（level-order traversal）從根節點開始，依照由上而下、每層由左至右的順序列出節點。 本題先依照運算子優先順序解析運算式：括號內優先，其次為乘除，最後為加減；同一優先順序的運算子則由左至右結合。 解題方法 先依規則補上運算次序： $$ (((B-(E/(A-D)))+E)+(CD))-(AB) $$ 因此，最外層運算是減法，根節點為 $-$；根節點的左子樹是前三項與 $CD$ 相加的結果，右子樹是 $AB$。 運算式樹如下： 依層由上而下、每層由左至右列出節點：

Question 5

What is the expression in prefix form? (A) $+--B/E-ADAB+ECD$ (B) $-BEAD/-AB-ECD++$ (C) $-+-B/E-AD+ECDAB$ (D) $+--/BE-ADAB+ECD$ (E) None of the above

Accepted Answer

核心觀念 把中序式轉成前序式，要先依優先序（、/ 高於 +、-）與結合律（同優先序由左至右）加上完整括號，確定每個運算子的運算元，再把運算子移到它的兩個運算元前面。 解題方法 1. 括號內與高優先序先結合： - $E/(A-D)$、$CD$、$AB$。 2. 剩下的 -、+、+、- 同優先序，由左至右結合： $$ \Big(\big((B-E/(A-D))+E\big)+CD\Big)-AB $$ 3. 由內而外寫成前序： - $A-D \Rightarrow -AD$ - $E/(A-D) \Rightarrow /E-AD$ - $B-E/(A-D) \Rightarrow -B/E-AD$ - $(\ldots)+E \Rightarrow +-B/E-ADE$ - $(\ldots)+CD \Rightarrow ++-B/E-ADECD$ - $(\ldots)-AB \Rightarrow -++-B/E-ADECDAB$ 前序式為 -++-B/E-ADECDAB。

Question 6

Given the following failure function in the KMP matching algorithm and a string “AAABAAAAABAA” with 12 characters, what are the values of the failure function for the entire string?

f(j)= \begin{cases} \text{largest }k<j,\text{ such that }p_0p_1\cdots p_k=p_{j-k}p_{j-k+1}\cdots p_j,&\text{if such a }k\geq0\text{ exists}\\ -1,&\text{otherwise} \end{cases}

(A) $-1,0,1,-1,0,1,2,0,-1,0,1,2$

(B) $-1,0,1,0,1,2,2,2,3,4,5,6$

(C) $-1,0,1,-1,0,1,2,2,3,4,5,6$

(D) $-1,-1,0,-1,-1,0,1,2,3,4,5,6$

(E) None of the above

Accepted Answer

核心觀念 KMP 的失敗函數 $f(j)$：$p0\ldots pj$ 中「既是前綴、又是後綴」的最長真子字串，其最後一個字元的索引 $k$；不存在則為 $-1$。遞迴計算：令 $k=f(j-1)$，若 $p{k+1}=pj$ 則 $f(j)=k+1$；否則令 $k\leftarrow f(k)$ 再比，直到 $k=-1$ 時比較 $p0$。 解題方法 字串 AAABAAAAABAA： | j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | $pj$ | A | A | A | B | A | A | A | A | A | B | A | A | | $f(j)$ | −1 | 0 | 1 | −1 | 0 | 1 | 2 | 2 | 2 | 3 | 4 | 5 | 關鍵幾格： - $f(3)$：B 與前綴開頭的 A 都不符 → $-1$。 - $f(7)$：$f(6)=2$，比 $p3=B
e A$；退到 $f(2)=1$，比 $p2=A=p7$ → $2$（最長相同前後綴為 AAA）。

Question 7

Determine the binary tree using the provided in-order and post-order traversals. What is the resulting pre-order traversal of the constructed binary tree?

In-order: $A,B,G,E,D,I,J,F,H,C$

Post-order: $G,E,J,I,H,F,D,C,B,A$

(A) $A,B,C,D,E,F,G,I,H,J$

(B) $A,B,G,E,D,C,I,J,F,H$

(C) $A,B,C,D,E,G,F,I,J,H$

(D) $A,B,C,D,E,F,G,I,J,H$

(E) None of the above

Accepted Answer

核心觀念 由中序（左-根-右）與後序（左-右-根）可唯一重建二元樹：後序的最後一個元素是根；在中序中找到根，左邊是左子樹、右邊是右子樹；再依子樹大小把後序切成左、右兩段，遞迴處理。 解題方法 - 中序：A, B, G, E, D, I, J, F, H, C - 後序：G, E, J, I, H, F, D, C, B, A 1. 後序最後是 A → 根為 A。中序中 A 在最前面 → A 沒有左子樹，右子樹的中序為 B,G,E,D,I,J,F,H,C，後序為 G,E,J,I,H,F,D,C,B。 2. 右子樹的根為 B（後序最後）。中序中 B 在最前面 → B 只有右子樹：中序 G,E,D,I,J,F,H,C；後序 G,E,J,I,H,F,D,C。 3. 根為 C。中序中 C 在最後 → C 只有左子樹：中序 G,E,D,I,J,F,H；後序 G,E,J,I,H,F,D。 4. 根為 D。中序切成左 {G,E}、右 {I,J,F,H}；後序對應切成 G,E 與 J,I,H,F。 - 左子樹：後序 G,E → 根 E，中序 G,E → G 是 E 的左子節點。 - 右子樹：後序 J,I,H,F → 根 F；

Question 8

Please use the cost on each edge as the weight and perform Dijkstra’s algorithm starting from vertex A. What is the order in which the vertices are selected by Dijkstra’s algorithm?

(A) $A\to B\to D\to F\to E\to C$

(B) $A\to C\to E\to B\to D\to F$

(C) $A\to B\to D\to E\to C\to F$

(D) $A\to B\to C\to D\to F\to E$

(E) None of the above

Accepted Answer

核心觀念 Dijkstra 演算法適用於邊權重皆非負的有向圖。從起點 $A$ 開始，每一步選出「尚未確定最短距離、暫定距離最小」的頂點，並用它更新相鄰頂點的暫定距離。頂點被選出時，其起點最短距離即已確定。 解題方法 圖中可讀到的有向邊與權重為：$A	o B$ 權重 $10$、$A	o C$ 權重 $15$、$B	o D$ 權重 $12$、$B	o F$ 權重 $15$、$D	o F$ 權重 $1$、$D	o E$ 權重 $2$、$F	o E$ 權重 $5$、$C	o E$ 權重 $10$。依邊的箭頭方向，從 $A$ 執行 Dijkstra： 1. 選出起點 $A$，距離為 $0$。更新 $B=10$、$C=15$。 2. 未確定的頂點中，$B$ 距離最小，選出 $B$。更新 $D=10+12=22$、$F=10+15=25$。 3. $C$ 距離為 $15$，小於 $D$ 的 $22$ 與 $F$ 的 $25$，選出 $C$。更新 $E=15+10=25$。 4. $D$ 距離為 $22$，選出 $D$。經由 $D$ 到 $F$ 的距離為 $22+1=23$，比原本的 $25$ 短；到 $E$ 的距離為 $22+2=24$，比原本的 $25$ 短。 5. $F$ 的距離為 $23$，選出 $F$。經由 $F$ 到 $E$ 的距離為 $23+5=28$，不會改善 $E$ 的距離 $24$。 6. 最後選出 $E$，距離為 $24$。

Question 9

What is the topological ordering of the graph? You must choose the node with the label that has the smallest alphabetical order first, when finding the topological order.

(A) $A\to B\to D\to F\to E\to C$

(B) $A\to C\to E\to B\to D\to F$

(C) $A\to B\to D\to E\to C\to F$

(D) $A\to B\to C\to D\to F\to E$

(E) None of the above

Accepted Answer

核心觀念 拓樸排序是將有向無環圖的頂點排列成線性順序，使每條有向邊 $u	o v$ 都符合「$u$ 排在 $v$ 前面」。可用入度法逐步處理：每次從目前入度為 $0$ 的頂點中，選標籤字母順序最小者加入排序，再移除它的出邊。 解題方法 圖中有向邊為 $A	o B$、$A	o C$、$B	o D$、$B	o F$、$D	o F$、$D	o E$、$F	o E$、$C	o E$。題目要求每一步都優先選字母順序最小的入度為 $0$ 頂點；邊上的權重與拓樸排序無關。 | 步驟 | 入度為 $0$ 的頂點 | 選取 | |---|---|---| | 1 | $A$ | $A$ | | 2 | $B, C$ | $B$ | | 3 | $C, D$ | $C$ | | 4 | $D$ | $D$ | | 5 | $F$ | $F$ | | 6 | $E$ | $E$ | 因此拓樸順序為 $A	o B	o C	o D	o F	o E$。 選項分析

Question 10

請回答以下 C 語言程式碼執行後在螢幕上顯示之結果，共兩項輸出（各 5%）。 int main() { int num = 250; printf("%X
", num); printf("%.2f
", (float)num); return 0; }

Accepted Answer

核心觀念 這題考 printf 的格式指定符與數值表示方式： - %X：以大寫十六進位輸出整數。 - %.2f：以小數形式輸出浮點數，並在小數點後保留兩位。 - (float)num：將整數 num 轉型為 float。呼叫 printf 時，float 會自動提升為 double。 解題方法 先依格式指定符分別計算兩項輸出。 第一項：十六進位 十進位 $250$ 轉為十六進位： $$ 250 = 15 	imes 16 + 10 $$ 餘數由後往前讀，$15$ 對應十六進位的 F，$10$ 對應 A，因此： $$ 250{10} = \mathrm{FA}{16} $$ %X 使用大寫字母輸出，所以第一行為 FA。 第二項：浮點數格式

Question 11

請回答以下 C 語言程式碼執行後在螢幕上顯示之結果。

int main() {
int arr[] = {10, 20, 30, 40, 50};
int *ptr;
int sum = 0;
int i;

for (i = 0; i < 5; i++) {
    ptr = &arr[i];
    if (i % 2 == 0)
        sum += *ptr;
}

printf("%d", sum);

}

Accepted Answer

核心觀念 陣列 arr 的索引從 $0$ 開始，因此 arr[i] 是第 $i$ 個元素。&arr[i] 取得該元素的位址，指定給指標 ptr 後，ptr 就是該位址所存放的值。 條件 i % 2 == 0 用來判斷 $i$ 是否為偶數；只有條件成立時，程式才會把 ptr 加進 sum。 解題方法 每次迴圈先讓 ptr 指向 arr[i]，再依照索引是否為偶數決定要不要累加： | i | arr[i] | ptr 指向的值 | 是否累加 | sum | |---:|---:|---:|:---:|---:| | 0 | 10 | 10 | 是 | 10 |

Question 12

請回答以下 C 語言程式碼執行後在螢幕上顯示之結果。 void fun1(char str) { char end = str; char temp; if (str) { while (end) { ++end; } --end; while (str < end) { temp = str; str++ = end; end-- = temp; } } } int main() { char str[] = "13579"; fun1(str); int number = atoi(str); printf("%d
", number % 10); return 0; }

Accepted Answer

核心觀念 本題考查指標走訪字串、原地反轉字串，以及整數取餘數。 C 語言字串以 '\0' 作為結尾標記。end 從字串開頭一路前進，直到 end == '\0'，再往前退一格，便會指向最後一個字元。接著，程式用 str 與 end 分別由前、後往中間移動，交換兩端字元，完成原地反轉。 解題方法 初始字串是 "13579"，記憶體中的字元依序為： | 索引 | 0 | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---|---| | 字元 | '1' | '3' | '5' | '7' | '9' | '\0' | while (end) 結束時，end 指向 '\0'；執行 --end 後，end 指向最後一個字元 '9'。 交換過程如下： 1. str 指向 '1'，end 指向 '9'，交換後字串為 "93571"。 2. 指標往內移動，str 指向 '3'，end 指向 '7'，交換後字串為 "97531"。

Question 13

Write a C++ program to find the largest factor of a number (the user supplies the number). The program is partially completed for you. Please only fill the missing parts. You should not introduce any new blocks.

number = 24, largest factor = 12

#include <iostream>
using namespace std;

int main() {
int number;
cout << “Enter an integer that is larger than 1: ”;
____; // line (A) (2%)

if (number <= 1) return -1;

int factor = number - 1;
while (____) // line (B) (3%)
    factor--;

cout << “The largest factor is: ” << factor << endl;
return 0;

}

Accepted Answer

核心觀念 因數是能整除某整數的正整數。題目範例把 $24$ 的最大因數定義為小於 $24$ 的最大因數，因此要找的是「最大真因數」，不包含數字本身。 解題方法 先讀入整數。factor 從 number - 1 開始，依序往下檢查；當 number 除以 factor 的餘數為 $0$，就找到因數並停止。由於檢查順序是由大到小，第一個找到的因數就是最大真因數。 兩個空格應填入： 以 $24$ 為例，factor 從 $23$ 開始往下遞減。$23$ 到 $13$ 都無法整除 $24$；當 factor 為 $12$ 時，$24 \bmod 12 = 0$，迴圈停止並輸出 $12$。 關鍵程式碼

Question 14

Find the best match of each term with the descriptions by writing a letter from 1 to 10 in each of the blanks.

Terms:

(A) function declaration
(B) if-else statement
(C) break statement
(D) pass by value
(E) local variable
(F) void
(G) float
(H) cast
(I) promotion
(J) overloaded function

Descriptions:

A variable declared inside a function
The default method in C++ of passing arguments to parameters
The type in C++ of the constant 5.0F
The type in C++ which has no values
A variable inside of a class definition. If $n$ and $m$ are of type int, the programmer can insert this to request the int in $n$ to be converted to an equivalent value of type double before the division operation occurs, as in this expression: $(\text{double})n/m$
A specification of a function name, its list of parameter types, and its return type
Selects one of two choices of statements to execute depending on a condition
Causes execution to leave an 'if', 'switch', or a loop and continue at the next statement after the one that was left
A function name that has more than one definition
Conversion of char to int or float to double

Accepted Answer

核心觀念

本題考查 C++ 的基本名詞，包括變數作用範圍、參數傳遞方式、資料型別、型別轉換、函式宣告與控制流程。配對時，先抓各描述中的關鍵字，再用程式語意確認。

解題方法

逐題辨認描述的核心概念：

「函式內宣告的變數」對應區域變數。
「預設的引數傳遞方式」對應傳值呼叫。
5.0F 的尾綴 F 指定型別為 float。
void 表示沒有值。
(double)n 將 n 轉成 double，屬於型別轉型。
char 轉成 int、float 轉成 double，屬於型別提升。
依條件選擇兩種敘述之一，是 if-else；離開迴圈或 switch 則是 break。
同名函式有多個定義，稱為多載函式。

選項分析

(A) function declaration：對應第 6 題。
函式宣告描述函式名稱、參數型別清單與回傳型別，讓編譯器知道函式的介面。

(B) if-else statement：對應第 7 題。
if-else 根據條件真假，選擇兩組敘述中的一組執行。

(C) break statement：對應第 8 題。
break 會結束最內層的迴圈或 switch，從該結構之後的敘述繼續執行。嚴格來說 break 不能單獨跳出 if（if 裡的 break 跳出的是包住它的迴圈或 switch）；原題第 8 項把 if 也列進去並不精確，但在所有術語中，「離開結構、跳到其後繼續執行」最符合的仍是 break。

(D) pass by value：對應第 2 題。
C++ 一般參數傳遞方式為傳值：函式收到引數的值之副本，對參數的修改不會直接改變呼叫端的原變數。

(E) local variable：對應第 1 題。
在函式內宣告的變數是區域變數，其作用範圍通常限於所屬函式或區塊。

(F) void：對應第 4 題。
void 表示沒有值，例如函式回傳型別為 void 時，代表函式不回傳值。

Question 15

The solution of the recurrence $T(n)=3T\left(\frac{n}{5}\right)+n$ is (A) $n^{3/5}$ (B) $n$ (C) $n^{5/3}$ (D) $n^{\log5 3}$ (E) $n\log n$

Accepted Answer

核心觀念 這題考遞迴式的漸近解，可用主定理（Master Theorem）判斷。對形式 $$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$ 先比較 $f(n)$ 與 $n^{\logb a}$ 的成長速度。 本題中 $a=3$、$b=5$、$f(n)=n$，因此比較 $n$ 與 $n^{\log5 3}$。 解題方法 計算遞迴子問題所對應的指數： $$ \log5 3 \approx 0.683 $$ 因此 $n^{\log5 3}$ 的成長速度低於 $n$。更精確地說，存在常數 $\varepsilon0$，使得 $$ n^{\log5 3}=O(n^{1-\varepsilon}) $$ 這屬於主定理第三種情況的候選條件。再檢查規則性條件： $$ 3f\left(\frac{n}{5}\right) =3\cdot\frac{n}{5} =\frac{3}{5}n \le cn $$ 其中可取常數 $c=\frac{3}{5}<1$，所以規則性條件成立。依主定理第三種情況： $$ T(n)=\Theta(f(n))=\Theta(n) $$ 選項分析

Question 16

The solution of the recurrence $T(n)=4T\left(\frac{n}{4}\right)+n\log n$ is (A) $n^2$ (B) $n\log n$ (C) $n\log^2 n$ (D) $n\log^{(2)}n$ (E) $n\log n^2$

Accepted Answer

核心觀念 本題考遞迴式的漸近解，可用 Master 定理。對形式 $$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$ 先比較 $f(n)$ 與 $n^{\logb a}$。若 $$ f(n)=\Theta\left(n^{\logb a}\log^k n\right),\qquad k\ge 0 $$ 則 $$ T(n)=\Theta\left(n^{\logb a}\log^{k+1}n\right). $$ 解題方法 本題中 $a=4$、$b=4$，所以 $$ n^{\logb a}=n^{\log4 4}=n. $$ 非遞迴項為 $f(n)=n\log n$，因此 $$ f(n)=\Theta\left(n^{\log4 4}\log^1 n\right). $$ 符合 Master 定理的上述情形，取 $k=1$，得到 $$ T(n)=\Theta\left(n\log^2 n\right). $$ 所以正確選項是 (C)。 選項分析 - (A) $n^2$：錯誤。 遞迴樹第 $i$ 層有 $4^i$ 個子問題、每個大小 $n/4^i$，該層成本為 $4^i\cdot\frac{n}{4^i}\log\frac{n}{4^i}=n(\log n-i\log 4)$，逐層遞減；

Question 17

The solution of the recurrence $T(n)=4T\left(\frac{n}{2}\right)+n^3$ is (A) $n^{1/2}$ (B) $n$ (C) $n^2$ (D) $n^3$ (E) $n^2\log n$

Accepted Answer

核心觀念 這題考遞迴式的漸近解，可用主定理。對形式 $$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$ 先比較 $f(n)$ 與 $n^{\logb a}$。其中 $a$ 是子問題數量，$b$ 是每次縮小的比例。 解題方法 本題中 $a=4$、$b=2$、$f(n)=n^3$。先計算遞迴部分的基準量： $$ n^{\logb a}=n^{\log2 4}=n^2 $$ 因為 $f(n)=n^3$ 比 $n^2$ 多一個多項式階，因此檢查主定理第三種情況的正則條件： $$ a f\left(\frac{n}{b}\right) =4\left(\frac{n}{2}\right)^3 =\frac{n^3}{2} \leq c n^3 $$ 取 $c=\frac12<1$，正則條件成立。因此由主定理第三種情況： $$ T(n)=\Theta(n^3) $$

Question 18

Determine if the following statement is true or false: “There is no polynomial time algorithm that can find the value of an $s$-$t$ minimum cut in a directed graph.”

Accepted Answer

核心觀念 這題考的是有向圖的最小割與最大流。 給定有向圖 $G=(V,E)$、源點 $s$、匯點 $t$，一個 $s$-$t$ 割將頂點分成兩個集合 $S$ 與 $T$，滿足 $s\in S$、$t\in T$。割的容量是所有從 $S$ 指向 $T$ 的邊容量總和： $$ c(S,T)=\sum{\substack{(u,v)\in E\u\in S,\ v\in T}} c(u,v) $$ $s$-$t$ 最小割的值，是所有符合條件的割中容量最小者。 最大流最小割定理指出：有向圖中的最大 $s$-$t$ 流值等於最小 $s$-$t$ 割容量。因此，只要用多項式時間演算法求最大流，就能求得最小割的值。 解題方法

Question 19

Determine if the following statement is true or false: “Both the subroutines ‘Merge’ in Merge sort and ‘Partition’ in Quicksort are linear time operations.”

Accepted Answer

核心觀念 本題考查排序演算法中兩個子程序的時間複雜度： - Merge sort 的 Merge：將兩個已排序的子陣列合併成一個有序陣列。 - Quicksort 的 Partition：依照樞紐值重新排列子陣列，使樞紐值左側的元素不大於它，右側的元素不小於它。 若子程序處理的元素數量為 $n$，每個元素只需被檢查或搬移常數次，該子程序的時間複雜度就是 $\Theta(n)$，也稱為線性時間。 解題方法 Merge 為線性時間。 設兩個已排序子陣列的長度分別為 $m$ 與 $n$。合併時，每一步比較兩個子陣列目前尚未處理的元素，將較小者放入結果；每個元素都會被取出並放入結果一次。因此總工作量與元素總數成正比： $$ \Theta(m+n) $$ 若兩個子陣列合計有 $N$ 個元素，則 Merge 的時間複雜度為 $\Theta(N)$。

Question 20

Determine if the following statement is true or false: “Find the median of $n$ elements takes $\Omega(n\log n)$ time for any algorithms working in the comparison-based model.”

Accepted Answer

核心觀念 題目考查比較式模型下的「選擇問題」與「排序問題」之差異。找中位數只需找出排序後位於中央的元素，不必排好所有元素。 比較式模型中，中位數可在最壞情況 $O(n)$ 時間內找出；因此不能說所有演算法都需要 $\Omega(n\log n)$ 時間。 解題方法 使用中位數的中位數選擇演算法，可在最壞情況線性時間內找出第 $k$ 小元素。令 $k=\lceil n/2\rceil$，即可取得中位數。 此演算法每次將元素分組、找出各組中位數，再以這些中位數選出樞紐並進行分割。遞迴式可寫為： $$ T(n)\leq T(n/5)+T(7n/10+O(1))+O(n) $$

Question 21

Determine if the following statement is true or false: “Given $T$ is a minimum spanning tree of a graph $G$, for any pair of vertices $(s,t)$, the shortest path from $s$ to $t$ in $G$ is the path from $s$ to $t$ in $T$.”

Accepted Answer

核心觀念

最小生成樹（Minimum Spanning Tree, MST）是在連通圖中，選出連接所有頂點且不含環的邊集合，使所有樹邊權重總和最小。

最短路徑則是針對指定的兩個頂點，尋找讓路徑上邊權重總和最小的路徑。兩者最佳化的目標不同，因此最小生成樹不保證保留每一對頂點之間的最短路徑。

解題方法

用反例判斷敘述是否成立。考慮一個有三個頂點 $s,a,t$ 的三角形，邊權重如下：

w(s,a)=2,\qquad w(a,t)=2,\qquad w(s,t)=3

選取 $(s,a)$ 與 $(a,t)$ ，總權重為 $2+2=4$ ；選取 $(s,a)$ 與 $(s,t)$ ，總權重為 $2+3=5$ ；選取 $(a,t)$ 與 $(s,t)$ ，總權重也為 $2+3=5$ 。因此，最小生成樹由 $(s,a)$ 與 $(a,t)$ 組成。

Question 22

The following graph (graph on the left-hand side with 6 vertices) describes a flow assignment in a flow network. The notation $x/y$ describes $x$ units of flow in an edge with capacity $y$. Determine if it reaches the maximum flow. If your answer is yes, demonstrate how to derive such flow assignment. If your answer is no, then calculate its maximum flow.

Accepted Answer

核心觀念 最大流問題要在每條邊的流量不超過容量，且中間節點流入量等於流出量的條件下，讓來源點 $s$ 到終點 $t$ 的流量總和最大。依增廣路定理，只要殘餘網路中還有 $s$ 到 $t$ 的增廣路，就能增加流量；若能找到容量等於流量值的割，便可證明此流量已是最大流。 解題方法 圖中頂點為 $s,a,b,c,d,t$；邊上的標示為「流量／容量」。原流量包括 $s	o a$ 的 $1/4$、$s	o b$ 的 $6/6$、$b	o a$ 的 $3/7$、$a	o c$ 的 $4/5$、$c	o b$ 的 $0/2$、$b	o d$ 的 $3/3$、$c	o d$ 的 $1/4$、$c	o t$ 的 $3/6$，以及 $d	o t$ 的 $4/4$。 目前流量值為 $s$ 的流出量 $1+6=7$，也等於 $t$ 的流入量 $3+4=7$。但殘餘網路中有一條增廣路：

Question 23

Given the above graph (graph on right-hand side with 5 vertices), determine if each of the following algorithm options (a-h) can be used to find the shortest paths of user-specified pair/pairs of vertices:

(a) Kruskal’s algorithm

(b) Dijkstra’s algorithm

(c) Ford-Fulkerson algorithm

(d) Johnson’s algorithm

(e) Bellman-Ford algorithm

(f) Jarvis’s march algorithm

(g) Floyd-Warshall algorithm

(h) Huffman algorithm

Accepted Answer

核心觀念 本題考查各演算法的用途，以及它們對圖形條件的要求。右側圖是有向加權圖，包含負權邊；負權邊不一定代表沒有最短路徑，關鍵是圖中是否存在負權環。Johnson、Bellman–Ford、Floyd–Warshall 都能處理負權邊，但要求相關範圍內沒有負權環。 解題方法 讀圖可得頂點為 $a,b,c,d,e$，有向邊與權重如下：$b	o a$ 權重 $3$、$a	o c$ 權重 $7$、$a	o d$ 權重 $1$、$e	o a$ 權重 $4$、$b	o e$ 權重 $8$、$b	o c$ 權重 $-4$、$d	o b$ 權重 $2$、$c	o d$ 權重 $6$、$d	o e$ 權重 $-5$。 圖上有負權邊，因此 Dijkstra 的非負權重前提不成立。這張圖沒有負權環：取勢能值 $h(a)=-1,\ h(b)=0,\ h(c)=-4,\ h(d)=0,\ h(e)=-5$，並將每條邊的權重改寫為 $w'(u,v)=w(u,v)+h(u)-h(v)$，各邊的新權重依序為 $4,10,0,0,13,0,2,2,0$，全部非負。沿任一環的勢能項會互相抵消，所以原環權重等於新權重總和，不可能為負。 因此，可用支援負權邊且適用範圍內無負權環的最短路徑演算法；再依題目要找單一來源或多組頂點間的路徑，判斷演算法的範圍是否符合。 選項分析 (a) Kruskal’s algorithm：不可以。 Kruskal 用來求無向圖的最小生成樹，按邊權重由小到大選邊；它不是求有向圖中頂點間最短路徑的演算法。 (b) Dijkstra’s algorithm：不可以。 Dijkstra 的正確性要求邊權重皆非負，本圖含有 $-4$ 與 $-5$ 的邊。貪婪地確定某頂點距離後，後續負權邊可能使它的距離變短，故不能保證得到正確最短路徑。

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

第 1 題3 分

核心觀念

解題方法

第 2 題3 分

第 3 題3 分

第 4 題3 分

第 5 題3 分

第 6 題3 分

第 7 題3 分

第 8 題2 分

第 9 題2 分

第 10 題10 分

核心觀念

解題方法

第 11 題10 分

第 12 題5 分

核心觀念

解題方法

第 13 題5 分

第 14 題20 分

核心觀念

解題方法

選項分析

第 15 題2 分

第 16 題2 分

核心觀念

解題方法

選項分析

第 17 題2 分

核心觀念

解題方法

第 18 題2 分

核心觀念

解題方法

第 19 題2 分

核心觀念

解題方法

第 20 題2 分

第 21 題2 分

核心觀念

解題方法

第 22 題3 分

第 23 題8 分

核心觀念

解題方法

選項分析

其他考古題

113 年中正大學的其他科目

中正大學《軟體設計》其他年度

其他學校的資工系考古題

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