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

此題考驗對 C 語言中函數傳遞參數（傳值 vs. 傳址）的理解。

在 C 語言中，函數傳遞參數預設是「傳值」(pass by value)。這表示當你呼叫 func(i) 時，func 函數接收到的是變數 i 的「值」的副本，而不是 i 本身。

1. void main() 開始執行。
2. 宣告整數變數 i 並初始化為 2。
3. 呼叫 func(i)：

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

二維陣列 num[3][3] 在記憶體中是連續儲存的。num 本身可以被視為指向第一個「列」的指標。

1. num：代表指向 int num[3] 這個一維陣列（第一列）的指標。
2. num + 1：由於指標的類型是 int (*)[3] (指向一個包含 3 個 int 的陣列)，加 1 會使指標前進一整個列的大小。所以 num + 1 會指向二維陣列的第二列（即 num[1]）。
3. *(num + 1)：解引用 (dereference) num + 1，得到的是第二列的「第一個元素」的位址。這相當於 &num[1][0]。

此題考驗對 C 語言 printf 函數格式化輸出（特別是浮點數）的理解。

格式字串的規則如下：%[flags][width][.precision][length]specifier

• %: 開始一個格式說明符。
• specifier: 指定要輸出的資料類型，如 d (整數), f (浮點數), s (字串) 等。
• width: 指定欄位最小寬度。
• .precision:
  • 對於浮點數 (f)：指定小數點後要顯示的位數。
  • 對於字串 (s)：指定要顯示的最大字元數。

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

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

1. 第一次迴圈 (n=0):

   • do 區塊開始。
   • if (n > 5)：0 > 5 為 false。
   • n += 2;：n 變為 0 + 2 = 2。
   • while(1)：條件為 1 (true)，迴圈繼續。

2. 第二次迴圈 (n=2):

   • do 區塊開始。
   • if (n > 5)：2 > 5 為 false。
   • n += 2;：n 變為 2 + 2 = 4。

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

程式碼的目的是計算一個累加和 sum。初始值為 20。迴圈會遍歷陣列 arr 的部分元素並將它們加到 sum 中。

1. 初始化:

   • arr 陣列被初始化為 {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}。
   • sum 被初始化為 20。
   • 迴圈變數 i 準備開始。

2. for 迴圈執行:

   • 迴圈條件是 i < 10，且每次迴圈結束後 i 增加 2 (i += 2)。
   • 第一次迭代:
     • i = 0。0 < 10 為 true。
     • sum = sum + arr[0]; => sum = 20 + 5 = 25。
     • i 變為 0 + 2 = 2。
   • 第二次迭代:
     • i = 2。2 < 10 為 true。
     • sum = sum + arr[2]; => sum = 25 + 15 = 40。
     • i 變為 2 + 2 = 4。

核心觀念

本題考查虛擬記憶體中的頁面置換（page replacement）。

• Page fault（頁面錯誤）：參考頁面不在目前的 frame 中時發生。
• 若尚有空 frame，直接載入，不需置換既有頁面。
• 若 frame 已滿，依演算法選擇被替換的頁面。
• 本題共有 $4$ 個 frame，但初始只有 $3$ 個頁面，因此第 4 個 frame 一開始為空。

頁面參考字串為：

$$7,\ 2,\ 3,\ 1,\ 2,\ 5,\ 3,\ 4,\ 1,\ 2,\ 3$$

初始 frame：

$$[1,\ 3,\ 2,\ \text{空}]$$

下表中的「✓」表示命中，「F」表示發生 page fault。

---

(a) FIFO 置換

FIFO（First-In, First-Out）替換最早載入記憶體的頁面。初始載入順序視為：

$$1 \rightarrow 3 \rightarrow 2$$

因此 $1$ 最早被替換。

參考頁	Frame 狀態	結果	被替換頁
初始	$[1,3,2,\_ ]$	—	—
7	$[1,3,2,7]$	F	空 frame
2	$[1,3,2,7]$	✓	—
3	$[1,3,2,7]$	✓	—
1	$[3,2,7,1]$	F	1
2	$[3,2,7,1]$	✓	—
5	$[2,7,1,5]$	F	3
3	$[7,1,5,3]$	F	2
4	$[1,5,3,4]$	F	7
1	$[1,5,3,4]$	✓	—
2	$[5,3,4,2]$	F	1
3	$[5,3,4,2]$	✓	—

發生 page fault 的頁面為：

$$7,\ 1,\ 5,\ 3,\ 4,\ 2$$

因此：

$$\boxed{\text{FIFO page faults}=6}$$

---

(b) Optimal 置換

Optimal replacement 會替換「未來最晚才會再被使用」或「之後不再使用」的頁面。

