115 年 國立成功大學工程科學系碩士班乙組《計算機概論》

核心觀念

本題考查 8 位元二補數表示法與溢位判斷。

8-bit two's complement 的表示範圍為：

因此範圍是 $-128$ 至 $127$。

溢位判斷原則：

• 正數加正數得到負數：發生溢位。
• 負數加負數得到正數：發生溢位。
• 一正一負相加：不會發生溢位。

解題方法

先將十六進位數轉成 8 位元二進位：

進行二進位加法：

因此：

溢位判斷

$0\text{x}9\text{C}$ 的最高位為 $1$，代表負數；$0\text{x}36$ 的最高位為 $0$，代表正數。

核心觀念

十進位整數轉二進位，可用「連續除以 $2$，記錄餘數，再由下往上讀取」；十進位小數轉二進位，則用「連續乘以 $2$，依序記錄每次乘積的整數部分」。

解題方法

先處理整數部分 $13$：

由下往上讀取餘數，得到 $13_{10}=1101_2$。

再處理小數部分 $0.375$：

此題考驗 IEEE 754 單精度浮點數的轉換。

IEEE 754 單精度格式（32位元）結構如下：
1 位元符號 (Sign)
8 位元指數 (Exponent)
23 位元尾數 (Fraction)

給定的值：
符號 (S) = 0 (表示正數)
指數 (E) = $10000010_2$
尾數 (F) = $01000000000000000000000_2$

步驟 1：轉換指數
指數部分為 8 位元。IEEE 754 使用偏移表示法 (biased representation)，偏移量 (bias) 為 $2^{8-1} - 1 = 2^7 - 1 = 128$。
給定的指數二進位值 $10000010_2$ 轉換為十進位：
$10000010_2 = 1 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0$
$= 128 + 2 = 130_{10}$。

實際指數值 (Actual Exponent) = 偏移指數 (Biased Exponent) - 偏移量 (Bias)
實際指數值 = $130 - 128 = 2$。

此題考驗 CPU 時間的計算，核心公式為：
CPU Time = Instruction Count $\times$ CPI $\times$ Clock Cycle Time
或者
CPU Time = (Instruction Count $\times$ CPI) / Clock Rate

其中：
Instruction Count (IC) = $1.2 \times 10^9$ (指令數量)
Average CPI (Cycles Per Instruction) = 1.5 (平均每條指令所需的時脈週期數)
Clock Rate = 3.0 GHz = $3.0 \times 10^9$ Hz (時脈頻率)

步驟 1：計算時脈週期時間 (Clock Cycle Time)
時脈週期時間是時脈頻率的倒數。
Clock Cycle Time = $1 / \text{Clock Rate}$
Clock Cycle Time = $1 / (3.0 \times 10^9 \text{ Hz})$
Clock Cycle Time = $(1/3.0) \times 10^{-9}$ 秒
Clock Cycle Time $\approx 0.333 \times 10^{-9}$ 秒

此題考驗 Amdahl's Law 的應用。Amdahl's Law 用於評估系統中某一部分的效能提升對整體系統效能的影響。

Amdahl's Law 的公式為：
$\text{Speedup} = \frac{1}{(1 - \text{Fraction}_{\text{enhanced}}) + \frac{\text{Fraction}_{\text{enhanced}}}{\text{Speedup}_{\text{enhanced}}}}$

其中：
$\text{Fraction}_{\text{enhanced}}$ = 可被加速的執行時間比例
$\text{Speedup}_{\text{enhanced}}$ = 可被加速部分的加速因子

根據題目：
$\text{Fraction}_{\text{enhanced}} = 40\% = 0.4$
$\text{Speedup}_{\text{enhanced}} = 3$

此題考驗快取記憶體 (cache) 的位址分割，特別是直接對應 (direct-mapped) 快取。

給定資訊：
Cache Size = 16 KB
Block Size = 64 B
Addressing = 32-bit byte addressing

步驟 1：計算位址所需的總位元數
由於是 32-bit 位址，總共有 32 位元。

步驟 2：計算位址分割的組成部分
一個完整的記憶體位址通常由三部分組成：Tag, Index, Offset。
位址 = Tag | Index | Offset

