108 年 國立中央大學企業管理學系碩士班戊組《計算機概論》

此題考驗對 C 語言函式傳遞參數（傳值呼叫）的理解。

在 C 語言中，函式參數的傳遞預設是「傳值呼叫」(pass by value)。這表示當函式被呼叫時，函式內部的參數是主調函式中對應變數的「副本」。對副本的任何修改，都不會影響到主調函式中的原始變數。

程式碼解析：

1. void main() 是程式的進入點。
2. int i = 2; 在 main 函式中宣告一個整數變數 i 並初始化為 2。
3. func (i); 呼叫 func 函式，並將 main 中的 i (值為 2) 作為參數傳入。

此題考察 C 語言二維陣列的指標運算與存取方式。

二維陣列在記憶體中是連續儲存的，可以視為一維陣列的陣列，或是一行行連續儲存的一維陣列。

對於 int num[3][3]：

• num 本身是一個指向第一個元素（即第一列）的指標，其類型是 int (*)[3]。
• num+1 表示指向第二列的起始位置。
• *(num+1) 則是取得第二列第一個元素的位址，其類型是 int*，值為 4。
• *(num+1)+2 表示從第二列的起始位置開始，往後偏移 2 個 int 的位址。這會指向第二列的第三個元素。
• *(*(num+1)+2) 則是指解引用該位址，取得該位置的值。

陣列 num 的內容如下：

此題考驗 C 語言 printf 函式中浮點數格式控制的理解。

printf 函式中的格式控制符號用於指定輸出的樣式。對於浮點數（float 或 double），常用的格式符號是 %f。

格式控制的一般形式為：%[flags][width][.precision]type

• type: 指定資料型態，例如 f 表示浮點數。
• width: 指定輸出的最小欄位寬度。如果實際輸出寬度小於此值，則會用空格補齊。
• .precision: 指定小數點後的位數。

此題考驗對 C 語言 do-while 迴路結構以及 break 語句的理解。

do-while 迴路至少會執行一次，因為迴圈條件的判斷是在迴圈體執行之後進行。

程式碼逐步執行分析：

1. 初始化：int n=0;
2. 第一次迴圈體執行：
   • if (n>5) break;：此時 n 是 0，0 > 5 為假，不執行 break。
   • n+=2;：n 變為 $0 + 2 = 2$。
   • while(1);：條件為真 (1 代表真)，繼續迴圈。
   • 迴圈執行 1 次。
3. 第二次迴圈體執行：
   • if (n>5) break;：此時 n 是 2，2 > 5 為假，不執行 break。
   • n+=2;：n 變為 $2 + 2 = 4$。

此題考驗 C 語言 for 迴圈、陣列存取以及累加操作的理解。

程式碼解析：

1. 初始化：

   • int arr[10] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};：宣告一個包含 10 個整數的陣列，並給予初始值。
   • int i, sum=20;：宣告整數變數 i 作為迴圈計數器，並宣告整數變數 sum 並初始化為 20。

2. for 迴圈：for(i = 0; i < 10; i+=2)

   • 迴圈初始化：i = 0。
   • 迴圈條件：i < 10。
   • 迴圈迭代：i += 2 (每次 i 增加 2)。

3. 迴圈體內的運算：sum = sum + arr[i];

   • 在每次迴圈迭代中，將陣列 arr 中索引為 i 的元素值加到 sum 上。

迴圈執行過程：

• 第一次迭代:
  • i 為 0。
  • 條件 0 < 10 為真。
  • sum = sum + arr[0] => sum = 20 + 5 = 25。
  • i 變為 $0 + 2 = 2$。
• 第二次迭代:
  • i 為 2。

此題考驗虛擬記憶體分頁置換演算法的應用，包括 FIFO、Optimal、LRU 以及 LFU (Counting replacement)。題目設定為有 4 個記憶體框架 (frames)，初始載入頁面為 1, 3, 2。頁面參考字串為 7, 2, 3, 1, 2, 5, 3, 4, 1, 2, 3。

初始狀態：
記憶體框架 (Frames) 狀態：[1, 3, 2, _] (假設第四個框架是空的，或者可以根據演算法決定是否空著)
頁面錯誤 (Page Faults) 初始計數：0

