112 年 國立臺灣大學生物機電系碩士班丁組《計算機概論（A）》

核心觀念

本題考查：

• 布林代數的分配律、互補律與吸收律。
• SOP（Sum of Products，乘積和）：多個 AND 乘積項以 OR 相加。
• 真值表：列出所有輸入組合，判斷輸出 $Q$。
• SOP 電路的閘級實現：反相器、AND 閘與 OR 閘。

原式為：

$$Q=\bar{A}(\bar{B}\bar{C}+BC+\bar{B}C)+ABC$$

---

解題方法與推導

先利用分配律將 $\bar A$ 分配至括號內：

$$\begin{aligned} Q &=\bar{A}\bar{B}\bar{C}+\bar{A}BC+\bar{A}\bar{B}C+ABC \end{aligned}$$

此式已經是 SOP 形式，包含四個乘積項：

$$\bar{A}\bar{B}\bar{C},\quad \bar{A}BC,\quad \bar{A}\bar{B}C,\quad ABC$$

接著化簡：

$$\begin{aligned} \bar{B}\bar{C}+\bar{B}C &=\bar{B}(\bar{C}+C)\\ &=\bar{B} \end{aligned}$$

因此：

$$\begin{aligned} Q &=\bar{A}(\bar{B}+BC)+ABC \end{aligned}$$

利用布林代數公式：

$$X+YZ=(X+Y)(X+Z)$$

也可直接使用：

$$\bar{B}+BC=\bar{B}+C$$

所以：

$$Q=\bar{A}(\bar{B}+C)+ABC$$

再展開：

$$Q=\bar{A}\bar{B}+\bar{A}C+ABC$$

對 $\bar A C+ABC$ 化簡：

$$\begin{aligned} \bar{A}C+ABC &=C(\bar{A}+AB)\\ &=C(\bar{A}+B) \end{aligned}$$

因此得到最簡 SOP：

$$\boxed{Q=\bar{A}\bar{B}+\bar{A}C+BC}$$

---

真值表

三個輸入變數共有 $2^3=8$ 種組合。

以最簡 SOP：

$$Q=\bar{A}\bar{B}+\bar{A}C+BC$$

逐列判斷：

$A$	$B$	$C$	$\bar A\bar B$	$\bar AC$	$BC$	$Q$
0	0	0	1	0	0	1
0	0	1	1	1	0	1
0	1	0	0	0	0	0
0	1	1	0	1	1	1
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	0	0	0	0
1	1	1	0	0	1	1

因此，會使 $Q=1$ 的輸入組合為：

$$(A,B,C)=(0,0,0),(0,0,1),(0,1,1),(1,1,1)$$

也可寫成標準最小項表示：

$$Q=\Sigma m(0,1,3,7)$$

---

邏輯閘圖

採用最簡 SOP：

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

核心觀念：IEEE 754 單精度格式解析、指數偏差 (bias) 的處理、二進位轉十進位。

IEEE 754 單精度浮點數格式（32 位元）結構如下：
Sign (S): 1 位元 (最高位)
Exponent (E): 8 位元
Fraction (F): 23 位元

給定的二進位數是：11000001110000000000000000000000

1. 解析各部分：

   • Sign (S): 最高位是 1。這表示該數字是負數。
   • Exponent (E): 接下來的 8 位元是 10000011。
   • Fraction (F): 最後的 23 位元是 100000000000000000000000。

2. 轉換指數 (Exponent)：
   指數部分是 10000011。
   首先，將這個二進位數轉換為十進位：
   $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 + 1 \times 2^0$
   $= 128 + 0 + 0 + 0 + 0 + 0 + 2 + 1 = 131$。

   對於單精度浮點數，指數是帶有偏差 (bias) 的。偏差值是 $2^{8-1} - 1 = 2^7 - 1 = 128 - 1 = 127$。
   實際的指數值 $e$ 為：$E_{decimal} - Bias = 131 - 127 = 4$。

3. 轉換分數 (Fraction)：
   分數部分是 100000000000000000000000。
   在 IEEE 754 標準中，對於正規化數 (normalized numbers)，分數部分的前面隱含一個 1.。

此題考查氣泡排序法 (Bubble Sort) 的執行過程與計算比較次數和交換次數。

核心觀念：氣泡排序法的運作原理、比較次數、交換次數。

氣泡排序法的基本原理是：重複地遍歷列表，比較相鄰的元素，如果它們的順序錯誤就交換它們。這個過程會一直重複，直到列表排序完成。在每一輪遍歷中，最大的（或最小的，取決於排序方向）元素會被「冒泡」到列表的末尾。

