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

這題考驗對二元樹（Binary Tree）前序（Preorder）、中序（Inorder）及後序（Postorder）遍歷（Traversal）的理解與應用。已知前序和中序遍歷序列，可以唯一重建二元樹，進而求得後序遍歷序列。

核心觀念：

• 前序遍歷 (Preorder Traversal): 根節點 -> 左子樹 -> 右子樹 (Root -> Left -> Right)
• 中序遍歷 (Inorder Traversal): 左子樹 -> 根節點 -> 右子樹 (Left -> Root -> Right)
• 後序遍歷 (Postorder Traversal): 左子樹 -> 右子樹 -> 根節點 (Left -> Right -> Root)

解題步驟：

1. 找出根節點： 前序遍歷的第一個節點永遠是樹的根節點。在此例中，根節點是 'M'。
2. 分割中序遍歷： 在中序遍歷序列中找到根節點 'M'。'M' 左邊的所有節點屬於左子樹，右邊的所有節點屬於右子樹。
   • 中序：C, A, B, K, F, D, M, G, H
   • 左子樹節點（中序）：C, A, B, K, F, D
   • 右子樹節點（中序）：G, H
3. 分割前序遍歷： 前序遍歷的序列長度與中序遍歷的節點數相同。從前序遍歷中，移除根節點 'M' 後，緊接著的節點數等於左子樹的節點數，這部分節點構成左子樹的前序遍歷。剩餘的節點則構成右子樹的前序遍歷。
   • 前序：M, B, C, A, F, K, D, G, H
   • 左子樹前序（包含 M 之後的 6 個節點）：B, C, A, F, K, D
   • 右子樹前序（包含 M 之後的 2 個節點）：G, H
4. 遞迴建構左子樹：
   • 左子樹根節點：左子樹前序的第一個節點是 'B'。
   • 在中序序列 (C, A, B, K, F, D) 中找到 'B'。
   • 左子樹的左子樹節點（中序）：C, A
   • 左子樹的右子樹節點（中序）：K, F, D
   • 從左子樹前序 (B, C, A, F, K, D) 中，移除根節點 'B'，緊接著的 2 個節點 (C, A) 是左子樹的左子樹前序。剩下的 4 個節點 (F, K, D) 是左子樹的右子樹前序。
   • 遞迴建構左子樹的左子樹：
     • 根節點：前序 (C, A) 的第一個是 'C'。
     • 中序 (C, A) 中，'C' 左邊沒有節點（左子樹為空），右邊是 'A'。
     • 前序 (C, A) 中，'C' 後面的 0 個節點是左子樹，1 個節點 'A' 是右子樹。
     • 所以，'C' 是根節點，右子節點是 'A'。
   • 遞greencar建構左子樹的右子樹：
     • 根節點：前序 (F, K, D) 的第一個是 'F'。
     • 中序 (K, F, D) 中，'F' 左邊是 'K'，右邊是 'D'。

核心觀念

Huffman Coding 是一種以「變動長度前綴碼」進行無損壓縮的方法，核心原則如下：

1. 字元出現頻率越高，通常配置越短的編碼。
2. 每次選取目前頻率最低的兩個節點合併。
3. 合併後的新節點頻率等於兩子節點頻率總和。
4. 編碼具有前綴碼性：任何字元的編碼都不是另一字元編碼的前綴，因此可以唯一解碼。
5. 本題指定左分支為 $0$、右分支為 $1$，且低頻節點置於左側；頻率相同時依 ASCII 值或字母順序決定左右。

---

解題方法

先計算字串：

$$\text{BANANA\_BANDANA}$$

各字元出現次數如下：

字元	頻率
A	6
N	4
B	2
D	1
_	1

字串總長度為 $14$，頻率總和為：

$$6+4+2+1+1=14$$

依 Huffman 規則，由最低頻率開始合併。

步驟一：合併 D 與 _

兩者頻率皆為 $1$，依 ASCII 值：

$$\text{D}=68 < \text{\_}=95$$

因此 D 放左側、_ 放右側：

$$(D,\_): 1+1=2$$

對應分支為：

• D：$0$
• _：$1$

步驟二：合併 B 與 $(D,\_)$

兩者頻率皆為 $2$。B 的排序位置低於由 D、_ 組成的節點，因此 B 放左側：

$$B:2 \quad+\quad (D,\_):2 \quad\longrightarrow\quad 4$$

步驟三：合併 $(B,D,\_)$ 與 N

兩者頻率皆為 $4$。依節點中代表字元的排序，B 低於 N，因此 $(B,D,\_)$ 放左側：

