112 年 國立中正大學資訊工程學系碩士班乙組《計算機概論（含程式設計）》

這題考驗對遞迴函數呼叫次數的理解。

遞迴函數 a(n) 的定義如下：

• 當 n 等於 0 時，回傳 1。
  -否則，回傳 n 乘以 a(n-1) 的結果。

我們要計算 a(15) 會產生多少次函數呼叫。
當我們呼叫 a(15) 時：

• a(15) 呼叫 a(14)
• a(14) 呼叫 a(13)
• ...
• a(1) 呼叫 a(0)

核心觀念

本題考查 C 語言 for 迴圈的執行順序：

$$\text{初始化} \rightarrow \text{條件判斷} \rightarrow \text{執行迴圈本體} \rightarrow \text{更新運算}$$

程式中的變數初值為：

• score = 2
• all_num_test = 5
• num_test = 0
• final_score = 0

每次迴圈執行完 printf 後，才會執行：

num_test++;
final_score += score;

因此，第一次列印時的 final_score 仍是初始值 $0$。

解題方法

逐次追蹤 num_test 與 final_score：

迴圈次數	num_test 進入條件時的值	列印的 final_score	更新後的 final_score
1	0	0	2
2	1	2	4
3	2	4	6
4	3	6	8
5	4	8	10

第五次更新後，num_test 變成 $5$，條件

num_test < all_num_test

變成 $5 < 5$，結果為假，迴圈結束。

所以實際輸出為：

0 2 4 6 8

選項分析

這題考驗對資料結構操作方式的理解，特別是函數 f(x) 和 g() 如何存取陣列 A 及指標 p，來模擬某種資料結構的操作。

首先，我們來分析函數 f(x) 和 g() 的行為：

函數 f(x):

1. p \leftarrow p + 1: 指標 p 先遞增。這意味著下一個元素將被寫入陣列的「下一個」可用位置。
2. A[p] \leftarrow x: 將輸入值 x 存入陣列 A 中，索引是遞增後的 p。
   這個函數的作用是將元素 x 放入陣列 A 中，並且 p 指向這個剛放入元素的下一個位置，準備好接收下一個元素。這是一個「加入」元素的動作。

函數 g():

1. x \leftarrow A[p]: 從陣列 A 中取出一個元素，索引是當前的 p，並將其值存入變數 x。
2. p \leftarrow p - 1: 指標 p 遞減。這意味著下一次存取將會是「前一個」元素。
3. return x: 回傳取出的元素值。
   這個函數的作用是從陣列 A 中取出一個元素，並且 p 指向這個剛取出元素的「前一個」位置。這是一個「移除」或「讀取」元素的動作。

現在我們來觀察 p 的行為：

• f(x) 總是讓 p 遞增，並在新的 p 位置寫入。
• g() 總是從當前 p 位置讀取，然後讓 p 遞減。

假設 p 和 q 最初都初始化為 0。
當我們連續呼叫 f(x) 幾次，例如 f(10), f(20), f(30)：

• 第一次 f(10): p 變為 1, A[1] = 10。

這題考驗對 C 語言迴圈、條件判斷、輸入處理以及變數更新的理解。我們要模擬程式執行，並記錄變數 s, g, z, i 在迴圈結束時的值。

程式碼首先初始化了五個整數變數：z = 0, g = 0, s = 0, i = 0。變數 t 沒有被初始化，但會在 scanf 中被賦值。
迴圈的條件是 i < 6，這表示迴圈會執行 6 次，因為 i 從 0 開始，每次加 1。
使用者輸入的數字序列是 -1, -2, -3, 1, 2, 3，總共有 6 個數字，正好對應迴圈執行的次數。

我們來逐步追蹤變數的變化：

迴圈前:
z = 0, g = 0, s = 0, i = 0

第一次迭代:

• 迴圈條件: i < 6 (0 < 6) 為真。
• scanf("%d", &t);: 讀取第一個輸入 -1，所以 t = -1。
• s = s + t;: s 變為 0 + (-1) = -1。
• if (t >= 0): t 是 -1，條件 -1 >= 0 為假。
• else z++;: z 變為 0 + 1 = 1。
• i += 1;: i 變為 0 + 1 = 1。
• 結束時: z = 1, g = 0, s = -1, i = 1。

