108 地方特考三等 資訊處理 程式語言 考古題詳解

核心觀念

1. 時間複雜度與大 $O$ 符號（Big-$O$ Notation）： 用來衡量演算法執行時間隨輸入規模 $n$ 增長的漸近上限（Asymptotic Upper Bound）。定義為：若存在正常數 $c$ 與 $n_0$，使得當 $n \ge n_0$ 時，$T(n) \le c \cdot f(n)$，則記為 $T(n) = O(f(n))$。
2. 循序程式碼的加法法則（Addition Rule / Sum Rule）： 當程式由多個依序執行的獨立程式區塊組成時，總時間為各區塊時間之和。若區塊執行的複雜度分別為 $T_1(n) = O(f(n))$ 與 $T_2(n) = O(g(n))$，則總時間複雜度由成長速率最高的主導項（Dominant Term）決定： $T(n) = T_1(n) + T_2(n) = O(\max(f(n), g(n)))$
3. 巢狀迴圈的乘法法則（Multiplication Rule）： 當迴圈內部包含另一層迴圈，且內外層計數器互不干涉時，總運算次數為各層迴圈執行次數的乘積。

---

解題方法

本題給定一個輸入規模為 $n$ 的函式 A(n)，分析其各程式區塊的執行頻率與基本運算次數：

1. 變數初始化與常數輸出區塊：

• int a = 0;、int b = 0; 各執行 1 次。
• printf("Hello"); 與 printf("World"); 各執行 1 次。
• 這些基本運算的執行次數不隨 $n$ 改變，時間花費為常數時間： $T_{\text{const}} = O(1)$

2. 第一段：單層 for 迴圈：

for (int i = 0; i < n; i++) {
a++;
}

• 迴圈計數器 $i$ 由 $0$ 遞增至 $n-1$，共執行 $n$ 次。
• 迴圈本體 a++; 執行 $n$ 次。
• 此區塊執行時間與 $n$ 成正比： $T_1(n) = O(n)$

核心觀念

本題為標準的程式邏輯與靜態程式碼分析（Static Code Analysis）題型，主要測驗以下三大核心觀念：

1. 迴圈控制結構（Loop Control Structure）與終止條件：

• while 迴圈必須具備推進迴圈狀態的機制。迴圈控制變數（Loop Control Variable）必須在迴圈主體內被合理修改，否則將導致無法終止的無窮迴圈（Infinite Loop）。

2. 布林邏輯運算與數值區間：

• 邏輯運算子 ||（OR，聯集）與 &&（AND，交集）的求值。
• 恆真式（Tautology）：條件運算式對所有定義域內的數值皆成立。
• 矛盾式／恆假式（Contradiction）：條件運算式對所有定義域內的數值皆不成立。

3. 分支結構與無效程式碼（Dead Code / Unreachable Code）：

• 多重分支結構（if-else if-else）由上而下依序評估，若前置條件已涵蓋所有可能情況，後續分支將永遠無法被觸發，成為無效程式碼。

---

解題方法

由外向內、由整體到區域逐步推導剖析程式碼結構：

步驟一：分析迴圈控制結構（while (s < 30)）

• 進入迴圈的先決條件為 $s < 30$。
• 檢視 while 迴圈區塊內部，程式碼僅對變數 t 進行遞增（t++）或遞減（t--）操作，變數 s 在迴圈內部完全沒有任何被更新或重新指派的陳述式。
• 若使用者輸入之 $s < 30$，$s$ 的值將永遠保持不變，使得條件 $s < 30$ 永遠成立，程式將陷入無窮迴圈，永遠無法執行到後續的 system("pause") 與 return 0。

步驟二：分析條件分支的區間邏輯

1. 第一分支：if (s < 100 || s > 50)

• 邏輯運算子為 ||（聯集）。在數線上分析其涵蓋範圍： $(-\infty, 100) \cup (50, \infty) = (-\infty, \infty) = \mathbb{R}$ 無論變數 $s$ 為任何整數，此條件恆為真（Tautology）。
• 加上外層迴圈已限制 $s < 30$，而 $s < 30 \implies s < 100$ 必然成立。因此只要程式能進入迴圈，第一分支必定成立並執行 t++。

2. 第二分支：else if (s > 60 && s < -1)

• 邏輯運算子為 &&（交集）。在數線上分析其涵蓋範圍： $(60, \infty) \cap (-\infty, -1) = \emptyset$ 沒有任何實數或整數可以「同時大於 $60$ 且小於 $-1$」，此條件恆為假（Contradiction）。
• 此外，因第一分支已恆為真，第二分支在結構上屬於永遠無法執行到的死碼（Unreachable Code）。