$$(B,D,\_):4 \quad+\quad N:4 \quad\longrightarrow\quad 8$$

步驟四：合併 A 與前述頻率為 8 的節點

$$A:6 \quad+\quad (B,D,\_,N):8 \quad\longrightarrow\quad 14$$

A 頻率較低，因此放左側。

---

Huffman Tree

這題考驗對 TCP/IP 協定堆疊（Protocol Stack）中各層功能的理解，特別是網路層的路由功能，以及傳輸層中 TCP 和 UDP 的差異與應用場景。

核心觀念：

• TCP/IP 模型： 通常分為四層：應用層 (Application Layer)、傳輸層 (Transport Layer)、網際網路層 (Internet Layer / Network Layer)、網路介面層 (Network Interface Layer / Link Layer)。
• 網路層 (Internet Layer): 主要負責將封包從來源傳送到目的地，跨越不同的網路。路由器 (Router) 工作在此層。
• 傳輸層 (Transport Layer): 在端對端（End-to-End）之間提供通訊服務。主要的協定是 TCP (Transmission Control Protocol) 和 UDP (User Datagram Protocol)。
  • TCP: 提供可靠的、有連接的、有序的、錯誤檢查的資料傳輸。適合要求高可靠性的應用（如網頁瀏覽、檔案傳輸）。
  • UDP: 提供不可靠的、無連接的、盡力而為的資料傳輸。速度快，開銷小，但可能丟失封包或順序錯亂。適合對延遲敏感且能容忍少量丟失的應用（如串流媒體、線上遊戲、DNS）。

解題步驟：

a. Which layer is responsible for routing packets across different networks?

• 解釋： 路由（Routing）是將資料封包從來源主機傳送到目的地主機的過程，這個過程可能需要經過多個中間網路和路由器。負責這個功能的是 TCP/IP 模型中的 網路層 (Internet Layer / Network Layer)。網路層的協定（如 IP - Internet Protocol）定義了封包的格式、定址以及路由選擇的機制。路由器是工作在網路層的設備，它們根據封包的目的 IP 位址來決定封包的下一跳路徑。

【答案】 網路層 (Network Layer / Internet Layer)。

b. What is the difference between TCP and UDP? Why might a real-time patient monitoring system prefer UDP for live waveform streaming?

• TCP 與 UDP 的差異：

  特性	TCP (Transmission Control Protocol)	UDP (User Datagram Protocol)
  連接性	有連接 (Connection-oriented)，需要建立三次握手連接。	無連接 (Connectionless)，不需要事先建立連接。

這題考驗對作業系統中 CPU 排程（CPU Scheduling）概念的理解，特別是「搶佔式 (Preemptive)」與「非搶佔式 (Non-preemptive)」排程的區別，以及如何應用「最短作業優先 (Shortest Job First, SJF)」的非搶佔式演算法來計算平均等待時間。

核心觀念：

• CPU 排程： 作業系統決定哪個就緒的程序（Process）將獲得 CPU 使用權，以及何時獲得。
• 非搶佔式排程 (Non-preemptive Scheduling): 一旦 CPU 被分配給一個程序，該程序將一直持有 CPU，直到它自己主動釋放 CPU（例如完成執行或進入等待狀態）。其他程序無法中斷它。
• 搶佔式排程 (Preemptive Scheduling): CPU 可以被作業系統從當前執行的程序手中搶走，並分配給另一個具有更高優先級或滿足特定條件的程序。這通常用於時間分享系統，以確保所有程序都能在合理的時間內獲得 CPU。
• 最短作業優先 (Shortest Job First, SJF): 是一種排程演算法，它總是選擇就緒佇列中預期執行時間（Burst Time）最短的程序來執行。
  • 非搶佔式 SJF: 一旦程序開始執行，即使有更短的程序進入就緒佇列，它也會執行完畢。
  • 搶佔式 SJF (也稱為 Shortest Remaining Time First, SRTF): 如果一個新進入的程序其剩餘執行時間比當前執行程序剩餘執行時間短，則會發生搶佔。
• 等待時間 (Waiting Time): 程序在就緒佇列中等待 CPU 分配的時間。
• 平均等待時間 (Average Waiting Time): 所有程序的等待時間總和除以程序的總數。

解題步驟：

1. 解釋搶佔式與非搶佔式排程的區別：

• 非搶佔式排程 (Non-preemptive Scheduling):
  一旦 CPU 被分配給一個程序，該程序將一直執行，直到它完成或自願放棄 CPU（例如 I/O 操作）。其他程序即使就緒，也必須等到當前程序執行完畢後才能獲得 CPU。這種方式實現簡單，但可能導致短任務長時間等待（「 the convoy effect」）。
