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

核心觀念

這題考圖靈機的逐步執行：每一步依照「目前狀態、讀取符號」查轉移表，接著寫入符號、移動讀頭，並切換到新狀態。只有遇到沒有對應轉移規則的狀態與符號組合，機器才會停住。

解題方法

依原圖，讀頭一開始指向連續三個 1 左側的空白格 b，初始狀態為 A。令這三個 1 依序位於 $x_1,x_2,x_3$，左側空白格為 $x_0$。

先執行一次轉移：

步驟	讀頭位置與狀態	讀取與寫入	移動後狀態
1	$x_0$，狀態 A	讀取 b，寫入 b	向右，進入 B

讀頭移到 $x_1$ 後，狀態 B 開始將 1 逐格改成 #，直到右側空白格：

步驟	讀頭位置與狀態	讀取與寫入	移動後狀態
2	$x_1$，狀態 B	1 改為 #	向右，B
3	$x_2$，狀態 B	1 改為 #	向右，B
4	$x_3$，狀態 B	1 改為 #	向右，B
5	$x_4$，狀態 B	讀取 b，寫入 b	向左，進入 C

此題考驗對 Polybius 密碼的理解與應用。Polybius 密碼是一種基於網格的替代密碼，將明文字母映射為網格的行號和列號組合。

Polybius 密碼原理：
Polybius 密碼使用一個 $N \times N$ 的網格（通常是 $5 \times 5$ 或 $6 \times 6$）來儲存字母表。加密時，找到明文字母在網格中的位置，其對應的密文即為該字母所在行的行號和列號。由於字母表通常比網格的格子數多，會有一些字母共享同一個格子（例如，I 和 J 在 $5 \times 5$ 網格中常合併），或者網格中包含數字、符號等。本題使用的是 $5 \times 5$ 的網格，並包含數字、空格等。

題目要求：
加密明文 "NCKU BME" 使用提供的 Polybius 密碼表。

步驟：
逐一找出明文中的每個字母（或空格）在給定的 $5 \times 5$ 網格中的位置，並記錄其行號和列號。

1. N: 在網格中找到 'N'。它位於第 3 行，第 1 列。
   • 加密 'N' $\rightarrow$ 31

核心觀念

本題考查兩種無損壓縮法：

• Huffman Encoding：根據各符號出現頻率建立最佳前綴碼，頻率越高通常使用越短的編碼。
• Lempel–Ziv Encoding：利用已出現過的字串建立字典，以字典索引與新符號表示目前字串。

題目中的字元採一般英文字母 $A,B,C$ 解讀，訊息為：

$$B A A B B B B A A C A A$$

共有 $12$ 個字元，統計頻率如下：

符號	次數
$A$	$6$
$B$	$5$
$C$	$1$

---

(A) Huffman Encoding

1. 建立 Huffman Tree

依頻率由小到大排列：

$$C:1,\quad B:5,\quad A:6$$

先合併頻率最小的兩個節點：

$$C(1)+B(5)=6$$

此時兩個節點的權重皆為 $6$：

• $A:6$
• $(B,C):6$

將兩者合併成根節點：

$$A(6)+(B,C)(6)=12$$

指定左分支為 $0$、右分支為 $1$，可得到下列一組合法 Huffman code：

符號	Huffman code
$A$	$0$
$B$	$10$
$C$	$11$

由於本題在合併時出現權重相同的節點，左右分支對調也會得到另一組同樣最佳的編碼；只要編碼可被唯一解碼，皆屬正確答案。

2. 編碼

原訊息逐字替換：

$$\begin{aligned} B A A B B B B A A C A A &\to 10\ 0\ 0\ 10\ 10\ 10\ 10\ 0\ 0\ 11\ 0\ 0 \end{aligned}$$

連接後得到：

$$\boxed{100010101010001100}$$

位元數為：

$$5\times 2+6\times 1+1\times 2=18\text{ bits}$$