步驟 3：計算 Offset 位元數
Offset 位元數取決於 Block Size。Block Size 是指每次從主記憶體讀取到快取中的資料區塊大小。
Offset 位元數 = $\log_2(\text{Block Size})$
Offset 位元數 = $\log_2(64 \text{ B})$
Offset 位元數 = $\log_2(2^6)$
Offset 位元數 = 6 位元。

步驟 4：計算 Index 位元數
Index 位元數取決於快取中有多少個 Cache Line (或 Cache Block)。
Number of Cache Lines = Cache Size / Block Size

此題考驗分頁記憶體管理中，單層分頁系統的頁表大小計算。

給定資訊：
Virtual Address Space = 32-bit
Page Size = 4 KB
Page Table Entry (PTE) Size = 4 bytes
Page Table Structure = Single-level

步驟 1：計算虛擬位址 (Virtual Address) 的組成部分
32-bit 的虛擬位址由兩部分組成：頁號 (Page Number, PN) 和頁內偏移 (Page Offset, PO)。
Virtual Address = PN | PO

步驟 2：計算頁內偏移 (Page Offset) 的位元數
頁內偏移的位元數由 Page Size 決定。
Page Size = 4 KB = $4 \times 1024$ Bytes = $2^2 \times 2^{10}$ Bytes = $2^{12}$ Bytes。
Page Offset Bits = $\log_2(\text{Page Size})$
Page Offset Bits = $\log_2(2^{12})$
Page Offset Bits = 12 位元。

步驟 3：計算頁號 (Page Number) 的位元數
總虛擬位址是 32 位元，其中 12 位元用於頁內偏移。

此題考驗網路傳輸延遲的計算，包含傳輸延遲 (Transmission Delay) 和傳播延遲 (Propagation Delay)。

給定資訊：
Bandwidth (B) = 10 Mbps = $10 \times 10^6$ bits/second
Distance (D) = 2000 km = $2000 \times 1000$ m = $2 \times 10^6$ m
Propagation Speed ($v_p$) = $2 \times 10^8$ m/s
Packet Size (L) = 1500 bytes

步驟 1：計算傳輸延遲 (Transmission Delay)
傳輸延遲是指將整個封包從網路介面發送到鏈路上所需的時間。
Transmission Delay = Packet Size / Bandwidth
首先將 Packet Size 轉換為位元 (bits)：
Packet Size = 1500 bytes $\times$ 8 bits/byte = 12000 bits。
Transmission Delay = 12000 bits / ($10 \times 10^6$ bits/second)
Transmission Delay = $12000 / 10,000,000$ seconds

此題考驗 RAID-5 中的 XOR 奇偶校驗計算。RAID-5 使用 XOR 操作來計算資料區塊的奇偶校驗，以實現資料冗餘。

給定資訊：
D0 = 0x3A
D1 = 0xC7
P = D0 XOR D1

步驟 1：將十六進位數轉換為二進位數
D0 = 0x3A = $0011\ 1010_2$
D1 = 0xC7 = $1100\ 0111_2$

此題考驗找出演算法時間複雜度的漸進緊界 (tightest asymptotic bound)，即 Big-Theta 符號 ($\Theta$)。

給定的演算法操作次數為：
$T(n) = 3n^2 + 10n \log_2 n + 500$

漸進緊界 $\Theta(f(n))$ 指的是當 $n$ 足夠大時，演算法的時間複雜度與 $f(n)$ 成比例，即存在正常數 $c_1, c_2, n_0$ 使得 $c_1 f(n) \le T(n) \le c_2 f(n)$ 對所有 $n \ge n_0$ 都成立。

在判斷漸進緊界時，我們關注時間複雜度中增長最快的那一項。
比較 $n^2$, $n \log_2 n$, 和常數 500：

1. $n^2$：這是二次方成長。
2. $n \log_2 n$：這是次二次方成長（比 $n^2$ 慢，但比 $n$ 快）。
3. $500$：這是常數成長。

當 $n$ 變得非常大時，$n^2$ 的增長速度遠遠快於 $n \log_2 n$ 和常數。
例如，當 $n=100$ 時：
$n^2 = 10000$
$n \log_2 n = 100 \times \log_2 100 \approx 100 \times 6.64 = 664$
$500$