參考頁	Frame 狀態	結果	說明
初始	$[1,3,2,\_ ]$	—	—
7	$[1,3,2,7]$	F	使用空 frame
2	$[1,3,2,7]$	✓	—
3	$[1,3,2,7]$	✓	—
1	$[1,3,2,7]$	✓	—
2	$[1,3,2,7]$	✓	—
5	$[1,3,2,5]$	F	7 之後不再使用，替換 7
3	$[1,3,2,5]$	✓	—
4	$[1,3,2,4]$	F	5 之後不再使用，替換 5
1	$[1,3,2,4]$	✓	—
2	$[1,3,2,4]$	✓	—
3	$[1,3,2,4]$	✓	—

發生 page fault 的頁面為：

$$7,\ 5,\ 4$$

因此：

$$\boxed{\text{Optimal page faults}=3}$$

---

(c) LRU 置換

LRU（Least Recently Used）替換「最久沒有被使用」的頁面。

本題將初始順序 $1,3,2$ 視為由最久未使用到最近使用，即：

$$1 \rightarrow 3 \rightarrow 2$$

每次命中後，該頁面移到「最近使用」的位置。

參考頁	Frame 狀態	結果	被替換頁
初始	$[1,3,2,\_ ]$	—	—

核心觀念

本題考查需求分頁（demand paging）與四種頁面置換演算法：

• 發生頁面參照時，頁面已在記憶體中稱為 page hit。
• 頁面不在記憶體中，必須載入頁面，稱為 page fault。
• 初始有四個 frame，但只放入三頁，因此第四個 frame 為空，可直接載入第一個新頁面，不必置換既有頁面。

初始狀態如下：

Frame 1	Frame 2	Frame 3	Frame 4
1	3	2	空

參照字串為：

$$7,2,3,1,2,5,3,4,1,2,3$$

---

(a) FIFO replacement

FIFO（First-In, First-Out）置換最早載入記憶體的頁面。初始頁面順序為 $1\rightarrow3\rightarrow2$，之後載入的頁面依序排在佇列尾端。

參照頁	Frame 1	Frame 2	Frame 3	Frame 4	結果
7	1	3	2	7	Fault，填入空 frame
2	1	3	2	7	Hit
3	1	3	2	7	Hit
1	1	3	2	7	Hit
2	1	3	2	7	Hit
5	5	3	2	7	Fault，置換 1
3	5	3	2	7	Hit
4	5	4	2	7	Fault，置換 3
1	5	4	1	7	Fault，置換 2
2	5	4	1	2	Fault，置換 7
3	3	4	1	2	Fault，置換 5

頁面錯誤發生於：

$$7,5,4,1,2,3$$

因此：

$$\boxed{\text{FIFO page faults}=6}$$

---

(b) Optimal replacement

Optimal 演算法會置換「未來最晚才會再被使用」或「未來不會再使用」的頁面，因此需要預知未來的參照字串，實際系統無法直接實作，主要作為理論上的最佳基準。

參照頁	Frame 1	Frame 2	Frame 3	Frame 4	結果與置換理由
7	1	3	2	7	Fault，填入空 frame
2	1	3	2	7	Hit
3	1	3	2	7	Hit
1	1	3	2	7	Hit
2	1	3	2	7	Hit
5	1	3	2	5	Fault，置換未來不再使用的 7
3	1	3	2	5	Hit
4	1	3	2	4	Fault，置換未來不再使用的 5
1	1	3	2	4	Hit
2	1	3	2	4	Hit
3	1	3	2	4	Hit

頁面錯誤只有：

$$7,5,4$$

因此：

$$\boxed{\text{Optimal page faults}=3}$$

---

(c) LRU replacement

LRU（Least Recently Used）置換最近最久沒有被使用的頁面。每次 page hit 也要更新該頁面的最近使用順序。

以下以「左側為最久未使用、右側為最近使用」表示順序：

此題考驗對虛擬記憶體位址轉換的理解，包含邏輯位址和實體位址的位元數計算。

題目給定：

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

(a) 邏輯位址的位元數 (Number of bits in logical address)

邏輯位址由兩部分組成：頁號 (page number) 和頁內偏移量 (offset)。

1. 頁內偏移量 (Offset):

   • 每個頁面有 1024 bytes。
   • 要表示 1024 個位址，我們需要 $2^n = 1024$ 個位元。
   • $n = \log_2{1024} = 10$ bits。
   • 所以，頁內偏移量需要 10 bits。

2. 頁號 (Page Number):

   • 邏輯位址空間總共有 8 個頁面。
   • 要表示 8 個頁面，我們需要 $2^m = 8$ 個位元。
   • $m = \log_2{8} = 3$ bits。
   • 所以，頁號需要 3 bits。

核心觀念

本題考查：