原本若以固定長度二進位表示三種符號，每個符號至少需要 $2$ bits，共需：

$$12\times 2=24\text{ bits}$$

因此 Huffman 編碼後為 $18$ bits。

3. 解碼

使用前綴碼表：

• 讀到 $0$，解碼為 $A$
• 讀到 $10$，解碼為 $B$
• 讀到 $11$，解碼為 $C$

將編碼串切分：

$$10\ |\ 0\ |\ 0\ |\ 10\ |\ 10\ |\ 10\ |\ 10\ |\ 0\ |\ 0\ |\ 11\ |\ 0\ |\ 0$$

因此解碼為：

$$\boxed{B A A B B B B A A C A A}$$

---

(B) Lempel–Ziv Encoding

1. 採用的編碼版本

「Lempel Ziv」有 LZ77、LZ78 等不同變形。以下採用考試中最常見、且可直接建立字典的 LZ78。

LZ78 的輸出格式為：

$$(\text{字典索引},\text{下一個新字元})$$

規則如下：

1. 字典初始為空，索引 $0$ 表示空字串。
2. 從目前位置開始，找出字典中最長的既有字串。
3. 輸出該字串的索引，以及接在後面的新字元。
4. 將「既有字串＋新字元」加入字典。

2. 編碼過程

核心觀念

本題考查三個計算機概論的重要基礎觀念：

1. 物件導向程式設計中的繼承與封裝。
2. OSI 模型第二層資料鏈結層的功能與運作方式。
3. 作業系統程序管理中的死結與飢餓。

---

a. OOP 的繼承與封裝

核心觀念

1. 繼承（Inheritance）

繼承是指子類別（subclass）取得父類別（superclass）既有的資料與方法，並可進一步擴充或覆寫功能。

例如：

Vehicle（父類別）
 ├── Car（子類別）
 └── Bicycle（子類別）

Car 可繼承 Vehicle 的速度、啟動等共同屬性與方法，再加入自身特有的車門數量、空調功能。

繼承的主要目的包括：

• 重複使用既有程式碼。
• 建立類別之間的階層關係。
• 利用多型（polymorphism）處理不同子類別的物件。
• 將共同功能集中於父類別，降低維護成本。

繼承通常具有「is-a」關係，例如：

• 汽車是一種交通工具。
• 狗是一種動物。

若兩個類別只有「使用關係」，則不適合使用繼承。例如「汽車擁有引擎」是「has-a」關係，通常以組合（composition）表示。

2. 封裝（Encapsulation）

封裝是將物件的資料與操作資料的方法包裝在同一個類別中，並限制外部直接存取內部資料。

例如，銀行帳戶的餘額不應由外部直接修改，而應透過存款與提款方法改變：

class Account {
    private balance;

    public deposit(amount) {
        balance = balance + amount;
    }

    public withdraw(amount) {
        if (amount <= balance) {
            balance = balance - amount;
        }
    }
}

其中 balance 設為 private，外部程式不能任意指定其數值，只能透過公開方法操作。

封裝的目的包括：

• 隱藏物件內部實作細節。
• 防止資料被不當修改。
• 透過方法統一執行合法性檢查。
• 降低類別之間的耦合程度。
• 提高程式的安全性、可維護性與可修改性。

常見存取修飾詞如下：

• private：只有類別本身可以存取。
• protected：類別本身及其子類別可以存取。
• public：外部程式也可以存取。

解題方法

回答這類名詞題時，應分別寫出「定義、目的、例子」：

• 繼承：強調「子類別取得父類別的屬性與方法」。
• 封裝：強調「資料與方法包裝」以及「限制外部直接存取」。

兩者容易混淆，但重點不同：

概念	主要重點	解決問題
繼承	類別之間的階層與重用	減少重複程式碼
封裝	隱藏資料與控制存取	保護資料、降低耦合

解題技巧

