112 年 國立成功大學生物醫學工程學系碩士班乙組《計算機概論》

本題考驗圖的遍歷（Graph Traversal）概念，特別是深度優先搜尋（Depth-First Search, DFS）。題目提供了兩個可能的樹狀結構，並要求畫出樹並展示 DFS 的過程。DFS 的核心思想是盡可能深入地探索圖的每一個分支，直到無法繼續為止，然後回溯到上一個節點，繼續探索其他未訪問的分支。

由於題目中提供了兩個圖，我們需要選擇其中一個來進行 DFS。通常，DFS 是從起始節點開始，選擇一個鄰居節點進入，重複此過程。如果遇到已經訪問過的節點，則不進入。當一個節點的所有鄰居都已被訪問過，或者沒有鄰居時，就回溯。

我們選擇第一個圖（左側圖）來展示 DFS 的過程。

DFS 過程展示：

1. 起始節點： 從 Start 開始，到達節點 A。
2. 探索 A 的鄰居： A 的鄰居有 B 和 C。DFS 會選擇其中一個，例如 B。
3. 探索 B 的鄰居： B 的鄰居有 A (已訪問)、D、E。選擇 D。
4. 探索 D 的鄰居： D 的鄰居有 B (已訪問)。沒有其他鄰居，回溯到 B。
5. 繼續探索 B 的鄰居： B 的另一個鄰居是 E。選擇 E。
6. 探索 E 的鄰居： E 的鄰居有 B (已訪問)、F。選擇 F。
7. 探索 F 的鄰居： F 的鄰居有 E (已訪問)、H、K。選擇 H。
8. 探索 H 的鄰居： H 的鄰居有 F (已訪問)、I。選擇 I。
9. 探索 I 的鄰居： I 的鄰居有 H (已訪問)。沒有其他鄰居，回溯到 F。
10. 繼續探索 F 的鄰居： F 的另一個鄰居是 K。選擇 K。
11. 探索 K 的鄰居： K 的鄰居有 F (已訪問)、L。選擇 L。
12. 探索 L 的鄰居： L 的鄰居有 K (已訪問)、Finish。到達 Finish。

核心觀念

本題考查圖靈機（Turing Machine）如何模擬二進位整數加 $1$。

二進位加法由最低位開始：

• $0+1=1$，不再產生進位。
• $1+1=0$，產生進位 $1$，繼續向左處理。
• 若所有位元皆為 $1$，最左側仍有進位，需新增一個 $1$。

例如：

$$(101)_2+1=(110)_2$$

圖靈機必須先找到輸入字串最右端，再由右向左執行二進位加一。

---

解題方法

假設：

• 輸入位元由左至右寫在連續磁帶格中。
• 讀寫頭一開始位於最左側輸入位元。
• 輸入字串左側與右側皆為空白符號 $\sqcup$。
• 採用「標準二進位表示法」，非零數字不以 $0$ 開頭。
• 圖靈機向右移動記為 $R$，向左移動記為 $L$。

設計三個狀態：

• $q_0$：向右掃描，尋找輸入字串最右端。
• $q_c$：向左處理進位。
• $q_h$：停機狀態。

---

狀態圖

轉移標記格式為：

$$\text{讀取符號}\ /\ \text{寫入符號},\ \text{移動方向}$$

                         0/0,R
                    ┌────────────┐
                    │            │
                    ▼            │
                 ┌─────┐       1/1,R
                 │ q₀  │─────────┘
                 └─────┘
                    │
                 ␣/␣,L
                    ▼
                 ┌─────┐
          1/0,L  │ q_c │  0/1,R
        ┌────────▶     ├────────▶ q_h
        │         └─────┘
        │            │
        │         ␣/1,R
        └────────────┘

其中 $\sqcup$ 表示空白符號。狀態 $q_c$ 遇到空白時，代表最左側仍有進位，必須寫入新的 $1$。

---

轉移函數

完整轉移規則如下：

目前狀態	讀取符號	寫入符號	移動	下一狀態	功能
$q_0$	$0$	$0$	$R$	$q_0$	向右掃描
$q_0$	$1$	$1$	$R$	$q_0$	向右掃描
$q_0$	$\sqcup$	$\sqcup$	$L$	$q_c$	到達最右端，開始處理進位
$q_c$	$1$	$0$	$L$	$q_c$	$1+1=0$，進位向左
$q_c$	$0$	$1$	$R$	$q_h$	$0+1=1$，進位結束
$q_c$	$\sqcup$	$1$	$R$	$q_h$	最左側新增進位 $1$

以轉移函數表示：

$$\delta(q_0,0)=(q_0,0,R)$$ $$\delta(q_0,1)=(q_0,1,R)$$

核心觀念

本題考查 Additive Cipher（加法密碼） 的加密與解密。