1. C 語言二維陣列的儲存方式：採 row-major order（列優先），同一列的元素連續存放。
2. 分頁記憶體：每頁可容納 200 個陣列元素。
3. Page fault：存取的頁面不在兩個 page frames 中時產生。
4. LRU（Least Recently Used）置換法：記憶體不足時，置換最久未被使用的頁面。

以下採用一般考題假設：陣列 A[0][0] 從頁面開頭對齊，且每個元素大小相同並以「元素數量」計算頁面容量。

---

陣列的頁面配置

陣列共有：

$$100 \times 100 = 10{,}000$$

個元素。

每頁可存放 200 個元素，因此總頁數為：

$$\frac{10{,}000}{200}=50$$

由於 C 語言採 row-major order，每一列有 100 個元素，因此：

$$\text{每頁可存放兩列}$$

頁面配置如下：

頁面	儲存的列
Page 0	第 0、1 列
Page 1	第 2、3 列
Page 2	第 4、5 列
$\cdots$	$\cdots$
Page 49	第 98、99 列

---

(a) 先列後欄

for(int i = 0; i < 100; i++)
{
  for(int j = 0; j < 100; j++)
  {
    A[i][j] = 0;
  }
}

存取順序

程式會依序存取：

$$A[0][0], A[0][1], \ldots, A[0][99], A[1][0], \ldots, A[1][99], \ldots, A[99][99]$$

由於每一列連續存放，而且每頁包含兩列，因此頁面存取順序為：

$$0,0,\ldots,0,\quad 1,1,\ldots,1,\quad \ldots,\quad 49,49,\ldots,49$$

每個頁面會被連續使用 200 次。

Page fault 計算

開始時兩個 page frames 為空：

• 第一次存取 Page 0：產生 1 次 page fault。
• Page 0 之後的存取都命中。
• 接著第一次存取 Page 1：產生 1 次 page fault。
• 依此類推，每個頁面第一次被存取時各產生 1 次 page fault。

總共有 50 個頁面，因此：

$$\text{Page faults}=50$$

兩個 page frames 足以保留目前正在連續使用的頁面，因此 LRU 不會增加額外 fault。

(a) 結果

$$\boxed{50\text{ 次 page faults}}$$

---

(b) 先欄後列

此題考驗對常見排序演算法時間複雜度（最佳、最差情況）的理解。時間複雜度通常用大 O (O) 表示上限，大 Omega ($\Omega$) 表示下限。

對於排序演算法，其時間複雜度分析通常基於比較 (comparison) 和交換 (swapping) 操作的次數。

(a) Bubble Sort (冒泡排序)

• 基本思想：重複地走訪要排序的列表，一次比較兩個鄰近的元素，如果它們的順序錯誤就把它們交換過來。走訪列表的工作是重複地進行直到沒有再需要交換，也就是列表排序完成。
• 最佳情況 (Best Case)：輸入的陣列已經是排序好的。
  • 只需要走訪一次列表，進行 $n-1$ 次比較，沒有交換。
  • 時間複雜度：$O(n)$。 $\Omega(n)$。
• 最差情況 (Worst Case)：輸入的陣列是反向排序的。
  • 需要進行 $n-1$ 次走訪，每次走訪都進行 $n-1, n-2, ..., 1$ 次比較和交換。
  • 總比較和交換次數約為 $\frac{n(n-1)}{2}$。
  • 時間複雜度：$O(n^2)$。 $\Omega(n^2)$。

結論 (Bubble Sort):

• 最佳情況 (Best Case): $\Omega(n)$
• 最差情況 (Worst Case): $O(n^2)$

(b) Quick Sort (快速排序)

• 基本思想：採用分治法 (Divide and Conquer)。選擇一個基準點 (pivot)，將列表分割成兩部分：一部分所有元素小於基準點，另一部分所有元素大於基準點。然後遞迴地排序兩個子列表。
• 最佳情況 (Best Case)：每次分割都能將列表均勻地分成兩半（接近中間值作為 pivot）。
  • 遞迴深度為 $O(\log n)$。
  • 每層遞迴的總工作量為 $O(n)$。
  • 時間複雜度：$O(n \log n)$。 $\Omega(n \log n)$。
• 最差情況 (Worst Case)：每次選擇的 pivot 都是列表中的最小值或最大值（例如，列表已經排序或反向排序，且 pivot 總是選擇第一個或最後一個元素）。
  • 每次分割都只會減少一個元素，遞迴深度為 $O(n)$。
  • 每層遞迴的工作量仍然是 $O(n)$（分割操作）。
  • 時間複雜度：$O(n^2)$。 $\Omega(n^2)$。

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

我們將分別計算各種表示法：

基本概念：