給定的數字列表是：4 1 3 2 5，我們要進行遞增排序（從小到大）。

第一輪 (Iteration 1):
從列表的第一個元素開始，與下一個元素比較。

• 比較 4 和 1：4 > 1，交換。列表變為：1 4 3 2 5。 (比較 1 次, 交換 1 次)
• 比較 4 和 3：4 > 3，交換。列表變為：1 3 4 2 5。 (比較 2 次, 交換 2 次)
• 比較 4 和 2：4 > 2，交換。列表變為：1 3 2 4 5。 (比較 3 次, 交換 3 次)
• 比較 4 和 5：4 < 5，不交換。列表保持：1 3 2 4 5。 (比較 4 次, 交換 3 次)

第一輪結束後，最大的元素 5 (實際上是第二輪結束後才確定是 5，第一輪結束後確定的是 4) 已經被移動到正確的位置（最後一個元素）。
列表狀態：1 3 2 4 5。
總比較次數：4。總交換次數：3。

第二輪 (Iteration 2):
現在我們只需要考慮前 n-1 個元素（因為最後一個元素已經是最大的）。

• 比較 1 和 3：1 < 3，不交換。列表保持：1 3 2 4 5。 (比較 1 次, 交換 0 次)
• 比較 3 和 2：3 > 2，交換。列表變為：1 2 3 4 5。 (比較 2 次, 交換 1 次)
• 比較 3 和 4：3 < 4，不交換。列表保持：1 2 3 4 5。 (比較 3 次, 交換 1 次)
  (注意：在這一輪的比較中，我們最多比較到倒數第二個未排序的元素。列表長度為 5，所以這一輪最多需要比較 5-1 = 4 次，但實際上是與前一個元素比較，所以是 3 次比較。)

第二輪結束後，第二大的元素 4 已經被移動到正確的位置。
列表狀態：1 2 3 4 5。
本輪比較次數：3。本輪交換次數：1。
總比較次數：4 + 3 = 7。總交換次數：3 + 1 = 4。

此題考查如何根據樹的先序遍歷 (Pre-order Traversal) 和後序遍歷 (Post-order Traversal) 來重建二元樹 (Binary Tree)。

核心觀念：先序遍歷、後序遍歷、二元樹重建。

理解遍歷順序：

• 先序遍歷 (Pre-order Traversal): 訪問順序是「根 (Root) -> 左子樹 (Left Subtree) -> 右子樹 (Right Subtree)」。
• 後序遍歷 (Post-order Traversal): 訪問順序是「左子樹 (Left Subtree) -> 右子樹 (Right Subtree) -> 根 (Root)」。

重建步驟：

1. 找出根節點：
   根據後序遍歷的定義，最後一個節點一定是樹的根節點。
   後序遍歷：D, B, G, E, H, I, F, C, A
   所以，根節點是 A。

2. 分割左右子樹：
   在先序遍歷中，根節點之後的所有節點都屬於其子樹。
   先序遍歷：A, B, D, C, E, G, F, H, I
   在先序遍歷中，除了根 A 之外，緊跟著的是左子樹的節點，然後是右子樹的節點。
   我們知道 A 是根，所以 A 後面的節點 B, D, C, E, G, F, H, I 構成了 A 的左右子樹。
   現在我們需要根據後序遍歷來確定 B, D, C, E, G, F, H, I 中哪些屬於左子樹，哪些屬於右子樹。
   在後序遍歷 D, B, G, E, H, I, F, C, A 中，A 之前的部分 D, B, G, E, H, I, F, C 包含了左、右子樹的所有節點。
   我們找到 A 在後序遍歷中的位置。A 之後（在先序遍歷中）的節點，在 A 之前（在後序遍歷中）的節點中，A 左邊的節點屬於左子樹，A 右邊的節點（在後序遍歷中）屬於右子樹。
   更簡單的方法是：在後序遍歷 D, B, G, E, H, I, F, C, A 中，找到 A 的前一個節點 C。C 在後序遍歷中是 A 的直接前驅，這意味著 C 是 A 的右子樹的根節點（因為後序是左->右->根）。
   那麼，在先序遍歷 A, B, D, C, E, G, F, H, I 中，從 A 之後的第一個節點開始，直到 C 的前一個節點（也就是 A 的左子樹的所有節點）為止。
   在後序遍歷 D, B, G, E, H, I, F, C, A 中，C 之前的節點是 D, B, G, E, H, I, F。
   在先序遍歷 A, B, D, C, E, G, F, H, I 中，A 之後的節點是 B, D, C, E, G, F, H, I。
   C 在先序遍歷中的位置是第 4 個 (A, B, D, C, E, G, F, H, I)。
   因此，A 的左子樹節點是先序遍歷中 A 之後，到 C 之前的所有節點：B, D。
   A 的右子樹節點是先序遍歷中 C 以及 C 之後的所有節點：C, E, G, F, H, I。

   左子樹節點集 (先序)： {B, D}
   右子樹節點集 (先序)： {C, E, G, F, H, I}

   左子樹節點集 (後序)： {D, B}
   右子樹節點集 (後序)： {G, E, H, I, F, C}