令英文字母依序編號如下：

$$A=0,\ B=1,\ C=2,\ \ldots,\ Z=25$$

加法密碼的加密公式為：

$$C=(P+k)\bmod 26$$

其中：

• $P$：明文英文字母的數值
• $C$：密文英文字母的數值
• $k$：密鑰，本題為 $20$

解密公式為：

$$P=(C-k)\bmod 26$$

題目要求忽略單字之間的空格，因此只處理 NCKUBME。

解題方法

一、加密

明文為：

$$\text{NCKUBME}$$

各字母依 $A=0$ 至 $Z=25$ 編碼：

明文字母	數值	加上密鑰 $20$	取模 $26$	密文字母
N	13	$13+20=33$	$33\bmod26=7$	H
C	2	$2+20=22$	$22\bmod26=22$	W
K	10	$10+20=30$	$30\bmod26=4$	E
U	20	$20+20=40$	$40\bmod26=14$	O
B	1	$1+20=21$	$21\bmod26=21$	V
M	12	$12+20=32$	$32\bmod26=6$	G
E	4	$4+20=24$	$24\bmod26=24$	Y

因此，加密後的密文為：

$$\boxed{\text{HWEOVGY}}$$

若按照原本單字分隔呈現，則可寫成：

$$\boxed{\text{HWEO VGY}}$$

二、解密

將密文 HWEOVGY 的每個字母套用解密公式：

$$P=(C-20)\bmod26$$

本題考驗哈夫曼編碼（Huffman Coding）的應用。哈夫曼編碼是一種數據壓縮演算法，用於生成變長編碼，使得出現頻率高的字元具有較短的編碼，而出現頻率低的字元具有較長的編碼。其目標是最小化總編碼長度。

哈夫曼編碼步驟：

1. 建立優先佇列（Priority Queue）： 將所有字元及其頻率放入一個最小優先佇列中，佇列根據頻率排序。
2. 建樹： 重複以下步驟，直到佇列中只剩一個節點（根節點）：
   • 從佇列中取出兩個頻率最低的節點。
   • 建立一個新的內部節點，其頻率是這兩個節點頻率之和。
   • 將這兩個節點分別作為新節點的左子節和右子節（通常頻率較低的作為左子節，較高的作為右子節，或者約定俗成）。
   • 將新節點插入回優先佇列。
3. 分配編碼： 從根節點開始，向左遍歷時賦予 '0'，向右遍歷時賦予 '1'。直到葉節點（代表原始字元）的路徑即為該字元的哈夫曼碼。

步驟 1：字元及其頻率
A: 12
B: 8
C: 10
D: 20
E: 31
F: 14
G: 8

步驟 2：建立優先佇列並建樹
我們將頻率低的先處理。

• 初始節點 (葉節點):
  (B, 8), (G, 8), (C, 10), (A, 12), (F, 14), (D, 20), (E, 31)

• 組合 (B, 8) 和 (G, 8):
  新節點 N1 = (B+G, 16)
  佇列: (C, 10), (A, 12), (F, 14), N1(16), (D, 20), (E, 31)

• 組合 (C, 10) 和 (A, 12):
  新節點 N2 = (C+A, 22)
  佇列: (F, 14), N1(16), (D, 20), N2(22), (E, 31)

• 組合 (F, 14) 和 N1(16):
  新節點 N3 = (F+N1, 30)
  佇列: (D, 20), N2(22), N3(30), (E, 31)

• 組合 (D, 20) 和 N2(22):
  新節點 N4 = (D+N2, 42)
  佇列: N3(30), (E, 31), N4(42)

• 組合 N3(30) 和 (E, 31):
  新節點 N5 = (N3+E, 61)
  佇列: N4(42), N5(61)

• 組合 N4(42) 和 N5(61):
  根節點 N6 = (N4+N5, 103)
  佇列: N6(103) (結束)

建樹結構 (示意，頻率低的放左邊，高的放右邊):

本題考驗雜湊（Hashing）的概念，特別是除法取餘法（Division Modulo Method）作為雜湊函數，以及開放定址法（Open Addressing）作為衝突解決策略。

基本概念：

• 雜湊函數 (Hash Function): 將鍵（Key）映射到雜湊表（Hash Table）中的索引（Index）或位置。
• 除法取餘法 (Division Modulo Method): 雜湊函數為 $h(k) = k \pmod{m}$，其中 $k$ 是鍵，$m$ 是雜湊表的大小。
• 開放定址法 (Open Addressing): 當發生衝突（即兩個不同的鍵映射到同一個索引）時，尋找表中其他可用的位置來存放鍵。常見的開放定址法有線性探測（Linear Probing）、二次探測（Quadratic Probing）和雙重雜湊（Double Hashing）。題目中提到 "open addressing"，我們一般預設為線性探測，除非另有說明。
• 線性探測 (Linear Probing): 如果索引 $h(k)$ 已被佔用，則嘗試 $h(k)+1, h(k)+2, \ldots$ (模 $m$)，直到找到空位。探測序列為 $h_i(k) = (h(k) + i) \pmod{m}$，其中 $i = 0, 1, 2, \ldots$。