• 4 位元表示法：能表示的數值範圍為 $-2^{4-1}$ 到 $2^{4-1}-1$ (對於 Two's Complement) 或 $-2^{4-1}+1$ 到 $2^{4-1}-1$ (對於 Signed-Magnitude 和 One's Complement)。
• 4 位元的範圍：
  • Signed-Magnitude: $-7$ 到 $+7$
  • One's Complement: $-7$ 到 $+7$
  • Two's Complement: $-8$ 到 $+7$
  • Excess-3: 這裡的 Excess-3 是指數字本身加上 3 後再轉換為二進位。對於 4 位元，通常是指表示範圍。由於 Excess-3 是 BCD (Binary Coded Decimal) 的一種變體，它不是用來表示負數的標準方法，而是用來表示數字。但題目要求表示 -1，這意味著我們需要理解如何用 Excess-3 表示負數，或者題目可能是在考驗對 Excess-3 的基本表示。
  • 常見的 Excess-3 表示法：通常用於 BCD 編碼，每個十進位數字用 4 位元二進位表示，這個二進位值是該數字加 3 的結果。例如，十進位 5 的 Excess-3 是 $5+3=8$，二進位是 1000。
  • 表示 -1 的 Excess-3：這部分比較特殊。一般來說，Excess-3 不直接表示負號。如果題目意指將 -1 轉換成十進位 -1，然後再進行 Excess-3 編碼，那麼這是不標準的。
  • 一種可能的解釋：題目可能是在考驗對 Excess-3 的基本概念，並混淆了負數表示法。如果我們假設題目是想問 "數字 1 的 Excess-3 表示法是什麼？" 那答案是 $1+3=4$ -> 0100。但題目明確要求 -1。
  • 另一種解釋：也許是將 -1 的某種二進位表示（如 Two's Complement）轉換成 Excess-3 格式。但這也不常見。
  • 標準做法：對於負數，Signed-Magnitude, One's Complement, Two's Complement 是標準的。Excess-3 通常不直接處理負數，或者有額外的符號位。
  • 假設：題目可能是在考驗對 -1 在不同二進位系統中的表示，而 Excess-3 的部分可能是個陷阱或有特定上下文。如果我們將 -1 的 Two's Complement 表示法（1111）看作是某種基礎，然後再進行轉換，那也不符合 Excess-3 的定義。
  • 最可能的理解：在 4 位元下，Excess-3 的設計是為了 BCD。如果我們要表示 "數字 1"，其 Excess-3 是 0100。如果題目硬要表示 -1，且是在 4 位元下，這就比較棘手。
  • 如果題目是考驗 "數字 1" 的 Excess-3，則是 0100。
  • 如果題目是考驗 "數字 -1" 的 Excess-3，這沒有標準解法。

此題考驗對數字系統轉換，特別是十進位數字到二進位數字的轉換，以及位元數的計算。

題目要求：儲存「最多六個數字」的十進位整數。

這裡的「最多六個數字」是指十進位數字的位數 (digits)，而不是數值的大小。例如，數字 123456 是六個數字，數字 999999 也是六個數字。

1. 最大值：

   • 最多六個數字的十進位整數的最大值是 999999。

2. 轉換為二進位：

   • 我們需要找到能表示 999999 的最小二進位位數。
   • 設所需的二進位位數為 $k$。
   • 則 $2^k \ge 999999$。

3. 計算 $k$：

   • 我們可以逐步試驗 2 的次方：
     • $2^{10} = 1024$
     • $2^{15} = 32768$
     • $2^{19} = 524288$
     • $2^{20} = 1048576$

核心觀念

本題考查：

• 陣列與指標的關係：p = array 等同於 p = &array[0]
• 指標位移：*(p+k) 等同於存取第 $k$ 個元素
• 指標遞增：p++ 會使指標移至下一個陣列元素
• 陣列索引範圍與未定義行為（Undefined Behavior）

題目中的 Int、Printf 應視為大小寫誤植，依標準 C 語言應寫成 int、printf。

解題方法

陣列宣告如下：

int array[4] = {0};

因此初始內容為：

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

且：

p = array;

表示：

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

依序追蹤程式：

程式碼	動作	陣列內容
array[0] = 1;	將第 0 格設為 1	[1,0,0,0]
p[0] = 2;	p[0] 等同於 array[0]	[2,0,0,0]
*(p+1) = 3;	設定 array[1]	[2,3,0,0]
p++;	p 移至 array[1]	[2,3,0,0]
*(p+2) = 4;	此時等同於 array[3] = 4	[2,3,0,4]
*(p+3) = 5;	此時等同於 array[4] = 5	超出陣列範圍

關鍵在於：

p++;

之後：

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

因此：

$$*(p+2)=array[3]$$

但下一行：

$$*(p+3)=array[4]$$

而 array 的合法索引只有：

核心觀念

本題考查二元搜尋樹（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) 兩層頁表