重要說明： 題目提到 "All frames initially contain three pages number 1, 3, 2 (in order)"。這表示前三個框架已載入 1, 3, 2。由於只有 4 個框架，這意味著第四個框架是空的，或者我們需要將這三個頁面放入框架中，然後再處理第一個參考頁面。通常，我們會將初始頁面載入，然後計算頁面錯誤。

假設初始框架為 [1, 3, 2, 空]。
頁面參考字串：7, 2, 3, 1, 2, 5, 3, 4, 1, 2, 3

(a) FIFO (First-In, First-Out) Replacement
FIFO 演算法將淘汰最舊載入的頁面。

參考頁面	框架 1	框架 2	框架 3	框架 4	頁面錯誤	說明
初始	1	3	2	_	0
7	7	3	2	_	1	7 頁不在，載入 7，淘汰 1 (最舊)
2	7	2	2	_	2	2 頁不在，載入 2，淘汰 3
3	7	2	3	_	3	3 頁不在，載入 3，淘汰 2 (原先的 2)
1	1	2	3	_	4	1 頁不在，載入 1，淘汰 7
2	1	2	3	_	4	2 在
5	1	2	3	5	5	5 頁不在，載入 5，淘汰 1
3	1	2	3	5	5	3 在
4	4	2	3	5	6	4 頁不在，載入 4，淘汰 2
1	1	2	3	5	7	1 頁不在，載入 1，淘汰 3
2	1	2	3	5	7	2 在
3	1	2	3	5	7	3 在

FIFO 頁面錯誤總數：7

(b) Optimal Replacement
Optimal 演算法將淘汰在未來最長時間內都不會被使用的頁面。

參考頁面	框架 1	框架 2	框架 3	框架 4	頁面錯誤	說明
初始	1	3	2	_	0
7	7	3	2	_	1	7 頁不在，載入 7，淘汰 1 (未來最遠)
2	7	2	2	_	2	2 頁不在，載入 2，淘汰 3 (未來最遠)
3	7	2	3	_	3	3 頁不在，載入 3，淘汰 2 (未來最遠)
1	1	2	3	_	4	1 頁不在，載入 1，淘汰 7 (未來最遠)
2	1	2	3	_	4	2 在
5	1	2	5	_	5	5 頁不在，載入 5，淘汰 3 (未來最遠)
3	1	2	3	5	6	3 頁不在，載入 3，淘汰 2 (未來最遠)
4	1	4	3	5	7	4 頁不在，載入 4，淘汰 1 (未來最遠)
1	1	4	3	5	7	1 在
2	1	2	3	5	8	2 頁不在，載入 2，淘汰 4 (未來最遠)
3	1	2	3	5	8	3 在

Optimal 頁面錯誤總數：8

(c) LRU (Least Recently Used) Replacement
LRU 演算法將淘汰最近最少使用的頁面。

參考頁面	框架 1	框架 2	框架 3	框架 4	頁面錯誤	LRU 順序 (最近 -> 最舊)
初始	1	3	2	_	0	(1, 3, 2)
7	7	3	2	_	1	(7, 3, 2) - 淘汰 1
2	7	2	2	_	2	(2, 7, 2) - 淘汰 3
3	7	2	3	_	3	(3, 7, 2) - 淘汰 2 (原先的 2)
1	1	2	3	_	4	(1, 2, 3) - 淘汰 7
2	1	2	3	_	4	(2, 1, 3)
5	1	2	3	5	5	(5, 1, 3) - 淘汰 2 (LRU)
3	1	2	3	5	5	(3, 5, 1)
4	4	2	3	5	6	(4, 5, 1) - 淘汰 1 (LRU)

此題考驗對虛擬位址 (Logical Address) 和實體位址 (Physical Address) 的結構與位元數計算的理解，涉及分頁系統的位址轉換。

給定資訊：

• 位址空間是位元組導向 (byte-oriented)。
• 邏輯空間有 8 個頁面 (pages)。
• 每個頁面大小為 1024 位元組 (bytes)。
• 實體記憶體有 32 個框架 (frames)。