• 看到「子類別取得父類別功能」即聯想到繼承。
• 看到 private、資料隱藏、getter/setter、存取控制，即聯想到封裝。
• 繼承不等於複製程式碼；子類別通常可擴充父類別功能。
• 封裝不只是把資料與方法放在同一個類別，也包含對資料存取權限的控制。

---

b. OSI 模型的資料鏈結層

核心觀念

資料鏈結層（Data-link Layer）是 OSI 七層模型的第二層，位於實體層之上、網路層之下。

其主要任務是在「直接相連的節點」之間，提供可靠且有規則的資料傳輸。資料鏈結層所處理的資料單位稱為訊框（frame）。

OSI 模型中，資料鏈結層的主要功能如下。

1. 成框（Framing）

資料鏈結層將網路層傳下來的封包切割並包裝成訊框，加入標頭與尾端資訊，使接收端能辨識：

• 一個訊框從哪裡開始。
• 一個訊框在哪裡結束。
• 訊框所屬的來源與目的地。

2. 實體位址識別

資料鏈結層通常使用 MAC 位址識別同一區域網路中的網路介面。

MAC 位址主要用於區域網路內的節點傳送；IP 位址則由網路層用於跨網路的邏輯定址。兩者用途不同：

• MAC 位址：區域網路內的硬體位址。
• IP 位址：跨網路傳輸時的邏輯位址。

3. 錯誤偵測與處理

資料鏈結層可在訊框中加入錯誤偵測資訊，例如循環冗餘檢查（CRC）。接收端重新計算檢查值，若與訊框中的值不一致，即表示傳輸過程可能發生錯誤。

CRC 的概念可表示為：

$$\text{接收端計算的 CRC} \neq \text{訊框所附的 CRC}$$

代表訊框內容可能已遭破壞。

資料鏈結層常具備錯誤偵測能力，但是否負責重新傳送，取決於具體協定。不能一概認定所有資料鏈結層協定都會自動修正錯誤。

4. 流量控制

當傳送端速度比接收端快時，資料鏈結層可透過流量控制避免接收端緩衝區溢位。

5. 媒體存取控制

在多個裝置共用同一傳輸媒體時，資料鏈結層必須規範何時可以傳送資料，避免多個節點同時傳送造成碰撞。

核心觀念

本題考查三種基本排序法，並要求將資料依「遞減順序」排列：

$114>98>25>20>16>6>1$

原始序列為：

$20,\ 1,\ 98,\ 25,\ 114,\ 16,\ 6$

遞減排序的判斷原則是：若左側元素小於右側元素，就必須交換，使較大的元素逐漸移向左側。

三種排序法的核心概念如下：

• Bubble Sort：反覆比較相鄰元素，將較大的元素逐步移至前方。
• Selection Sort：每一回合從未排序部分找出最大值，放到目前未排序部分的最前端。
• Insertion Sort：維持左側部分為遞減排序，逐一將新元素插入正確位置。

---

一、Bubble Sort 氣泡排序法

解題方法

為了得到遞減順序，每次比較相鄰兩元素：

若

$A[j]<A[j+1]$

則交換兩者，使較大的元素往左移動。

每一回合結束後，最小的元素會被推至目前範圍的最右端，因此右側已排序區域逐漸增加。

第 1 回合

初始序列：

$20,\ 1,\ 98,\ 25,\ 114,\ 16,\ 6$

依序比較相鄰元素：

1. 比較 $20$ 與 $1$：不交換
   $20,\ 1,\ 98,\ 25,\ 114,\ 16,\ 6$

2. 比較 $1$ 與 $98$：交換
   $20,\ 98,\ 1,\ 25,\ 114,\ 16,\ 6$

3. 比較 $1$ 與 $25$：交換
   $20,\ 98,\ 25,\ 1,\ 114,\ 16,\ 6$

4. 比較 $1$ 與 $114$：交換
   $20,\ 98,\ 25,\ 114,\ 1,\ 16,\ 6$