可以看到 $n^2$ 佔據了主導地位。

形式上，我們可以證明 $n^2$ 是 $T(n)$ 的漸進緊界。
我們需要找到常數 $c_1, c_2, n_0$ 使得 $c_1 n^2 \le 3n^2 + 10n \log_2 n + 500 \le c_2 n^2$ 對所有 $n \ge n_0$ 成立。

下界證明 ($c_1 n^2 \le T(n)$)：
要找到一個 $c_1$ 和 $n_0$。
考慮 $T(n) = 3n^2 + 10n \log_2 n + 500$。
當 $n \ge 1$ 時，$n \log_2 n \ge 0$ 且 $500 > 0$。
所以，$T(n) \ge 3n^2$。
我們可以選擇 $c_1 = 3$ 和 $n_0 = 1$。
則 $3n^2 \le T(n)$ 對所有 $n \ge 1$ 成立。

核心觀念

本題考查四變數 Karnaugh Map（K-map）化簡，以及將最小 SOP（Sum of Products）表示式轉換成二輸入 NAND 閘電路。

K-map 的排列採 Gray code 順序：

• 欄：$AB=00,01,11,10$
• 列：$CD=00,01,11,10$

分組時，每組必須包含 $1,2,4,8,\ldots$ 個相鄰的 $1$，且 K-map 邊界可以互相相鄰。

解題方法

題目給定：

依照題目圖中的 K-map 順序填入：

可採用以下三組四格：

1. $m(0,2,8,10)$

   $A$、$C$ 改變，固定 $B=0,D=0$：

   $$\boxed{B'D'}$$

2. $m(5,7,13,15)$

   $A$、$C$ 改變，固定 $B=1,D=1$：

   $$\boxed{BD}$$

3. $m(2,3,10,11)$

   $A$、$B$、$D$ 中部分變化，固定 $B=0,C=1$：

此題考驗 Round Robin (RR) CPU 排程演算法的應用，包括 Gantt Chart 的繪製、平均等待時間 (Average Waiting Time) 和平均周轉時間 (Average Turnaround Time) 的計算。

給定資訊：
時間量子 (Time Quantum, Q) = 3 ms
進程 P1: Arrival Time = 0 ms, Burst Time = 7 ms
進程 P2: Arrival Time = 2 ms, Burst Time = 4 ms
進程 P3: Arrival Time = 4 ms, Burst Time = 5 ms
進程 P4: Arrival Time = 6 ms, Burst Time = 3 ms

核心概念：

• Round Robin: 每個進程輪流獲得 CPU 使用權，每個進程最多執行一個時間量子。如果進程在時間量子內完成，則釋放 CPU；否則，進程被中斷並放入就緒隊列的末尾。
• Gantt Chart: 顯示 CPU 如何分配給各個進程的時間順序圖。
• Turnaround Time (TAT): 進程從進入系統到完成所花費的總時間。TAT = Completion Time - Arrival Time。
• Waiting Time (WT): 進程在就緒隊列中等待 CPU 所花費的總時間。WT = Turnaround Time - Burst Time。

繪製 Gantt Chart：

我們使用一個就緒隊列 (Ready Queue) 來追蹤等待執行的進程。

• 時間 0: P1 到達，就緒隊列：[P1]。CPU 分配給 P1。
• 時間 0-3: P1 執行 3 ms。剩餘 P1 Burst Time = $7 - 3 = 4$ ms。P2 在時間 2 到達。
  • 在時間 2，P2 到達，加入就緒隊列。
  • 在時間 3，P1 執行完一個量子，被中斷，放入就緒隊列末尾。就緒隊列：[P2, P1]。CPU 分配給 P2。
• 時間 3-6: P2 執行 3 ms。剩餘 P2 Burst Time = $4 - 3 = 1$ ms。P3 在時間 4 到達。
  • 在時間 4，P3 到達，加入就緒隊列。
  • 在時間 6，P2 執行完一個量子，被中斷，放入就緒隊列末尾。就緒隊列：[P1, P3, P2]。CPU 分配給 P1。