第二次迭代:

• 迴圈條件: i < 6 (1 < 6) 為真。
• scanf("%d", &t);: 讀取第二個輸入 -2，所以 t = -2。
• s = s + t;: s 變為 -1 + (-2) = -3。
• if (t >= 0): t 是 -2，條件 -2 >= 0 為假。
• else z++;: z 變為 1 + 1 = 2。
• i += 1;: i 變為 1 + 1 = 2。
• 結束時: z = 2, g = 0, s = -3, i = 2。

第三次迭代:

• 迴圈條件: i < 6 (2 < 6) 為真。
• scanf("%d", &t);: 讀取第三個輸入 -3，所以 t = -3。
• s = s + t;: s 變為 -3 + (-3) = -6。
• if (t >= 0): t 是 -3，條件 -3 >= 0 為假。
• else z++;: z 變為 2 + 1 = 3。

這題考驗對 C 語言字串指標操作、迴圈嵌套以及字串比較的理解。函數 f 的目的是尋找字串 s 中第一個在字串 t 中也出現的字元，並回傳該字元在 s 中的索引。

函數 f 接受兩個字串指標 s 和 t 作為參數。
它使用兩個指標 p1 和 p2 來遍歷這兩個字串。
p1 從 s 的開頭開始，p2 從 t 的開頭開始。

外層迴圈: for (p1 = s; *p1; p1++)

• p1 初始化為指向字串 s 的第一個字元。
• 迴圈繼續的條件是 *p1 (即 p1 所指向的字元) 不是字串結束符 \0。
• p1++ 讓 p1 指向字串 s 中的下一個字元。
  此迴圈遍歷字串 s 中的每一個字元。

內層迴圈: for (p2 = t; *p2; p2++)

• p2 初始化為指向字串 t 的第一個字元。
• 迴圈繼續的條件是 *p2 (即 p2 所指向的字元) 不是字串結束符 \0。
• p2++ 讓 p2 指向字串 t 中的下一個字元。
  此迴圈遍歷字串 t 中的每一個字元。

判斷條件: if (*p1 == *p2) break;

• 在內層迴圈中，如果當前 s 中的字元 (*p1) 與 t 中的某個字元 (*p2) 相符，則立即跳出內層迴圈 (break;)。

外層迴圈的判斷: if (*p2 == '\0') break;

• 在內層迴圈結束後，檢查 p2 的值。
• 如果內層迴圈是因為 break; 而結束（表示找到了匹配的字元），那麼 p2 指向的是匹配的字元，它不是 \0。
• 如果內層迴圈是自然結束（遍歷完 t 中的所有字元都沒找到匹配），那麼 p2 會指向 t 的結束符 \0。
• 如果 *p2 == '\0'，表示對於當前的 *p1，在整個字串 t 中都沒有找到匹配的字元。此時，外層迴圈也應該跳出 (break;)，因為我們已經找到了 s 中第一個不在 t 中的字元（或者說，是第一個在 t 中找不到匹配的字元）。

回傳值: return p1 - s;

• 函數回傳 p1 和 s 的差值。由於 p1 和 s 都是指標，它們的差值代表了 p1 相對於 s 的偏移量，也就是 p1 指向的字元在字串 s 中的索引。
• 如果迴圈是因為 *p1 == *p2 匹配成功而中斷，p1 指向的就是第一個匹配的字元。
• 如果迴圈是因為 *p2 == '\0' 而中斷，p1 指向的就是第一個在 t 中找不到匹配的字元。

現在我們來模擬 f("abcd", "babc") 的執行過程：

這題考驗對 C 語言結構 (struct) 和聯合 (union) 的記憶體配置規則的理解，以及編譯器如何處理成員的對齊 (alignment) 和填充 (padding)。題目特別說明「假設編譯器在成員之間不留空隙」(assume that the compiler leaves no holes between members)，這簡化了問題，讓我們專注於結構和聯合的大小計算。

首先，我們需要了解 struct 和 union 的記憶體分配規則：