5. 比較 $1$ 與 $16$：交換
   $20,\ 98,\ 25,\ 114,\ 16,\ 1,\ 6$

6. 比較 $1$ 與 $6$：交換
   $20,\ 98,\ 25,\ 114,\ 16,\ 6,\ 1$

第 1 回合結果：

$20,\ 98,\ 25,\ 114,\ 16,\ 6\mid 1$

其中 $1$ 已位於正確的最後位置。

第 2 回合

$20,\ 98,\ 25,\ 114,\ 16,\ 6\mid 1$

1. $20<98$，交換：

$98,\ 20,\ 25,\ 114,\ 16,\ 6\mid 1$

2. $20<25$，交換：

$98,\ 25,\ 20,\ 114,\ 16,\ 6\mid 1$

3. $20<114$，交換：

$98,\ 25,\ 114,\ 20,\ 16,\ 6\mid 1$

4. $20>16$，不交換
5. $16>6$，不交換

第 2 回合結果：

$98,\ 25,\ 114,\ 20,\ 16,\ 6\mid 1$

第 3 回合

1. $98>25$，不交換
2. $25<114$，交換：

$98,\ 114,\ 25,\ 20,\ 16,\ 6\mid 1$

3. $25>20$，不交換
4. $20>16$，不交換

結果：

$98,\ 114,\ 25,\ 20,\ 16,\ 6\mid 1$

第 4 回合

比較 $98$ 與 $114$：

$98<114$

交換後：

$114,\ 98,\ 25,\ 20,\ 16,\ 6,\ 1$

其餘元素皆已依遞減順序排列。

Bubble Sort 結果

$\boxed{114,\ 98,\ 25,\ 20,\ 16,\ 6,\ 1}$

---

二、Selection Sort 選擇排序法

解題方法

每一回合從尚未排序的部分找出最大值，並與該部分的第一個元素交換。

第 $i$ 回合完成後，前 $i+1$ 個元素必定是目前最大的 $i+1$ 個元素，且已依遞減順序排列。

第 1 回合

未排序部分：

$20,\ 1,\ 98,\ 25,\ 114,\ 16,\ 6$

最大值為 $114$，與第一個元素 $20$ 交換：

$114,\ 1,\ 98,\ 25,\ 20,\ 16,\ 6$

已排序部分：

$114\mid 1,\ 98,\ 25,\ 20,\ 16,\ 6$

第 2 回合

未排序部分：

$1,\ 98,\ 25,\ 20,\ 16,\ 6$

核心觀念

本題考查二進位、八進位、十進位與十六進位之間的基數轉換。

各進位制的位值公式為：

$$(d_nd_{n-1}\cdots d_0.d_{-1}d_{-2}\cdots)_b = \sum_{i} d_i b^i$$

其中 $b$ 為基底。

常用快速轉換關係：

• $1$ 個十六進位數字 = $4$ 個二進位位元。
• $1$ 個八進位數字 = $3$ 個二進位位元。
• 十六進位與八進位之間，可先轉成二進位再分組。
• 小數點左側由右向左分組；小數點右側由左向右分組。不足位數時補 $0$。

解題方法與計算

a. $(\mathrm{F27.D})_{16}$ 轉換為八進位

先將每個十六進位數字轉成四位二進位：

$$\mathrm{F}=1111,\quad 2=0010,\quad 7=0111,\quad \mathrm{D}=1101$$

因此：

$$(\mathrm{F27.D})_{16} = (111100100111.1101)_2$$

八進位每一位對應三個二進位位元，從小數點向兩側分組：

$$111100100111.1101 = 111\ 100\ 100\ 111.110\ 100$$

將每組轉成八進位：

$$111_2=7,\quad 100_2=4,\quad 100_2=4,\quad 111_2=7$$ $$110_2=6,\quad 100_2=4$$

所以：

$$(\mathrm{F27.D})_{16}=(7447.64)_8$$