• 時間 6-9: P1 執行 3 ms。剩餘 P1 Burst Time = $4 - 3 = 1$ ms。P4 在時間 6 到達。
  • 在時間 6，P4 到達，加入就緒隊列。
  • 在時間 9，P1 執行完一個量子，被中斷，放入就緒隊列末尾。就緒隊列：[P3, P2, P4, P1]。CPU 分配給 P3。
• 時間 9-12: P3 執行 3 ms。剩餘 P3 Burst Time = $5 - 3 = 2$ ms。
  • 在時間 12，P3 執行完一個量子，被中斷，放入就緒隊列末尾。就緒隊列：[P2, P4, P1, P3]。CPU 分配給 P2。
• 時間 12-13: P2 執行剩餘的 1 ms。
  • 在時間 13，P2 完成。就緒隊列：[P4, P1, P3]。CPU 分配給 P4。

此題考驗 Dijkstra 演算法在加權圖中尋找最短路徑。

給定圖形：
節點：A, B, C, D, E, F
邊及權重：
(A, B): 4
(A, C): 2
(B, D): 5
(C, D): 1
(C, E): 10
(D, E): 2
(D, F): 6
(E, F): 3

目標：找到從節點 A 到節點 F 的最短路徑，以及從 A 到所有其他節點的最短距離。

Dijkstra 演算法步驟：

1. 初始化：

   • 創建一個集合 S，包含已找到最短路徑的節點。初始 S 為空。
   • 創建一個集合 V，包含所有節點。
   • 對於每個節點 v，初始化其距離 dist(v) 和前驅節點 prev(v)。
     • dist(A) = 0
     • dist(B) = $\infty$
     • dist(C) = $\infty$
     • dist(D) = $\infty$
     • dist(E) = $\infty$
     • dist(F) = $\infty$
     • prev(v) = null 對所有 v。

2. 迭代：當 S 不包含所有節點時，重複以下步驟：
   a. 從 V-S 中選擇一個節點 u，使得 dist(u) 是 V-S 中所有節點的最小值。
   b. 將 u 加入 S。
   c. 對於 u 的每個鄰居 v：
   * 如果 dist(u) + weight(u, v) < dist(v)，則更新 dist(v) = dist(u) + weight(u, v)，並設置 prev(v) = u。

迭代過程：

初始化：
S = {}
dist = {A: 0, B: $\infty$, C: $\infty$, D: $\infty$, E: $\infty$, F: $\infty$}
prev = {A: null, B: null, C: null, D: null, E: null, F: null}

Iteration 1:
a. 從 V-S (A, B, C, D, E, F) 中選擇 dist 最小的節點：A (dist=0)。
b. 將 A 加入 S。S = {A}。
c. 放鬆 A 的鄰居：
* B: dist(A) + weight(A, B) = $0 + 4 = 4$。$4 < \infty$。更新 dist(B) = 4, prev(B) = A。
* C: dist(A) + weight(A, C) = $0 + 2 = 2$。$2 < \infty$。更新 dist(C) = 2, prev(C) = A。
dist = {A: 0, B: 4, C: 2, D: $\infty$, E: $\infty$, F: $\infty$}
prev = {A: null, B: A, C: A, D: null, E: null, F: null}

Iteration 2:
a. 從 V-S (B, C, D, E, F) 中選擇 dist 最小的節點：C (dist=2)。
b. 將 C 加入 S。S = {A, C}。
c. 放鬆 C 的鄰居：
* B: dist(C) + weight(C, B) = $2 + \infty$ (假設 C 和 B 沒有直接邊，若圖是無向的，則 C,B 邊權重為 4)。如果為無向圖，則 $2 + 4 = 6$。$6 > dist(B)=4$。不更新。
* D: dist(C) + weight(C, D) = $2 + 1 = 3$。$3 < \infty$。更新 dist(D) = 3, prev(D) = C。
* E: dist(C) + weight(C, E) = $2 + 10 = 12$。$12 < \infty$。更新 dist(E) = 12, prev(E) = C。
dist = {A: 0, B: 4, C: 2, D: 3, E: 12, F: $\infty$}
prev = {A: null, B: A, C: A, D: C, E: C, F: null}