• struct: 總大小是其所有成員大小的總和，並且可能因為對齊 (alignment) 而在成員之間插入填充 (padding)。每個成員的大小是其宣告的類型大小。
• union: 總大小是其最大成員的大小。所有成員共享同一塊記憶體空間。

題目給定的資訊：

• char 佔 1 位元組 (byte)。
• int 佔 4 位元組。
• double 佔 8 位元組。

現在我們來計算結構 s 的大小：

結構 s 包含三個成員：

1. double a;

   • double 的大小是 8 位元組。

2. union { char b[4]; double c; int d; } e;

   • 這是個聯合 (union) 成員，名為 e。
   • 我們需要計算這個聯合的大小。聯合的大小是其最大成員的大小。
   • 聯合 e 的成員有：
     • char b[4];: 4 個 char，每個 1 位元組，總共 4 * 1 = 4 位元組。
     • double c;: double 的大小是 8 位元組。
     • int d;: int 的大小是 4 位元組。
   • 比較這三個成員的大小：4, 8, 4。其中最大的是 8 位元組 (來自 double c)。
   • 因此，聯合 e 的大小是 8 位元組。

3. char f[4];

   • 4 個 char，每個 1 位元組，總共 4 * 1 = 4 位元組。

現在我們將結構 s 的成員大小加總，同時考慮到「不留空隙」的假設：

• 成員 a (double): 8 位元組
• 成員 e (union): 8 位元組 (其最大成員 double c 的大小)
• 成員 f (char[4]): 4 位元組

總大小 = sizeof(a) + sizeof(e) + sizeof(f)
總大小 = 8 位元組 + 8 位元組 + 4 位元組 = 20 位元組。

這題考驗對 C 語言邏輯運算子 (&& 邏輯 AND, || 邏輯 OR) 的求值順序和短路 (short-circuiting) 特性的理解。

C 語言中的邏輯運算子 && 和 || 是從左到右進行求值的，並且具有短路特性：

• 對於 A && B：如果 A 的求值結果為假 (false)，則 B 不會被求值，整個表達式結果為假。
• 對於 A || B：如果 A 的求值結果為真 (true)，則 B 不會被求值，整個表達式結果為真。

在 C 語言中，數值 0 被視為假 (false)，任何非零值被視為真 (true)。

給定的表達式是 i && j || k。
變數的值為：i = 5, j = 0, k = -5。

讓我們逐步求值：

1. 求值 i && j:
   • i 的值是 5，在 C 語言中被視為真 (true)。
   • j 的值是 0，在 C 語言中被視為假 (false)。
   • 由於是 && (AND) 運算，需要兩個操作數都為真才為真。
   • true && false 的結果是 false。

核心觀念

進位制以基底 $b$ 表示數值：每一位數字乘上其位權後相加。從右至左，位權依序為 $b^0,b^1,b^2,\ldots$。常用基底包括二進位 $2$、八進位 $8$、十進位 $10$ 與十六進位 $16$；十六進位中的 $A$ 至 $F$ 分別代表十進位的 $10$ 至 $15$。

二進位與八進位可直接互換：每 $3$ 個二進位位元對應 $1$ 個八進位數字，因為 $8=2^3$。二進位與十六進位也可直接互換：每 $4$ 個二進位位元對應 $1$ 個十六進位數字，因為 $16=2^4$。

解題方法

a. 八進位 $123$ 轉十進位

依照八進位各位數的位權展開：

$$(123)_8 =1\times 8^2+2\times 8^1+3\times 8^0 =64+16+3 =83$$

因此，$(123)_8=(83)_{10}$。

b. 二進位 $111010101001$ 轉八進位

從右側開始，每 $3$ 位分成一組：

$$111\quad 010\quad 101\quad 001$$

各組分別換成八進位數字：

$$111_2=7,\quad 010_2=2,\quad 101_2=5,\quad 001_2=1$$

依序寫回，得到：

$$(111010101001)_2=(7251)_8$$

這題考驗對正規表示式 (Regular Expression) 的撰寫能力。語言的字母表是 {0, 1}。

a. 包含字串 "010" 的所有字串
一個字串要包含 "010"，表示 "010" 這三個字元必須連續出現在字串的某個位置。
在 "010" 之前，可以有任意數量的 0 或 1。
在 "010" 之後，也可以有任意數量的 0 或 1。