3. 遞歸重建左子樹：

   • 左子樹的先序遍歷是：B, D
   • 左子樹的後序遍歷是：D, B
   • 左子樹的根節點是後序遍歷的最後一個：B。
   • 在先序遍歷 B, D 中，B 是根，B 後面的 D 屬於 B 的子樹。
   • 在後序遍歷 D, B 中，B 是根，B 之前的 D 屬於 B 的子樹。
   • B 的右子樹的節點是後序遍歷中 B 之前的節點：{D}。
   • B 的左子樹是空的。
   • 所以，B 的右子樹的先序是 {D}，後序是 {D}。
   • 遞歸重建 B 的右子樹：根是 D，左子樹和右子樹都是空的。
   • 因此，B 的左邊是空，右邊是 D。

4. 遞歸重建右子樹：

   • 右子樹的先序遍歷是：C, E, G, F, H, I
   • 右子樹的後序遍歷是：G, E, H, I, F, C
   • 右子樹的根節點是後序遍歷的最後一個：C。

核心觀念

RSA 使用兩個質數 $p$、$q$ 建立模數：

$$n=pq$$

其歐拉函數為：

$$\phi(n)=(p-1)(q-1)$$

公開金鑰中的 $e$ 必須與 $\phi(n)$ 互質；私密指數 $d$ 則是 $e$ 在模 $\phi(n)$ 下的乘法反元素，滿足：

$$ed\equiv 1\pmod{\phi(n)}$$

本題要求計算模數 $n$ 與私密指數 $d$。

解題方法

1. 計算 $n$

題目給定：

$$p=7,\qquad q=11$$

因此：

$$n=pq=7\times 11=77$$

2. 計算 $\phi(n)$

因為 $p$、$q$ 均為質數：

$$\phi(n)=(p-1)(q-1)$$

代入數值得：

$$\phi(n)=(7-1)(11-1)=6\times 10=60$$

3. 求 $d$

核心觀念

本題考查雜湊表（hash table）搭配線性探測（linear probing）處理碰撞的方法。

雜湊函數為：

$$H(x)=x\bmod 11$$

因此每個鍵值先利用除以 $11$ 的餘數決定其初始位置。若該位置已被占用，便依序檢查下一個位置：

$$H(x),\ H(x)+1,\ H(x)+2,\ldots$$

當探測到索引 $10$ 後，必須循環回索引 $0$，稱為循環線性探測。

本題容量為 $11$，索引範圍為 $0$ 至 $10$。

解題方法

初始雜湊表如下：

索引	0	1	2	3	4	5	6	7	8	9	10
內容	0	1	空	空	空	空	空	空	8	9	空

依題目指定順序插入各鍵值。

插入 $52$

$$52\bmod 11=8$$

索引 $8$ 已有 $8$，繼續探測索引 $9$；索引 $9$ 已有 $9$，再探測索引 $10$。

索引 $10$ 為空，因此將 $52$ 放入索引 $10$。

插入 $44$

$$44\bmod 11=0$$

索引 $0$ 已有 $0$，索引 $1$ 已有 $1$，索引 $2$ 為空。

因此將 $44$ 放入索引 $2$。

插入 $56$

$$56\bmod 11=1$$

索引 $1$ 已有 $1$，索引 $2$ 已有 $44$，索引 $3$ 為空。

因此將 $56$ 放入索引 $3$。

插入 $53$

$$53\bmod 11=9$$

探測順序為：

核心觀念

文法的 parse tree 必須符合兩項條件：

1. 根節點為開始符號 $S$。
2. 每個非終結符都必須依照某條產生式展開，最後所有葉節點串接後，恰好得到目標字串。

題目中的 $ 是輸入結束標記，通常不是文法產生的終結符，因此實際需要判斷文法是否能產生 $xx$。