(a) 邏輯位址的位元數
邏輯位址由兩部分組成：頁面號 (Page Number) 和頁內位移 (Page Offset)。

• 頁面號 (Page Number)： 邏輯空間總共有 8 個頁面。要唯一識別 8 個頁面，需要 $\log_2 8$ 位元。
  頁面號位元數 = $\log_2 8 = 3$ 位元。
• 頁內位移 (Page Offset)： 每個頁面有 1024 個位元組。要唯一識別一個頁面內的位址，需要 $\log_2 1024$ 位元。
  頁內位移位元數 = $\log_2 1024 = \log_2 (2^{10}) = 10$ 位元。

此題考驗對二維陣列在記憶體中的儲存方式（列主序或行主序）以及分頁系統中 LRU 置換演算法在不同存取模式下的頁面錯誤 (page faults) 計算。

基本設定：

• 陣列大小：$A[100][100]$。假設每個元素是 1 個位元組 (byte) 的話，總共有 $100 \times 100 = 10000$ 個元素。
• 頁面大小 (Page Size)：200 位元組 (bytes)。
• 記憶體框架數量 (Number of Frames)：2 個。
• 置換演算法：LRU (Least Recently Used)。

重要假設：
C 語言的二維陣列預設是「列主序」(row-major order) 儲存。這意味著，在記憶體中，同一列的元素是連續存放的。例如，A[i][j] 和 A[i][j+1] 在記憶體中是相鄰的，而 A[i][j] 和 A[i+1][j] 則不一定相鄰（它們之間隔著一整列的元素）。

計算元素的位址：
假設每個元素佔用 1 個位元組。
則 A[i][j] 的位址可以表示為：BaseAddress + (i * 100 + j) * sizeof(element)。
在這裡 sizeof(element) 假設為 1。
所以，A[i][j] 的位址是 BaseAddress + i*100 + j。

頁面結構：
頁面大小是 200 位元組。

• 陣列的總大小是 10000 位元組。
• 所需的頁面數量 = $\lceil \frac{10000 \text{ bytes}}{200 \text{ bytes/page}} \rceil = \lceil 50 \rceil = 50$ 個頁面。

由於我們只有 2 個記憶體框架，而陣列需要 50 個頁面，這表示大部分時間記憶體中只會有 2 個頁面。當存取到不在這 2 個頁面中的元素時，就會發生頁面錯誤，並觸發 LRU 置換。

---

(a) 迴圈順序：for(i...) { for(j...) } (列主序存取)
這個迴圈以列主序遍歷陣列。對於每一列 i，它會依序存取該列的所有元素 j=0 到 j=99。

我們需要追蹤哪些頁面被載入到記憶體中，以及它們的 LRU 順序。

元素位址與頁面的對應：
A[i][j] 的位址是 i*100 + j (從 0 開始)。

• 頁面 0 包含位址 0 到 199。
• 頁面 1 包含位址 200 到 399。
• ...
• 頁面 k 包含位址 $k \times 200$ 到 $(k+1) \times 200 - 1$。

分析存取模式：
當 i 保持不變，j 從 0 增加到 99 時，位址 i*100 + j 會連續增加。

• 如果 i 是偶數，例如 i=0：位址是 j。
  • j=0 to j=99：位址 0 到 99。這落在 頁面 0。
• 如果 i 是奇數，例如 i=1：位址是 100 + j。
  • j=0 to j=99：位址 100 到 199。這也落在 頁面 0。
• 當 j 遍歷完 0 到 99，i 增加到 2。
• 當 i=2：位址是 2*100 + j = 200 + j。
  • j=0 to j=99：位址 200 到 299。這落在 頁面 1 (位址 200-399)。

詳細模擬 (2 個框架)：