• 「任意數量的 0 或 1」可以用 (0|1)* 或 [01]* 來表示。
• 「包含字串 010」表示 010 必須出現。

所以，我們可以將它表示為：
(0|1)*010(0|1)*

這表示：

• (0|1)*: 任意數量的 0 或 1 (包括 0 個)。
• 010: 字串 "010" 必須出現。
• (0|1)*: 任意數量的 0 或 1 (包括 0 個)。

這題要求解釋四個計算機科學的術語。

a. Binary translation (二進位翻譯)
二進位翻譯是指將一種二進位代碼（例如，為特定處理器架構編寫的機器碼）轉換為另一種二進位代碼的過程。這通常發生在以下情況：

1. 模擬或仿真: 在一種架構的處理器上運行為另一種架構編寫的程式。翻譯器將原始架構的指令翻譯成目標架構的指令。例如，在 x86 處理器上運行 ARM 程式。
2. 二進位轉譯器 (Binary Translator): 這種軟體工具讀取應用程式的機器碼，並將其轉換為另一組機器碼，而無需重新編譯原始程式碼。
3. 向上或向下相容性: 有時用於使舊的軟體能在新的硬體上運行，或反之。
   與直譯 (interpretation) 不同，二進位翻譯通常會生成新的可執行二進位檔，或者在執行時動態地進行翻譯（如動態二進位翻譯，Dynamic Binary Translation, DBT），以便在目標架構上高效執行。

b. Pseudo instruction in assembly language (組合語言中的偽指令)
偽指令 (Pseudo-instruction) 是組合語言中的一種指令，它本身並不是處理器真正執行的機器指令，而是由組合器 (assembler) 處理的指令。它們提供了一種方便的方式來執行某些常見的任務，或者讓程式更容易編寫和閱讀。
偽指令的功能通常包括：

1. 定義資料: 例如 .data, .byte, .word, .string 等，用於在記憶體中分配空間並初始化數據。
2. 控制組合過程: 例如 .equ (定義符號), .macro (定義巨集), .if/.else/.endif (條件組合)。
3. 生成機器指令: 有些偽指令會被組合器展開成一條或多條實際的機器指令。例如，某些處理器可能沒有直接支援的「複製」指令，但可以用偽指令 MOV AX, BX (如果 AX 和 BX 是暫存器)，組合器會將其翻譯成底層的機器指令。
4. 提供抽象: 允許程式設計師使用更高級的語法，而不用擔心底層的硬體細節。

c. Memory leak (記憶體洩漏)
記憶體洩漏 (Memory leak) 是指程式在運行過程中，動態分配了記憶體，但在不再需要使用該記憶體時，未能將其釋放回作業系統或記憶體管理器。

核心觀念

本題考查：

1. C 語言「函式型巨集」與「物件型巨集」的語法差異。
2. 巨集展開與函式呼叫的執行方式。
3. 運算子優先序：+ 高於 >>，因此

$$*ptr1 = *ptr1 + *ptr2 >> 2;$$

等價於

$$*ptr1 = (*ptr1 + *ptr2) >> 2$$

4. 巨集與函式在執行時間、型別檢查、參數求值等方面的差異。

---

a. 兩個程式是否有相同輸出？

先判斷 Program A 的巨集語法

題目中的宣告是：

#define func (var1, var2) \
  var1 = var1 + var2 >> 2; \
  var2 = (var1 + var2) % 10;

在 C 語言中，函式型巨集的巨集名稱與左括號之間不能有空白：

#define func(var1, var2)

題目寫成：

#define func (var1, var2)

因此 func 會被視為「物件型巨集」，而不是函式型巨集。

呼叫：

func(a, b);

會展開成類似：

(var1, var2)
var1 = var1 + var2 >> 2;
var2 = (var1 + var2) % 10;
(a, b);

這不是合法的 C 語法，因此 Program A 無法通過編譯，也就沒有輸出。

按照題目原文的嚴格答案

Program A 無法編譯，Program B 可以編譯，因此兩者沒有相同輸出。

若題目原意是函式型巨集

若將宣告修正為：

#define func(var1, var2) \
  var1 = var1 + var2 >> 2; \
  var2 = (var1 + var2) % 10;