題目資訊：

• 雜湊表大小 $m = 411$。
• 雜湊函數：$h(k) = k \pmod{411}$。
• 衝突解決：開放定址法（預設為線性探測）。
• 需要處理的鍵：a. 10278, b. 08222, c. 20553, d. 17256。

步驟：
對於每個鍵，我們計算其初始雜湊值，如果該位置已被佔用，則使用線性探測尋找下一個可用位置。

a. 鍵 = 10278

• 初始雜湊值：$h(10278) = 10278 \pmod{411}$
  $10278 = 25 \times 411 + 3$
  所以，$h(10278) = 3$。
• 位置 3 是空的。將 10278 存放在索引 3。
  紀錄： Index 3: 10278

b. 鍵 = 08222 (即 8222)

• 初始雜湊值：$h(8222) = 8222 \pmod{411}$
  $8222 = 20 \times 411 + 2$
  所以，$h(8222) = 2$。
• 位置 2 是空的。將 8222 存放在索引 2。
  紀錄： Index 2: 8222

c. 鍵 = 20553

• 初始雜湊值：$h(20553) = 20553 \pmod{411}$
  $20553 = 50 \times 411 + 3$
  所以，$h(20553) = 3$。
• 位置 3 已被鍵 10278 佔用。發生衝突。

核心觀念

二元樹的走訪順序如下：

• Inorder（中序）：左子樹 → 根 → 右子樹
• Postorder（後序）：左子樹 → 右子樹 → 根

後序走訪的最後一個節點必定是整棵樹的根。找到根之後，再利用該根在中序序列中的位置，將節點分成左、右子樹，遞迴處理即可。

---

解題方法

1. 找出整棵樹的根

題目給定：

• Postorder：FECHGDBA
• Inorder：FECABHDG

後序序列最後一個節點為 A，因此：

$$\text{根節點}=A$$

在中序序列中，A 將節點分為：

• 左子樹：FEC
• 右子樹：BHDG

因此，左子樹共有 3 個節點，右子樹共有 4 個節點。

---

2. 建立左子樹

左子樹的中序序列為：

FEC

其後序序列取前 3 個節點：

FEC

後序序列最後一個節點為 C，所以左子樹的根為 C。

在中序序列 FEC 中，C 左側為 FE，右側沒有節點：

• C 的左子樹：FE
• C 的右子樹：空

處理 FE：

• 中序：FE
• 後序：FE

後序最後一個節點為 E，因此 E 是根；中序中 E 左側為 F。

所以：

• E 的左子節點為 F
• E 沒有右子節點

左子樹結構為：

    C
   /
  E
 /
F

---

3. 建立右子樹

右子樹的中序序列為：

BHDG

後序序列取剩餘的 4 個節點：

HGDB

後序最後一個節點為 B，所以右子樹的根為 B。

本題考驗對斐波那契數列（Fibonacci Sequence）遞迴定義的理解與計算。斐波那契數列的定義如下：

• $Fib(0) = 0$
• $Fib(1) = 1$
• $Fib(n) = Fib(n-1) + Fib(n-2)$，當 $n > 1$ 時。

我們需要計算 $Fib(5)$、$Fib(8)$ 和 $Fib(10)$。

a. 計算 $Fib(5)$：
根據定義，我們逐步計算：

• $Fib(0) = 0$
• $Fib(1) = 1$
• $Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1$
• $Fib(3) = Fib(2) + Fib(1) = 1 + 1 = 2$
• $Fib(4) = Fib(3) + Fib(2) = 2 + 1 = 3$
• $Fib(5) = Fib(4) + Fib(3) = 3 + 2 = 5$

核心觀念

Insertion sort（插入排序）的概念是：維持陣列左側的一段「已排序區間」，每次取出下一個元素，將它插入已排序區間中的正確位置。

以遞增排序為例：

• 第一次處理時，視 $A[1]$ 為已排序。
• 取出 $A[i]$ 作為待插入元素 key。
• 從已排序區間的最右端向左比較。
• 將所有大於 key 的元素向右移動一格。
• 將 key 放入空出的位置。

核心迴圈不變量為：

每次外層迴圈開始時，$A[1 \dots i-1]$ 已經按照遞增順序排列。

解題方法

令陣列採用 1-based indexing：