• 搶佔式排程 (Preemptive Scheduling):
  CPU 可以被從當前執行的程序手中「搶走」，並分配給另一個程序。這種搶佔通常基於優先級（例如，一個高優先級的程序進入就緒狀態）或時間片（Time Slice）的到期。搶佔式排程能更好地響應短任務，提高系統的響應時間和公平性，但實現更複雜，需要額外的硬體支持（如計時器）和軟體開銷（如上下文切換）。

核心觀念

本題考查：

• **Singly Linked List（單向鏈結串列）**的節點結構。
• 透過指標重新連接節點，使串列方向完全反轉。
• 反轉過程中必須保留尚未處理部分的起點，避免遺失後續節點。
• 空串列與只有一個節點的串列也必須能正確處理。

單向鏈結串列的每個節點包含兩個欄位：

1. data：儲存資料。
2. next：指向下一個節點；最後一個節點的 next 為 NULL。

例如：

$$A \rightarrow B \rightarrow C \rightarrow NULL$$

反轉後應為：

$$C \rightarrow B \rightarrow A \rightarrow NULL$$

解題方法

採用迭代法，使用三個指標：

• previous：目前節點反轉後要指向的前一個節點。
• current：目前正在處理的節點。
• nextNode：暫存目前節點原本的下一個節點。

初始狀態：

previous = NULL
current = head

每次處理一個節點時，依序執行：

1. 先保存後續節點：

   nextNode = current.next
   

2. 將目前節點的方向反轉：

   current.next = previous
   

3. 三個指標向前移動：

   previous = current
   current = nextNode
   

當 current 變成 NULL，代表所有節點都已處理完畢，此時 previous 就是新的串列首節點。

節點結構與偽程式碼

Structure Node
    data
    next : Node
End Structure

Algorithm ReverseSinglyLinkedList(head)

    previous ← NULL
    current ← head

    While current ≠ NULL do

        nextNode ← current.next
        current.next ← previous
        previous ← current
        current ← nextNode

    End While

    Return previous

End Algorithm

執行過程示範

假設原串列為：

head
 ↓
A → B → C → NULL

第一次迭代

初始：

previous = NULL
current = A

保存 A 的下一個節點：

nextNode = B

反轉連結：

A.next = NULL

指標前進：

previous = A
current = B

目前狀態：

A → NULL

B → C → NULL

第二次迭代

保存：

nextNode = C

反轉：

B.next = A

指標前進：

這題考驗對物件導向程式設計 (Object-Oriented Programming, OOP) 核心概念的理解，包括多型 (Polymorphism) 以及建構子 (Constructor) 與解構子 (Destructor) 的作用。

核心觀念：

• 物件導向程式設計 (OOP): 一種程式設計範式，以「物件」為中心，強調資料封裝、繼承和多型。
• 封裝 (Encapsulation): 將資料（屬性）和操作資料的方法（行為）綁定在一起，形成一個獨立的單元（物件），並隱藏內部實現細節。
• 繼承 (Inheritance): 允許一個類別（子類別）繼承另一個類別（父類別）的屬性和方法，從而實現程式碼的重用和層次結構。
• 多型 (Polymorphism): 允許不同類型的物件對相同的訊息（方法呼叫）做出不同的響應。
• 建構子 (Constructor): 在建立物件時自動呼叫的特殊方法，用於初始化物件的狀態（屬性）。
• 解構子 (Destructor): 在物件被銷毀（記憶體釋放）時自動呼叫的特殊方法，用於清理物件佔用的資源。

解題步驟：

a. Polymorphism

• 解釋： 多型（Polymorphism）是物件導向程式設計的三大基本特徵之一（另外兩個是封裝和繼承）。它的字面意思是「多種形態」。在 OOP 中，多型允許我們使用一個統一的介面來處理不同類型的物件。最常見的多型形式是：

  1. 運行時多型 (Runtime Polymorphism) / 方法覆寫 (Method Overriding): 這通常透過繼承實現。子類別可以重新定義（覆寫）父類別中的方法，使其具有不同的行為。當透過父類別的指標或參考呼叫被覆寫的方法時，實際執行的是子類別的版本（這取決於物件的實際類型，稱為「動態綁定」或「晚期綁定」）。
     • 範例： 假設有一個 Animal 類別，其中有一個 makeSound() 方法。Dog 和 Cat 類別繼承自 Animal，並分別覆寫 makeSound() 方法來發出「Woof」和「Meow」的聲音。如果我們有一個 Animal* 指標指向一個 Dog 物件，呼叫 animalPtr->makeSound() 會執行 Dog 的 makeSound()。
  2. 編譯時多型 (Compile-time Polymorphism) / 方法重載 (Method Overloading): 同一個類別中，可以有多個同名的方法，但它們的參數列表（參數類型、數量或順序）必須不同。編譯器會根據傳入的參數來決定呼叫哪個方法。
     • 範例： 一個 Calculator 類別可能有 add(int a, int b) 和 add(double a, double b) 兩個方法。