參考 (i, j)	位址 (i*100+j)	頁面	框架 1 (LRU: 最舊 -> 最新)	框架 2 (LRU: 最舊 -> 最新)	頁面錯誤
初始	-	-	-	-	0
(0, 0)	0	0	[0]	-	PF
(0, 1)	1	0	[0]	-	-
...	...	0	[0]	-	-
(0, 99)	99	0	[0]	-	-
(1, 0)	100	0	[0]	-	-
...	...	0	[0]	-	-
(1, 99)	199	0	[0]	-	-
(2, 0)	200	1	[0]	[1]	PF
(2, 1)	201	1	[0]	[1]	-
...	...	1	[0]	[1]	-
(2, 99)	299	1	[0]	[1]	-
(3, 0)	300	1	[0]	[1]	-
...	...	1	[0]	[1]	-
(3, 99)	399	1	[0]	[1]	-
(4, 0)	400	2	[1]	[2]	PF
(4, 1)	401	2	[1]	[2]	-
...	...	2	[1]	[2]	-
(4, 99)	499	2	[1]	[2]	-
(5, 0)	500	3	[2]	[3]	PF
...	...	...	...	...	...

觀察：
這個迴圈模式 (列主序) 使得在處理 A[i][j] 時，如果 i 相同，j 會連續增加，這意味著會連續存取同一個頁面內的元素。

• 當 i 從 0 到 1 時，存取的是頁面 0 (位址 0-199)。
• 當 i 從 2 到 3 時，存取的是頁面 1 (位址 200-399)。
  -當 i 從 4 到 5 時，存取的是頁面 2 (位址 400-599)。
• ...
  -當 i 從 98 到 99 時，存取的是頁面 49 (位址 9800-9999)。

總共有 50 個頁面 (0 到 49)。
由於只有 2 個框架，每次存取一個新的頁面時，都會發生頁面錯誤。

• 第一次存取頁面 0 (i=0, j=0)：PF. 框架: [0]
• 第一次存取頁面 1 (i=2, j=0)：PF. 框架: [0, 1]
• 第一次存取頁面 2 (i=4, j=0)：PF. 框架: [1, 2] (淘汰 0)

此題考驗對常見排序演算法的時間複雜度（最佳情況 $\Omega$ 和最差情況 $O$）的掌握。

時間複雜度通常用大 O 符號 (Big O Notation) 來表示最差情況，用大 Ω 符號 (Big Omega Notation) 來表示最佳情況。

(a) Bubble Sort (氣泡排序)

• 基本思想： 重複地遍歷列表，比較相鄰的元素，如果它們的順序錯誤就交換它們。每一趟遍歷會將當前未排序部分的最大（或最小）元素放到其最終位置。
• 最佳情況 ($\Omega$)： 當輸入列表已經排序時。
  • 氣泡排序仍然需要遍歷列表一次來確認沒有交換發生，但如果有優化（例如，如果一趟遍歷沒有發生交換，則提前終止），則只需要遍歷一次。
  • 最佳情況時間複雜度是 $O(n)$。
• 最差情況 ($O$)： 當輸入列表是逆序排序時。
  • 在這種情況下，每一對相鄰元素都需要交換，並且需要 $n-1$ 趟遍歷。
  • 最差情況時間複雜度是 $O(n^2)$。

(b) Quick Sort (快速排序)

• 基本思想： 分治法。選擇一個基準點 (pivot)，將列表分割成兩部分：小於基準點的元素和大于基準點的元素。然後遞歸地對這兩部分進行排序。
• 最佳情況 ($\Omega$)： 當每次分割都能將列表均勻地分成兩半時（即基準點總是選取到中間值）。
  • 遞歸深度為 $\log_2 n$。在每一層遞歸中，需要遍歷所有元素進行分割，總共是 $O(n)$ 的工作。
  • 最佳情況時間複雜度是 $\Omega(n \log n)$。
• 最差情況 ($O$)： 當每次分割都極度不均勻時（例如，每次都選擇到最小或最大的元素作為基準點，導致分割成一個空列表和一個包含 $n-1$ 個元素的列表）。
  • 遞歸深度變為 $n$。

此題考驗對不同二進位數表示法（包括負數表示法）的理解。題目要求表示 -1，且使用 4 個位元。

基本概念：