Iteration 3:
a. 從 V-S (B, D, E, F) 中選擇 dist 最小的節點：D (dist=3)。
b. 將 D 加入 S。S = {A, C, D}。
c. 放鬆 D 的鄰居：
* B: dist(D) + weight(D, B) = $3 + \infty$ (假設 D 和 B 沒有直接邊，若圖是無向的，則 D,B 邊權重為 5)。如果為無向圖，則 $3 + 5 = 8$。$8 > dist(B)=4$。不更新。
* E: dist(D) + weight(D, E) = $3 + 2 = 5$。$5 < dist(E)=12$。更新 dist(E) = 5, prev(E) = D。
* F: dist(D) + weight(D, F) = $3 + 6 = 9$。$9 < \infty$。更新 dist(F) = 9, prev(F) = D。

此題考驗二元搜尋樹 (Binary Search Tree, BST) 的建構與各種遍歷 (traversal) 序列的生成。

建構 BST：
按照給定的順序插入鍵值：50, 30, 70, 20, 40, 60, 80, 65, 35。

1. 插入 50: 樹為空，50 成為根節點。

       50
   

2. 插入 30: 30 < 50，插入到左子樹。

       50
      /
     30
   

3. 插入 70: 70 > 50，插入到右子樹。

       50
      /  \
     30  70
   

4. 插入 20: 20 < 50，往左。20 < 30，往左。

       50
      /  \
     30  70
    /
   20
   

5. 插入 40: 40 < 50，往左。40 > 30，往右。

       50
      /  \
     30  70
    /  \
   20  40
   

6. 插入 60: 60 > 50，往右。60 < 70，往左。

       50
      /  \
     30  70
    /  \  /
   20  40 60
   

7. 插入 80: 80 > 50，往右。80 > 70，往右。

       50
      /  \
     30  70
    /  \  / \
   20  40 60 80
   

8. 插入 65: 65 > 50，往右。65 < 70，往左。65 > 60，往右。

       50
      /  \
     30  70
    /  \  / \
   20  40 60 80
        /
       65
   

9. 插入 35: 35 < 50，往左。35 > 30，往右。35 < 40，往左。

       50
      /  \
     30  70
    /  \  / \
   20  40 60 80
      /    /
     35   65
   

最終 BST 結構圖：

        50
       /  \
      30  70
     /  \  / \
    20  40 60 80
       /    /
      35   65

BST 遍歷序列：

• Inorder Traversal (中序遍歷): Left -> Root -> Right。對於 BST，Inorder 遍歷會得到排序好的序列。

  1. 遍歷 20 的左子樹 (無)
  2. 訪問 20
  3. 遍歷 20 的右子樹 (無)
  4. 遍歷 30 的左子樹 (20 的遍歷結果)
  5. 訪問 30
  6. 遍歷 30 的右子樹 (40 的遍歷結果)
  7. 遍歷 40 的左子樹 (35 的遍歷結果)
  8. 訪問 40
  9. 遍歷 40 的右子樹 (無)
  10. 遍歷 50 的左子樹 (30 的遍歷結果)
  11. 訪問 50
  12. 遍歷 50 的右子樹 (70 的遍歷結果)

  Inorder: 20, 30, 35, 40, 50, 60, 65, 70, 80。

• Preorder Traversal (前序遍歷): Root -> Left -> Right。

  1. 訪問 50
  2. 遍歷 50 的左子樹 (前序)
     • 訪問 30
     • 遍歷 30 的左子樹 (前序)
       • 訪問 20

此題考驗快取記憶體 (cache) 的位址分割、命中/未命中 (hit/miss) 分析，以及直接對應 (direct-mapped) 快取的標記 (tag) 和索引 (index) 的管理。

給定資訊：
Cache Size = 1 KB = $1024$ Bytes = $2^{10}$ Bytes
Block Size = 16 B = $2^4$ Bytes
Addressing = 16-bit byte addressing
Cache Mapping = Direct-mapped

Part (1): 位址分割

一個 16-bit 的位址由 Tag, Index, Offset 組成：
Address = Tag | Index | Offset