---

b. $(110101.101)_2$ 轉換為八進位

八進位每一位對應三個二進位位元，直接分組：

$$110101.101 = 110\ 101.101$$

各組轉換為八進位：

$$110_2=6,\quad 101_2=5,\quad 101_2=5$$

因此：

$$(110101.101)_2=(65.5)_8$$

---

c. $(12.3)_8$ 轉換為二進位

每一個八進位數字直接換成三位二進位：

$$1_8=001_2,\quad 2_8=010_2,\quad 3_8=011_2$$

因此：

$$(12.3)_8=(001010.011)_2$$

整數部分最左側的 $0$ 可省略：

$$(12.3)_8=(1010.011)_2$$

---

此題分為兩部分：第一部分要求描述 Dijkstra 演算法並提供範例；第二部分則要求探討將 Dijkstra 演算法應用於腫瘤放射治療計畫設計的關鍵考量。

---

第一部分：Dijkstra 演算法描述與範例

Dijkstra 演算法描述：
Dijkstra 演算法是一種用於尋找圖中單源最短路徑的貪心演算法。它適用於邊權為非負權重的圖。演算法的核心思想是逐步擴展一個「已確定最短路徑」的頂點集合。

演算法步驟：

1. 初始化：

   • 為所有頂點設定一個初始距離。源頂點的距離設為 0，所有其他頂點的距離設為無限大 ($\infty$)。
   • 創建一個集合 S，用於存放已經找到最短路徑的頂點，初始為空。
   • 創建一個集合 Q，包含所有頂點（或使用一個優先佇列，按距離排序）。

2. 迭代： 當 Q 非空時，重複以下步驟：

   • 從 Q 中選取一個距離值最小的頂點 u。
   • 將 u 從 Q 中移除，並加入到集合 S 中。
   • 對於 u 的每一個鄰居 v（即存在邊 $(u, v)$）：
     • 計算從源頂點經由 u 到達 v 的距離：alt = dist(source, u) + weight(u, v)。
     • 如果 alt 小於 v 當前的距離 dist(source, v)，則更新 v 的距離：dist(source, v) = alt。同時，可以記錄 v 的前驅節點為 u，以便之後重建路徑。

3. 結束： 當 Q 為空時，演算法結束。此時，源頂點到所有其他頂點的最短路徑距離都已確定。

範例：
考慮以下加權無向圖，尋找從頂點 A 到其他所有頂點的最短路徑：

圖的表示：

• 邊 (A, B)，權重 4
• 邊 (A, C)，權重 2
• 邊 (B, E)，權重 3
• 邊 (C, D)，權重 2
• 邊 (C, F)，權重 4
• 邊 (D, E)，權重 3
• 邊 (D, F)，權重 1
• 邊 (E, F)，權重 1

初始化：

• dist = {A: 0, B: $\infty$, C: $\infty$, D: $\infty$, E: $\infty$, F: $\infty$}
• S = {}
• Q = {A, B, C, D, E, F}

迭代過程：

Iteration 1:

• 從 Q 選取距離最小的頂點 u = A (距離 0)。
• S = {A}, Q = {B, C, D, E, F}
• 鄰居 v：B, C
  • 對於 B：alt = dist(A) + w(A, B) = 0 + 4 = 4。dist(B) ($\infty$) > 4，更新 dist(B) = 4。前驅節點(B) = A。
  • 對於 C：alt = dist(A) + w(A, C) = 0 + 2 = 2。dist(C) ($\infty$) > 2，更新 dist(C) = 2。前驅節點(C) = A。
• dist = {A: 0, B: 4, C: 2, D: $\infty$, E: $\infty$, F: $\infty$}

Iteration 2:

• 從 Q 選取距離最小的頂點 u = C (距離 2)。
• S = {A, C}, Q = {B, D, E, F}
• 鄰居 v：A, D, F
  • A 已在 S 中，忽略。
  • 對於 D：alt = dist(C) + w(C, D) = 2 + 2 = 4。dist(D) ($\infty$) > 4，更新 dist(D) = 4。前驅節點(D) = C。
  • 對於 F：alt = dist(C) + w(C, F) = 2 + 4 = 6。dist(F) ($\infty$) > 6，更新 dist(F) = 6。前驅節點(F) = C。
• dist = {A: 0, B: 4, C: 2, D: 4, E: $\infty$, F: 6}

Iteration 3:

• 從 Q 選取距離最小的頂點 u = B (距離 4) 或 u = D (距離 4)。假設選擇 B。
• S = {A, C, B}, Q = {D, E, F}
• 鄰居 v：A, E
  • A 已在 S 中，忽略。
  • 對於 E：alt = dist(B) + w(B, E) = 4 + 3 = 7。dist(E) ($\infty$) > 7，更新 dist(E) = 7。前驅節點(E) = B。
• dist = {A: 0, B: 4, C: 2, D: 4, E: 7, F: 6}

Iteration 4:

• 從 Q 選取距離最小的頂點 u = D (距離 4)。
• S = {A, C, B, D}, Q = {E, F}
• 鄰居 v：C, E, F
  • C 已在 S 中，忽略。
  • 對於 E：alt = dist(D) + w(D, E) = 4 + 3 = 7。dist(E) (7) $\ngtr$ 7，不更新。
  • 對於 F：alt = dist(D) + w(D, F) = 4 + 1 = 5。dist(F) (6) > 5，更新 dist(F) = 5。前驅節點(F) = D。
• dist = {A: 0, B: 4, C: 2, D: 4, E: 7, F: 5}

Iteration 5:

• 從 Q 選取距離最小的頂點 u = F (距離 5)。
• S = {A, C, B, D, F}, Q = {E}
• 鄰居 v：C, D, E
  • C, D 已在 S 中，忽略。
  • 對於 E：alt = dist(F) + w(F, E) = 5 + 1 = 6。dist(E) (7) > 6，更新 dist(E) = 6。前驅節點(E) = F。

核心觀念

二元樹的走訪定義如下：

• Preorder（前序）：根節點 → 左子樹 → 右子樹
• Inorder（中序）：左子樹 → 根節點 → 右子樹

本題利用兩種走訪結果重建二元樹，關鍵定理是：

前序走訪的第一個節點必定是目前子樹的根節點；在中序走訪中，根節點左側的節點屬於左子樹，右側的節點屬於右子樹。

已知：

• 前序：JCBADEFIGH
• 中序：ABCEDFJGIH

---

解題方法

1. 找出整棵樹的根節點

前序的第一個節點是 J，因此 J 為整棵樹的根。

在中序中找到 J：

$$ABCEDF \mid J \mid GIH$$

因此：

• J 的左子樹包含：A、B、C、D、E、F
• J 的右子樹包含：G、H、I

前序中，根節點 J 之後，先列出左子樹的 6 個節點，再列出右子樹的 3 個節點：

$$J \mid CBADEF \mid IGH$$

---

2. 建立 J 的左子樹

左子樹的前序為：

CBADEF

左子樹的中序為：

ABCEDF

前序第一個節點是 C，所以 C 是左子樹的根。

在中序中找到 C：

$$AB \mid C \mid EDF$$

因此：

• C 的左子樹包含 A、B
• C 的右子樹包含 E、D、F

建立 C 的左子樹

前序為 BA，中序為 AB。

前序第一個節點是 B，所以 B 為根。中序為：

$$A \mid B$$

因此 B 沒有右子樹，且左子節點為 A。

建立 C 的右子樹

前序為 DEF，中序為 EDF。

前序第一個節點是 D，所以 D 為根。中序為：

$$E \mid D \mid F$$

因此：

• D 的左子節點為 E
• D 的右子節點為 F

---

3. 建立 J 的右子樹