則巨集展開後，兩個程式的運算順序相同。

Program B 的函式內容為：

*ptr1 = (*ptr1 + *ptr2) >> 2;
*ptr2 = (*ptr1 + *ptr2) % 10;

其中第二行使用的是第一行更新後的 *ptr1。

計算如下：

迴圈	原本的 $(a,b)$	更新後的 $a$	更新後的 $b$	輸出
第 1 次	$(2,4)$	$(2+4)>>2=1$	$(1+4)\%10=5$	1 5
第 2 次	$(1,5)$	$(1+5)>>2=1$	$(1+5)\%10=6$	1 6
第 3 次	$(1,6)$	$(1+6)>>2=1$	$(1+6)\%10=7$	1 7
第 4 次	$(1,7)$	$(1+7)>>2=2$	$(2+7)\%10=9$	2 9

因此，若修正巨集宣告，兩者輸出皆為：

1 5
1 6
1 7
2 9

---

b. 哪個程式一般執行時間較短？

在「沒有編譯器最佳化」的前提下，若 Program A 修正為合法的函式型巨集，通常是 Program A 執行時間較短。

原因

函式型巨集是在前處理階段直接展開。例如：

func(a, b);

會被替換成：

a = a + b >> 2;
b = (a + b) % 10;

因此不需要：

• 建立函式呼叫環境；
• 傳遞參數；
• 保存返回位址；
• 跳躍至函式；
• 從函式返回。

Program B 則需要真正呼叫：

func(&a, &b);

除了函式呼叫與返回成本外，還需要透過指標存取資料：

*ptr1
*ptr2

所以一般而言：

$$T_{\text{macro}} < T_{\text{function}}$$

補充

巨集展開會增加程式碼大小。若巨集在大量位置被使用，可能造成指令快取使用效率下降，因此實際效能不一定永遠較佳。但在本題「無編譯器最佳化」且只比較函式呼叫額外成本的情況下，應答 Program A 較快。

兩個版本每次呼叫都只執行固定數量的運算，因此時間複雜度與空間複雜度皆為：

$$\text{時間複雜度}=O(1)$$ $$\text{額外空間複雜度}=O(1)$$

---

c. 使用 C 巨集實作函式的優缺點

優點

1. 減少函式呼叫成本

巨集在編譯前直接展開，不需執行函式呼叫與返回，因此適合非常短小、且被大量呼叫的程式片段。

2. 可處理多種資料型別

核心觀念

本題考 pointer 的指向關係、陣列傳入函式時的退化，以及 sizeof 的計算方式。

• int *p1 表示 p1 是指向 int 的指標；int p2 則是一般整數，不是指標。
• int **r1 表示 r1 是指向 int * 的指標。因此 r1 = &p1 後，r1 指向的是指標變數 p1。
• 陣列名稱用在函式呼叫的引數位置時，會轉成指向首元素的指標。因此 func(v2) 中，函式參數 ptr 指向 v2[0]。
• *r1 = v2 會改寫 r1 所指的指標變數，也就是把 p1 改成指向 v2[0]。
• sizeof(v2) 計算整個陣列的大小；sizeof(ptr) 計算指標本身的大小。

解題方法

先以變數或陣列元素為節點，追蹤每次指定後的指向關係：

p1 = &v1;
p3 = &v3;
r1 = &p1;
func(v2);

執行完第 13 行後，p1 指向 v1、p3 指向 v3、r1 指向 p1。呼叫 func(v2) 時，陣列 v2 退化成首元素位址，所以 ptr 指向 v2[0]。

a. 第 14 行

此時各指標的指向如下：

指標	指向
p1	v1
p3	v3
r1	指標變數 p1
ptr	陣列元素 v2[0]

b. 第 18 行

第 18 行位於 cond % 2 == 0 的分支中。執行第 17 行：

*r1 = v2;

因為 r1 指向 p1，這行等同於：

p1 = v2;

而 v2 會退化為 &v2[0]。接著第 18 行只會改寫 p3 所指的整數值，不會改變 p3 的指向。因此：

指標	指向
p1	v2[0]
p3	v3
r1	指標變數 p1

c. 第 22 行