• 位元 (Bit)： 二進位數字，0 或 1。
• 4 位元表示： 總共 4 個位元，可以表示 $2^4 = 16$ 個不同的值。
• Signed-Magnitude (帶號符號)： 最高位 (MSB) 代表符號，0 為正，1 為負。其餘位元表示數值的絕對值。
• One's Complement (一補數)： 對於正數，表示法與 Signed-Magnitude 相同。對於負數，將其對應正數的二進位表示中的所有位元反轉（0 變 1，1 變 0）。
• Two's Complement (二補數)： 對於正數，表示法與 Signed-Magnitude 相同。對於負數，是其對應正數的 One's Complement 再加 1。這是現代電腦中最常用的表示負數的方法。
• Excess-3 (餘三碼)： 這是一種 BCD (Binary Coded Decimal) 的編碼方式，每個十進位數字都用其本身的二進位表示加上 3。它通常用於表示十進位數字，而非一般的二進位補數。

計算 -1 的表示：

1. Signed-Magnitude (帶號符號)

• 4 位元表示的範圍是 -7 到 +7 (0000 為 +0, 1000 為 -0)。
• 正 1 的 4 位元表示是 0001。
• 負 1 的符號位是 1，絕對值是 1。

核心觀念

1. 二進位位元與數值表示範圍：
   • 設二進位位元數（bit）為 $n$。
   • $n$ 個二進位位元最多可以表示 $2^n$ 種不同的狀態。若用以表示無號非負整數，可表示的範圍為 $0 \sim 2^n - 1$。
2. 十進位位數與狀態數：
   • 「最多六個數字（digits）的十進位整數」即代表整數值範圍在 1 位數到 6 位數之間。
   • 包含數值 $0$ 至 $999,999$，總共涵蓋 $10^6 = 1,000,000$ 種相異整數值。
3. 編碼容量不等式：
   • 若要無歧義地完整儲存這 $10^6$ 個不同整數，所需的二進位位元數 $n$ 必須滿足： $$2^n \ge 10^6$$
   • 亦即 $n = \lceil \log_2 (10^6) \rceil$。

---

解題方法

1. 定義表示範圍與狀態總數：
   最多六位的十進位整數範圍為 $0$ 到 $999,999$，共有 $1,000,000$（即 $10^6$）個整數。

2. 尋找滿足不等式 $2^n \ge 10^6$ 的最小整數 $n$：

   • 利用常見的 2 的次方幂進行逼近： $$2^{10} = 1024 \approx 10^3$$ $$2^{19} = 2^9 \times 2^{10} = 512 \times 1024 = 524,288 < 10^6$$ $$2^{20} = (2^{10})^2 = 1024 \times 1024 = 1,048,576 > 10^6$$
   • 若僅使用 19 個位元，最多僅能表示 524,288 個數字（範圍 $0 \sim 524,287$），無法涵蓋全部的六位數十進位整數。
   • 使用 20 個位元可表示 1,048,576 個數字（範圍 $0 \sim 1,048,575$），足以容納所有六位十進位整數。

核心觀念

本題考查 C 語言中的：

1. 陣列名稱與指標的關係
2. 指標位移與解參照
3. 陣列索引與指標表示法的等價性
4. 指標越界與未定義行為（Undefined Behavior）

若 p = array，則：

$$p = \&array[0]$$

因此：

$$p[i] \equiv array[i] \equiv *(p+i)$$

例如：

• p[0] 等同於 array[0]
• *(p+1) 等同於 array[1]
• *(p+2) 等同於 array[2]

---

解題方法

初始宣告：

int array[4] = {0};

陣列共有四個元素，初始值為：

$$array = [0,0,0,0]$$

逐行執行如下。

1. 設定陣列第一個元素

p = array;
array[0] = 1;

此時 p 指向 array[0]，陣列為：

$$[1,0,0,0]$$

2. 使用指標設定 array[0]

p[0] = 2;

因為 p[0] 等同於 array[0]：

p[0] = *(p+0) = array[0];

陣列變為：

$$[2,0,0,0]$$

3. 使用指標位移設定 array[1]

*(p+1) = 3;

此時 p 仍指向 array[0]，因此：

*(p+1) = array[1];

陣列變為：

$$[2,3,0,0]$$

4. 指標往後移動一格

p++;

此時：

$$p = \&array[1]$$