3. 第三分支：else if (s > 10 && s < 100) 與 第四分支：else

• 雖然 $s \in (10, 100)$ 本身在數學區間上具有合理交集，但由於其前方的 if (s < 100 || s > 50) 已經攔截了所有可能的 $s$ 值，因此第三分支與最後的 else 分支皆完全無法被執行，同樣屬於死碼。

核心觀念

本題為 C++ 物件導向程式設計（OOP）的經典考題，評量重點在於繼承（Inheritance）​與多型（Polymorphism）​的實作機制：

1. 靜態繫結（Static Binding / 早期繫結）： 一般成員函式（未宣告 virtual）在編譯時期即決定呼叫版本。透過指標呼叫時，系統依據「指標的宣告型別（Static Type）」決定呼叫哪一個類別的函式。
2. 動態繫結（Dynamic Binding / 晚期繫結）： 宣告為 virtual 的虛擬函式，在執行時期透過虛擬函式表（vtable）​機制，依據「指標實際指向的物件型別（Dynamic Type）」動態決定呼叫對應的衍生類別覆寫（Override）版本。
3. 建構子執行順序與成員初值列（Member Initializer List）： 建立衍生類別物件時，會優先執行基底類別建構子，再執行衍生類別建構子；建構子後的 : member(value) 會將成員變數初始化為指定數值。

---

解題方法

解題切入點在於追蹤物件實體化過程，並釐清指標 a 的「宣告型別」與「實體型別」，進而推導各成員函式與變數的存取結果：

步驟一：物件實體化與初始化

B b;

1. 建立衍生類別 B 的物件 b。
2. 呼叫順序：

• 先執行基底類別 A 的建構子：執行 testa(100)，將 b 繼承自 A 的成員變數 testa 設為 $100$。
• 再執行衍生類別 B 的建構子：執行 testb(300)，將 b 自身的成員變數 testb 設為 $300$。

步驟二：指標指派（Upcasting）

A *a = &b;

• 指標 a 的靜態型別（宣告型別）​為 A*。
• 指標 a 的動態型別（實際指向物件）​為 B 的實體。

---

輸出逐行分析

本題為非選擇題（程式追蹤輸出題），逐行推導各輸出行之結果如下：

核心觀念

本題評量 C 語言的字串走訪、ASCII 字元編碼特性以及多分支條件控制流程：

1. 字串結尾字元（Null Terminator）：C 語言字串以 '\0'（ASCII 碼為 0）作為終止標記。迴圈條件 a[i] != '\0' 即用來循序走訪字串中的每個有效字元，直至字串結束。
2. ASCII 編碼之連續性：

• 英文小寫字母 'a' 至 'z'（ASCII $97 \sim 122$）與大寫字母 'A' 至 'Z'（ASCII $65 \sim 90$）之編碼均為連續區間，可直接使用關係運算子進行區間判斷。
• 阿拉伯數字字元 '0' 至 '9'（ASCII $48 \sim 57$）亦為連續區間。

3. 多分支決策結構（if - else if - else）：

• 第一層 if：判斷字元是否為英文字母（小寫或大寫），符合則計數器 $k_1$ 加 1。
• 第二層 else if：若非字母，進一步判斷是否為數字字元，符合則計數器 $k_2$ 加 1。
• 最終層 else：既非英文字母亦非數字字元之其他符號，計數器 $k_3$ 加 1。

---

解題方法

題目中宣告的字串陣列為： $a[\,] = \text{"aA123bd45YH*\#*"}$

字串內各字元索引與對應分類之逐步追蹤如下表所示：

索引 $i$	字元 $a[i]$	判定條件	符合之分支	累計計數器狀態 ($k_1, k_2, k_3$)
$0$	'a'	屬於 'a'～'z'	第一層 if	$(1, 0, 0)$
$1$	'A'	屬於 'A'～'Z'	第一層 if	$(2, 0, 0)$
$2$	'1'	屬於 '0'～'9'	第二層 else if	$(2, 1, 0)$
$3$	'2'	屬於 '0'～'9'	第二層 else if	$(2, 2, 0)$
$4$	'3'	屬於 '0'～'9'	第二層 else if	$(2, 3, 0)$
$5$	'b'	屬於 'a'～'z'	第一層 if	$(3, 3, 0)$