• 在醫療和生命科學領域的應用：

  • 模擬不同生物行為： 可以建立一個基礎的 Organism 類別，並讓 Virus, Bacteria, Cell 等子類別覆寫 reproduce() 或 metabolize() 方法，以模擬各自獨特的生命週期和行為。
  • 處理不同類型的醫療影像： 可以有一個通用的 ImageProcessor 類別，其中包含 process() 方法。MRIProcessor, CTProcessor, XRayProcessor 等子類別可以覆寫此方法，以執行針對特定影像類型的特徵提取或分析。

【答案】 多型是指程式能夠根據物件的實際類型，以統一的介面來呼叫不同的方法。它允許子類別覆寫父類別的方法（運行時多型）或在同一類別中使用參數不同的同名方法（編譯時多型），從而使程式碼更靈活、可擴展和易於維護。

b. Constructor vs. Destructor

這題考驗對機器學習中「過度擬合 (Overfitting)」概念的理解，以及如何在醫療 AI 模型訓練中預防過度擬合。

核心觀念：

• 過度擬合 (Overfitting): 在機器學習中，過度擬合發生在模型學習了訓練資料中的雜訊和細節，而不是資料底層的模式。這導致模型在訓練資料上表現極佳，但在未見過的測試資料（或實際應用）上表現很差。模型過於複雜，對訓練資料「記憶」過於深刻，失去了泛化能力。
• 欠擬合 (Underfitting): 與過度擬合相反，模型過於簡單，未能捕捉到訓練資料中的基本模式，導致在訓練和測試資料上表現都較差。
• 泛化能力 (Generalization): 模型在新資料上的預測能力。一個好的模型應該具備良好的泛化能力。
• 卷積神經網路 (Convolutional Neural Networks, CNNs): 一種專門用於處理網格狀資料（如圖像）的深度學習模型，廣泛應用於圖像識別、診斷等任務。
• 醫療 AI 模型： 利用 AI 技術（如 CNNs）來輔助醫療診斷、藥物研發、影像分析等。

解題步驟：

1. 解釋什麼是過度擬合 (Overfitting)：

過度擬合是指一個機器學習模型在訓練過程中，過度地學習了訓練資料的細節和雜訊，以至於模型在訓練資料上能達到非常高的準確度，但在應用於新的、未見過的資料時，其預測準確度卻顯著下降。這意味著模型未能從訓練資料中學習到普遍適用的模式，而是「死記硬背」了訓練集的特定樣本。

在醫療影像診斷的場景下，過度擬合可能導致模型對訓練集中某些特定圖像的細微特徵（可能是偽影或不具診斷意義的雜訊）產生過度依賴，從而在面對真實世界的、略有不同的影像時做出錯誤的診斷。例如，一個過度擬合的腫瘤檢測模型可能會學習到訓練影像中特定儀器造成的陰影，並將其誤判為腫瘤。

2. 描述兩種預防過度擬合的方法（針對醫療 AI 模型）：

在訓練醫療 AI 模型時，由於醫療數據的獲取成本高、數據量相對有限，以及對模型準確性的極高要求，預防過度擬合尤為重要。以下是兩種常用的方法：

• 方法一：資料增強 (Data Augmentation)
  • 解釋： 資料增強是一種通過對現有訓練資料進行各種隨機變換來創建新訓練樣本的技術。這些變換旨在模擬真實世界中可能出現的數據變化，同時保持資料的標籤（例如，腫瘤是否存在）不變。對於醫學影像，常見的增強技術包括：
    • 幾何變換： 隨機旋轉、平移、縮放、翻轉（水平或垂直）、剪切。
    • 顏色和對比度調整： 改變亮度、對比度、飽和度、色調。
    • 加入雜訊： 添加高斯雜訊或其他類型的隨機雜訊。
    • 彈性變形 (Elastic Deformations): 模擬組織的輕微變形。
  • 為何有效： 通過增加訓練資料的多樣性，資料增強可以幫助模型學習到更魯棒（robust）的特徵，減少對訓練集中特定樣本細節的依賴，從而提高模型的泛化能力。這相當於在告訴模型：「即使影像看起來有點不一樣，它仍然是同一個東西」。