解題方法

文法為：

$$S\to AS$$ $$A\to(AB)\mid\varepsilon$$ $$B\to(A)\mid x$$

觀察開始符號 $S$：

• $S$ 唯一的產生式是 $S\to AS$。
• 套用一次後，右側仍然包含一個 $S$。
• 文法中沒有 $S\to\varepsilon$，也沒有其他能消除 $S$ 的產生式。

因此推導必然形成：

$$S\Rightarrow AS\Rightarrow AAS\Rightarrow AAAS\Rightarrow\cdots$$

其對應的樹形會出現無限延伸的 $S

此題考查漢明碼 (Hamming Code) 的構造，特別是偶校驗 (Even Parity) 的漢明碼。

核心觀念：漢明碼的原理、校驗位 (Parity Bits) 的位置、校驗位的計算、數據位的放置。

漢明碼用於檢測和糾正單比特錯誤。它的構造方法是在數據位之間插入校驗位。
對於一個長度為 $k$ 的數據字節，我們需要 $r$ 個校驗位，使得 $2^r \ge k + r + 1$。
給定的數據是 1001101，長度 $k=7$。
我們需要找到最小的 $r$ 使得 $2^r \ge 7 + r + 1$。

• 如果 $r=1$: $2^1 = 2 < 7+1+1=9$ (不足)
• 如果 $r=2$: $2^2 = 4 < 7+2+1=10$ (不足)
• 如果 $r=3$: $2^3 = 8 < 7+3+1=11$ (不足)
• 如果 $r=4$: $2^4 = 16 \ge 7+4+1=12$ (足夠)
  所以，我們需要 4 個校驗位 ($p_1, p_2, p_3, p_4$)。

漢明碼的總長度為 $n = k + r = 7 + 4 = 11$ 位。
校驗位通常放置在 2 的冪次方位置上：$2^0, 2^1, 2^2, 2^3, \dots$ (即位置 1, 2, 4, 8)。
數據位放置在剩餘的位置上。
位元位置：1 2 3 4 5 6 7 8 9 10 11
編碼類型：$p_1$ $p_2$ D $p_3$ D D D $p_4$ D D D

其中 D 代表數據位。
數據位是 1001101。
我們將數據位按順序放入 D 的位置：
位置 3: 1
位置 5: 0
位置 6: 0
位置 7: 1
位置 9: 1
位置 10: 0
位置 11: 1

漢明碼的框架（帶有數據位）：
位置：1 2 3 4 5 6 7 8 9 10 11
位元：$p_1$ $p_2$ 1 $p_3$ 0 0 1 $p_4$ 1 0 1

接下來，計算每個校驗位的值，以實現偶校驗 (Even Parity)。
偶校驗意味著，該校驗位所覆蓋的所有位元（包括校驗位本身）中，1 的數量必須是偶數。

計算 $p_1$ (位置 1)：
$p_1$ 覆蓋所有位址，其位址的最低位是 1。
這些位址是：1, 3, 5, 7, 9, 11。
對應的位元是：$p_1$, 1, 0, 1, 1, 1。
我們需要 $p_1 + 1 + 0 + 1 + 1 + 1$ 的 1 的數量為偶數。
即，$p_1 + 1 + 0 + 1 + 1 + 1$ (二進位表示)。
總和是 $p_1 + 4$ (十進位)。
我們需要 $p_1 + (1+0+1+1)$ 的 1 的數量為偶數。
數據位中的 1 的數量是：1 (在 pos 3) + 1 (在 pos 7) + 1 (在 pos 9) + 1 (在 pos 11) = 4。
$p_1$ 覆蓋的數據位是：位置 3 (1), 位置 5 (0), 位置 7 (1), 位置 9 (1), 位置 11 (1)。
這些數據位中的 1 的數量是：1 + 0 + 1 + 1 + 1 = 4。
為了使總和（包括 $p_1$）為偶數，由於數據位的 1 的數量已經是偶數 (4)，所以 $p_1$ 必須是 0。
$p_1 = 0$。

計算 $p_2$ (位置 2)：
$p_2$ 覆蓋所有位址，其位址的第二低位是 1。
這些位址是：2, 3, 6, 7, 10, 11。
對應的位元是：$p_2$, 1, 0, 1, 0, 1。

此題考查組合語言程式的執行追蹤，涉及記憶體、輸入暫存器和輸出暫存器的操作。

核心觀念：組合語言指令、暫存器操作、記憶體存取、程式流程控制。