1. 設 $i=2$，因為只有一個元素的 $A[1]$ 自然已排序。
2. 將 $A[i]$ 儲存到 key。
3. 設 $j=i-1$，從已排序區間的最右端開始比較。
4. 當 $j\geq 1$ 且 $A[j]>\text{key}$ 時：
   • 將 $A[j]$ 往右移至 $A[j+1]$。
   • 將 $j$ 向左移一格。
5. 迴圈結束後，$j+1$ 即為 key 的正確插入位置。
6. 將 key 放入 $A[j+1]$。
7. 增加 $i$，處理下一個元素。

演算法 pseudocode

InsertionSort(A, n)
    i ← 2

    while i ≤ n do
        key ← A[i]
        j ← i - 1

        while j ≥ 1 and A[j] > key do
            A[j + 1] ← A[j]
            j ← j - 1
        end while

        A[j + 1] ← key
        i ← i + 1
    end while

    return A

執行示例

考慮陣列：

$$A=[5,2,4,6,1,3]$$

第一次取出 key = 2：

• $5>2$，將 $5$ 右移。
• 將 $2$ 放入第一個位置。

結果為：

$$[2,5,4,6,1,3]$$

接著取出 key = 4：

• $5>4$，將 $5$ 右移。
• $2\leq4$，停止移動。
• 將 $4$ 放入 $2$ 與 $5$ 之間。

結果為：

$$[2,4,5,6,1,3]$$

每次完成插入後，左側前綴都保持排序，因此最後可得到完整的遞增陣列。

核心觀念

本題考查三項觀念：

1. 取樣定理與資料率
2. ECG 心率計算與警報條件判斷
3. 無線傳輸規格設計

ECG 的取樣率為 $100\ \text{Hz}$，表示每秒取得 $100$ 個樣本；解析度為 $8$ bits，表示每個樣本以 $8$ bits 儲存。

原始 ECG 資料率為

$$R_{\text{data}} =100\ \text{samples/s}\times 8\ \text{bits/sample} =800\ \text{bits/s}$$

因此，無線系統至少須能穩定傳輸 $800\ \text{bps}$ 的有效資料。考慮封包標頭、時間戳記、錯誤檢查與重傳等額外資訊，實際設計的傳輸速率必須高於 $800\ \text{bps}$。

---

解題方法

系統可分為 ECG 感測端、無線傳輸端與警報接收端三部分。

1. ECG 感測與數位化

ECG 裝置先將類比心電訊號經由放大器與濾波器處理，再以 ADC 進行數位化：

• 取樣率：$100\ \text{Hz}$
• 每一筆樣本解析度：$8$ bits
• 每秒資料量：$100$ bytes
• 原始資料率：$800\ \text{bps}$

$100\ \text{Hz}$ 的取樣率可表示最高約 $50\ \text{Hz}$ 的訊號頻率範圍，足以保留一般 ECG 波形中與心搏偵測相關的主要資訊。實際電路仍應搭配適當的抗混疊低通濾波器。

2. 心率計算

ECG 中的每一次心室收縮通常會產生明顯的 $R$ 波。系統可利用峰值偵測找出連續兩個 $R$ 波的時間間隔，即 $RR$ interval。

若兩個 $R$ 波間隔為 $\Delta t$ 秒，則心率為

$$HR=\frac{60}{\Delta t}\ \text{bpm}$$

若使用連續 $N$ 個心搏計算平均值，則可降低雜訊與單次誤判的影響：

$$HR=\frac{60(N-1)} {t_N-t_1}$$

其中 $t_1$ 與 $t_N$ 分別為第一個與最後一個偵測到的 $R$ 波時間。

以取樣點計算時，若相鄰 $R$ 波相差 $K$ 個樣本，由於取樣率為 $100\ \text{Hz}$，所以

$$\Delta t=\frac{K}{100}$$

因此

$$HR=\frac{60}{K/100} =\frac{6000}{K}\ \text{bpm}$$

警報條件為

$$HR<60\quad\text{或}\quad HR>100$$

當條件成立時，接收端啟動蜂鳴器、LED、震動器或手機通知。

3. 無線傳輸設計

可採用 Bluetooth Low Energy（BLE） 作為無線傳輸技術。BLE 適合穿戴式及醫療周邊裝置，具備低功耗、短距離、手機相容性高等特點。

建議規格如下：

項目	設計規格
無線技術	BLE
傳輸頻段	$2.4\ \text{GHz}$ ISM 頻段
有效資料	每秒 $100$ 筆 ECG 樣本，每筆 $8$ bits
最低有效資料率	$800\ \text{bps}$
建議連線速率	至少數十 kbps，保留封包額外負載與重傳餘裕
傳輸方向	ECG 裝置至警報主機
傳輸範圍	依環境需求設定，室內數公尺至數十公尺
功耗	使用低功耗模式，僅在取樣、封包傳輸時喚醒

每個封包可包含下列欄位：