• Offset Bits: 由 Block Size 決定。
  Offset Bits = $\log_2(\text{Block Size})$
  Offset Bits = $\log_2(16 \text{ B})$
  Offset Bits = $\log_2(2^4)$
  Offset Bits = 4 bits。

• Index Bits: 在直接對應快取中，Index 的數量等於 Cache Line 的數量。
  Number of Cache Lines = Cache Size / Block Size
  Number of Cache Lines = 1 KB / 16 B = $1024$ B / 16 B = $64$。
  Index Bits = $\log_2(\text{Number of Cache Lines})$
  Index Bits = $\log_2(64)$
  Index Bits = $\log_2(2^6)$
  Index Bits = 6 bits。

• Tag Bits: 總位址位元數減去 Index 和 Offset 的位元數。
  Tag Bits = Total Address Bits - Index Bits - Offset Bits
  Tag Bits = 16 - 6 - 4
  Tag Bits = 6 bits。

Part (2): 命中/未命中分析

我們需要追蹤快取記憶體的狀態，包括每個 Index 對應的 Tag 和 Valid 位元（雖然題目沒有明確給 Valid 位元，但通常是隱含的，第一次載入時為 Valid）。在直接對應快取中，每個 Index 只指向一個 Cache Line。

快取狀態 (Cache State):
我們可以用一個陣列來表示快取，大小為 Number of Cache Lines (64)。每個元素包含 Tag 和 Data (在此題中 Data 不用關心，只關心 Tag)。
Cache[Index] = {Tag, Valid} (Valid 預設為 0，載入資料後設為 1)

初始狀態：所有 Cache Line 的 Tag 都是空的，Valid 位元為 0。
我們將追蹤每个 Index 的 Tag 值。

位址分析：
對於每個位址，我們需要提取 Tag, Index, Offset。
位址結構：TTTTTT IIIIII OOOO (T=Tag, I=Index, O=Offset)
Tag: 位址的最高 6 bits。
Index: 位址的中間 6 bits。
Offset: 位址的最低 4 bits。

存取序列 (Access Sequence)：

1. Access 1: 0x0000

   • Address (hex): 0000
   • Address (bin): 0000 0000 0000 0000
   • Tag: 000000 (0x00)
   • Index: 000000 (0x00)
   • Offset: 0000 (0x0)
   • Analysis: Index 000000 是空的 (Valid=0)。Miss。
   • Action: 從主記憶體載入 Block 0x0000-0x000F 到 Cache Line 0x00。更新 Cache[0x00] 的 Tag 為 0x00。

2. Access 2: 0x0004

   • Address (hex): 0004
   • Address (bin): 0000 0000 0100
   • Tag: 000000 (0x00)
   • Index: 000000 (0x00)
   • Offset: 0100 (0x4)
   • Analysis: Index 0x00 的 Tag 是 0x00。與存取位址的 Tag (0x00) 匹配。Hit。

3. Access 3: 0x0010

   • Address (hex): 0010
   • Address (bin): 0000 0000 0001 0000
   • Tag: 000000 (0x00)
   • Index: 000000 (0x00)
   • Offset: 0000 (0x0)
   • Analysis: Index 0x00 的 Tag 是 0x00。與存取位址的 Tag (0x00) 匹配。Hit。
   • 注意：0x0010 屬於 Block 0x0000-0x000F。

4. Access 4: 0x0100

   • Address (hex): 0100
   • Address (bin): 0000 0001 0000 0000
   • Tag: 000000 (0x00)
   • Index: 000001 (0x01)
   • Offset: 0000 (0x0)
   • Analysis: Index 0x01 是空的 (Valid=0)。Miss。
   • Action: 從主記憶體載入 Block 0x0100-0x010F 到 Cache Line 1 (Index 0x01)。更新 Cache[0x01] 的 Tag 為 0x00。

5. Access 5: 0x0008

   • Address (hex): 0008
   • Address (bin): 0000 0000 1000
   • Tag: 000000 (0x00)
   • Index: 000000 (0x00)
   • Offset: 1000 (0x8)
   • Analysis: Index 0x00 的 Tag 是 0x00。與存取位址的 Tag (0x00) 匹配。Hit。