我們需要追蹤程式執行過程中，暫存器 OUT 和 M[4] 的變化。
程式碼從位置 12 開始執行。
初始值：
M[1] = 0001 (十進位 1)
M[2] = 0011 (十進位 3)
M[3] = 0011 (十進位 3)
M[4] = 0100 (十進位 4)
I[A] 和 I[B] 的初始值未給定，但指令 12 和 13 將 M[1] 和 M[2] 的值載入 I[A] 和 I[B]。
OUT 的初始值未給定。

指令追蹤：

• 12 MOV I [A] M[1]: 將 M[1] 的值 (0001) 複製到 I[A]。
  I[A] = 0001 (1)

• 13 MOV I [B] M[2]: 將 M[2] 的值 (0011) 複製到 I[B]。
  I[B] = 0011 (3)

• 14 ADD I [A] I[B]: 執行加法操作。OUT = I[A] + I[B]。
  OUT = 1 + 3 = 4。
  OUT = 0100 (4)

• 15 MOV I [A] OUT: 將 OUT 的值 (0100) 複製到 I[A]。
  I[A] = 0100 (4)

• 16 MOV I [B] M[3]: 將 I[B] 的值 (0011) 複製到 M[3]。
  M[3] = 0011 (3) (M[3] 的值沒有改變，因為它本來就是 0011)

• 17 ADD I [A] I[B]: 執行加法操作。OUT = I[A] + I[B]。
  I[A] 現在是 4。
  I[B] 仍然是 3 (從指令 13 載入後未改變)。
  OUT = 4 + 3 = 7。
  OUT = 0111 (7)

• 18 MOV M[4] OUT: 將 OUT 的值 (0111) 複製到 M[4]。
  M[4] = 0111 (7)

• 19 HALT: 程式終止。

回答問題：

核心觀念

本題旨在測驗基礎演算法設計、迴圈與流程控制、**數位拆解（Digit Extraction）以及環路檢測（Cycle Detection）**的能力。

1. 快樂數（Happy Number）定義：
   對於正整數 $n$，將其各個位數平方後加總得到新數，重複此過程：
   • 若最終結果收斂為 $1$，則該數為快樂數。
   • 若過程陷入不包含 $1$ 的循環，則該數為非快樂數（Unhappy number）。
2. 數位拆解運算：
   利用模數運算（n % 10）取得個位數，再配合整數除法（n / 10 或 n // 10）去除個位數，依序取出每一位數並累加平方。
3. 有界性與循環特性：
   • 對於 $n \le 1000$，其三位數各數位平方和的最大值為 $9^2 + 9^2 + 9^2 = 243$；四位數 $1000$ 的平方和為 $1$。因此，任何數字至多在一次運算後就會落入 $[1, 243]$ 的範圍內。
   • 由於狀態空間有限，數列必然會在有限步內抵達 $1$ 或進入循環。數論證明在十進位下，所有非快樂數最終都會落入同一個長度為 8 的固定循環：
     $4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4$

---

解題方法

程式設計採用模組化設計（Modular Design），拆解為兩個主要部分：

1. 子函式：計算數位平方和（sum_of_squares）
   輸入整數 $n$，初始化總和 sum = 0，當 $n > 0$ 時：

   • 取出個位數：$d = n \pmod{10}$
   • 累加平方：$\text{sum} = \text{sum} + d^2$
   • 移去個位數：$n = \lfloor n / 10 \rfloor$
   • 回傳 sum。

2. 子函式：判斷是否為快樂數（is_happy）
   檢測是否有環（Cycle）的常見方法有三種：

   • 雜湊集合法（Hash Set）：使用集合記錄走過的數字。若新數字為 $1$ 則回傳 true；若新數字已存在集合中則代表進入循環，回傳 false。
   • 快慢指標法（Floyd's Cycle-Finding Algorithm）：利用慢指標每次走一步、快指標每次走兩步，若快指標抵達 $1$ 則為快樂數；若快慢指標相遇且不為 $1$ 則代表有環。
   • 固定環特徵法：所有非快樂數必經數字 $4$，因此判斷條件可簡化為 $n \neq 1$ 且 $n \neq 4$。

3. 主程式：遍歷 $1$ 至 $1000$
   使用迴圈遍歷整數 $1 \le i \le 1000$，若 is_happy(i) 為真，則輸出或存入結果清單中。

---

程式實作

以下提供考試評分標準中最推薦的 Python 實作（使用 Hash Set） 與 C++ 實作（使用快慢指標）：

Python 實作