也就是 p 不再指向 array[0]，而是指向 array[1]。

5. 設定 array[3]

*(p+2) = 4;

因為目前 p = &array[1]，所以：

$$p+2 = \&array[3]$$

因此此行相當於：

array[3] = 4;

陣列變為：

$$[2,3,0,4]$$

6. 發生指標越界

*(p+3) = 5;

目前 p = &array[1]，因此：

$$p+3 = \&array[4]$$

但陣列 array[4] 的合法索引只有：

$$0,1,2,3$$

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的：

1. 逐一插入規則。
2. 刪除節點的處理方式。
3. 後序走訪（post-order traversal）。

BST 的基本性質是：

• 每個節點左子樹的鍵值都小於該節點。
• 每個節點右子樹的鍵值都大於該節點。
• 插入新字元時，從根節點開始逐層比較，較小者往左，較大者往右。
• 刪除具有兩個子樹的節點時，本題採用「中序後繼」法：以右子樹中最小的節點取代被刪除節點。

---

解題方法

依照題目給出的順序：

$$I,\ C,\ D,\ M,\ P,\ S,\ A,\ B,\ G,\ U,\ W,\ N,\ K,\ V$$

逐一插入空 BST。

插入路徑如下：

• $I$：成為根節點。
• $C<I$：放在 $I$ 的左側。
• $D<I$ 且 $D>C$：放在 $C$ 的右側。
• $M>I$：放在 $I$ 的右側。
• $P>M$、$S>P$：依序形成右鏈。
• $A<C$：放在 $C$ 的左側。
• $B<C$、$B>A$：放在 $A$ 的右側。
• $G>D$：放在 $D$ 的右側。
• $U>S$：放在 $S$ 的右側。
• $W>U$：放在 $U$ 的右側。
• $N>I$、$N<M$：放在 $M$ 的左側。
• $K>I$、$K<C$、$K>D$、$K>G$：放在 $G$ 的右側。
• $V>I$、$V>M$、$V>P$、$V>S$、$V>U$、$V<W$：放在 $W$ 的左側。

---

(a) 樹狀結構 $T$

$$\begin{array}{c} I\\ / \backslash\\ C M\\ / \backslash / \backslash\\ A D N P\\ \backslash \backslash \backslash\\ B G S\\ \backslash \backslash\\ K U\\ \backslash\\ W\\ /\\ V \end{array}$$

因此，$T$ 的結構可表示為：

核心觀念

本題考查：

• TLB（Translation Lookaside Buffer）命中率
• 有效記憶體存取時間（Effective Memory Access Time, EAT）
• 單層與兩層頁表的記憶體存取次數

已知：

• TLB 命中率：$h=90\%=0.9$
• TLB 查找時間：$t_T=10\text{ ns}$
• 一次記憶體存取時間：$t_M=100\text{ ns}$

TLB 命中時，可直接取得實體頁框位置；TLB 未命中時，必須查詢頁表，再存取真正的資料。

---

解題方法

有效記憶體存取時間採用加權平均：

$$\text{EAT} = (\text{命中率})\times(\text{命中時間}) + (\text{未命中率})\times(\text{未命中時間})$$

TLB 未命中率為：

$$1-h=1-0.9=0.1$$

TLB 查找時間 $10\text{ ns}$ 無論命中或未命中都必須付出，因此兩種情況都包含此時間。

---

(a) 單層頁表

TLB 命中

TLB 已經找到頁框編號，只需要再存取一次真正的資料：

$$T_{\text{hit}} = 10+100 = 110\text{ ns}$$

TLB 未命中

TLB 查找失敗後，需要：

1. 查詢一次頁表：$100\text{ ns}$
2. 存取真正的資料：$100\text{ ns}$

因此：

$$T_{\text{miss}} = 10+100+100 = 210\text{ ns}$$

有效記憶體存取時間

$$\begin{aligned} \text{EAT} &= 0.9(110)+0.1(210)\\ &= 99+21\\ &= 120\text{ ns} \end{aligned}$$

因此，單層頁表的有效記憶體存取時間為：

$$\boxed{120\text{ ns}}$$

---

(b) 兩層頁表