114 年 國立成功大學數據科學研究所《計算機概論（含資料結構）》

(a) 左子節點值必小於父節點，右子節點值必大於父節點。此性質保證中序遍歷得到遞增序列。 【答案】True

(b) 多型允許同名方法因參數型別或實作不同而具不同行為，涵蓋編譯時 overload 與執行時 override。 【答案】True

(c) 雙重雜湊僅改變探測序列，仍可能在探測過程中產生衝突。 【答案】False（衝突仍會發生）

(d) 單一共享變數若未同步，仍可能被多執行緒同時讀寫，產生競爭條件。 【答案】False

(e) TCP 透過流量控制與重傳機制降低遺失，但無法保證永不遺失，網路錯誤仍可能導致封包遺失。 【答案】False

(f) 图灵机在无限纸带上依規則讀寫符號，是可計算性理論的核心模型。 【答案】True

(g) 單向鍊表無法直接定位中間元素，二分搜尋需逐步走訪，最差需 O(n) 時間，故不保證 O(log n)。 【答案】False

(a) 資料結構與空間複雜度

• 稀疏圖：使用鄰接串列（Adjacency List），每個頂點保存一個「出邊」鏈表或向量，條目為 $(\text{neighbor},\text{weight})$。
  空間：$O(V+E)$（$V$ 為頂點數，$E$ 為邊數）。
• 密集圖：使用鄰接矩陣（Adjacency Matrix），大小為 $V\times V$ 的二維陣列，未存在的邊可用 $\infty$ 表示。
  空間：$O(V^2)$。

適用情境：

• $E \ll V^2$ 時，鄰接串列因 $O(V+E)$ 明顯小於 $O(V^2)$，節省記憶體且遍歷出邊快。
• $E \approx V^2$ 時，鄰接矩陣提供 $O(1)$ 的邊存取，且空間差距不大，適合快速檢索。

【答案】稀疏圖用鄰接串列 $O(V+E)$，密集圖用鄰接矩陣 $O(V^2)$，分別因邊密度不同而最適。

---

(b) 可處理負權邊的單源最短路

• Bellman‑Ford 演算法：可處理任意負權邊，只要圖無負迴路。
  時間複雜度 $O(VE)$，於第 $V-1$ 輪鬆弛後即得最短距離，若第 $V$ 輪仍可鬆弛則存在負迴路。

• Johnson 演算法（若需多源最短路）：先用 Bellman‑Ford 計算節點位移 $h(v)$，重新加權使所有邊非負，再以 Dijkstra 求每一源點。整體 $O(VE+V^2\log V)$。

核心觀念

本題比較作業系統中的兩種並行模型：

• Process-based parallelism（以行程為基礎）：每個工作在獨立的 process 中執行。
• Thread-based parallelism（以執行緒為基礎）：同一個 process 內建立多個 thread，共同執行工作。

比較重點包括：

1. 記憶體是否共享
2. context switch 的成本
3. 工作之間的 communication 成本
4. 在高吞吐量資料管線中的適用情境

---

解題方法

可依序比較三項系統成本，再根據資料管線的工作特性判斷適用模型：

1. 先確認 process 與 thread 的資源隔離程度。
2. 比較切換執行單位時需要保存與載入的狀態。
3. 分析資料交換是否需要跨行程通訊。
4. 最後依工作屬於 I/O-bound 或 CPU-bound，以及是否需要共享大型資料，選擇較有效率的模型。

---

(a) Process-based 與 thread-based 模型的差異

1. 記憶體共享

Process-based

每個 process 通常擁有獨立的虛擬位址空間，因此一個 process 的一般資料不會直接被另一個 process 存取。

例如，若 process $P_1$ 修改變數 $x$，process $P_2$ 不會直接看到相同的修改結果。兩者通常需要透過：

• shared memory
• pipe
• message queue
• socket
• file

等機制交換資料。

獨立記憶體的主要優點是隔離性較好。某個 process 發生錯誤時，通常不會直接破壞其他 process 的資料。

Thread-based

同一個 process 內的 threads 共享：

• code segment
• data segment
• heap
• 開啟的檔案與部分 process 資源

但每個 thread 仍擁有自己的：

• program counter
• registers
• stack
• thread-local storage

因此，多個 threads 可以直接透過共享變數、指標或資料結構交換資料，不必先進行跨行程資料傳送。

缺點是共享資料必須處理同步問題，例如：

• race condition
• deadlock
• data inconsistency

必要時需要使用 mutex、semaphore、monitor 或其他同步機制。

---

2. Context switching 成本

Process context switch

process 切換時，作業系統通常需要切換：

• CPU registers
• program counter
• stack pointer
• page table 或 address-space identifier
• process scheduling information

由於不同 process 可能使用不同的虛擬位址空間，切換時可能造成 TLB（Translation Lookaside Buffer）失效或重新填入，進而增加記憶體位址轉換成本。

因此，process context switch 通常較昂貴。

Thread context switch

同一個 process 內的 thread 共享相同的位址空間，因此切換時主要保存與載入該 thread 的：

• registers
• program counter
• stack pointer
• thread state

通常不需要切換整個 process 的位址空間，故 thread context switch 的成本一般低於 process context switch。

可用概念式表示：

$$C_{\text{thread switch}} < C_{\text{process switch}}$$

其中 $C$ 表示一次 context switch 的系統成本。實際成本仍會受到硬體、作業系統、快取與排程器實作影響。

---

3. Communication 成本

Process-based communication

不同 process 之間通常需要 IPC（Inter-Process Communication）。若使用 pipe、socket 或 message queue，資料往往需要經過核心，可能涉及：

1. 使用者空間資料複製到核心空間。
2. 核心將資料傳送至接收端。
3. 接收端再將資料複製回使用者空間。

因此，資料傳輸可能產生：

• system call
• kernel/user mode transition
• data copying
• synchronization
• serialization／deserialization

等成本。

若使用 shared memory，可以減少資料複製，但仍需要額外的同步機制來避免競爭條件。

Thread-based communication

同一個 process 內的 threads 可直接存取共享記憶體，因此資料交換通常只需讀寫共享資料結構，通信成本較低。

然而，若多個 thread 同時存取相同資料，仍會產生：

• lock contention
• cache coherence traffic
• synchronization overhead

所以 thread communication 並非零成本，但通常比一般的跨 process 通訊便宜。

---

(a) 作答整理

比較項目	Process-based	Thread-based

核心觀念

本題考查作業系統中的「死結（deadlock）」及其在機器學習叢集中的實際處理方式。

死結是指一組程序彼此等待對方持有的資源，導致所有程序都無法繼續執行。死結發生的必要條件稱為 Coffman 四條件，四者必須同時成立：

1. 互斥（Mutual Exclusion）：某項資源同一時間只能由一個程序使用。
2. 持有並等待（Hold and Wait）：程序已持有至少一項資源，同時等待其他資源。
3. 不可剝奪（No Preemption）：程序已取得的資源不能被系統強制取回，只能由程序主動釋放。
4. 循環等待（Circular Wait）：存在一個程序等待環，例如 $P_1$ 等待 $P_2$ 持有的資源，$P_2$ 等待 $P_3$ 的資源，最後 $P_3$ 又等待 $P_1$ 的資源。

只要破壞其中任一條件，就能避免死結。

---

解題方法

（a）死結的四個必要條件

1. 互斥

GPU、GPU 記憶體、大型共享記憶體池等資源，在某些分配模式下無法同時被多個訓練工作使用。例如，一張 GPU 若已被某個訓練工作獨占，其他工作就必須等待。

因此，若資源具有不可共享性，就滿足互斥條件。

2. 持有並等待

假設訓練工作 $J_1$ 已取得 GPU 0，卻繼續等待 GPU 1；同時，訓練工作 $J_2$ 已取得 GPU 1，卻等待 GPU 0。兩個工作都「持有部分資源並等待其他資源」，即符合持有並等待。

3. 不可剝奪

若訓練工作已取得 GPU，叢集排程器通常不能直接將 GPU 記憶體中的模型參數與中間狀態取走，否則可能造成訓練損毀。資源必須等工作完成、失敗或主動釋放後才能重新分配。

因此，若系統不允許強制回收已分配資源，就符合不可剝奪條件。

4. 循環等待

若有下列等待關係：

• $J_1$ 持有 GPU 0，等待 GPU 1；
• $J_2$ 持有 GPU 1，等待 GPU 2；
• $J_3$ 持有 GPU 2，等待 GPU 0；

便形成：

$$J_1 \rightarrow J_2 \rightarrow J_3 \rightarrow J_1$$

此等待環使任何工作都無法取得所需資源，形成死結。

---

（b）GPU 叢集的實務防止策略

可採用「整批分配（gang scheduling）搭配固定資源順序」的策略。

第一步：訓練工作事先宣告需求

每個訓練工作提交時，宣告其最大需求，例如：

• 需要 $4$ 張 GPU；
• 每張 GPU 需要 $40$ GB 記憶體；
• 需要一個大型共享記憶體區域。

排程器不讓工作先取得部分 GPU，再等待其他 GPU，而是等所有必要資源同時可用時一次分配。

第二步：所有資源一次取得

核心觀念

本題考查四組常見計算機科學概念的定義、資料存取規則、適用情境與主要差異：

1. Stacks 與 Queues：線性資料結構的取出順序。
2. Pass-by-Value 與 Pass-by-Reference：函式參數傳遞方式及其對原始變數的影響。
3. Relational Databases 與 NoSQL Databases：資料模型、結構限制與擴充方式。
4. Greedy Algorithms 與 Dynamic Programming：最佳化問題的解題策略與正確性基礎。

---

(a) Stacks vs. Queues

核心觀念

**Stack（堆疊）**遵循 LIFO（Last In, First Out，後進先出）。最後加入的元素會最先被取出。

常見操作：

• push：將元素加入堆疊頂端。
• pop：移除並回傳頂端元素。
• top 或 peek：查看頂端元素但不移除。

**Queue（佇列）**遵循 FIFO（First In, First Out，先進先出）。最早加入的元素會最先被取出。

常見操作：

• enqueue：將元素加入佇列尾端。
• dequeue：移除並回傳佇列前端元素。
• front：查看前端元素但不移除。

解題方法

比較兩者時，應從「資料加入位置」與「資料取出位置」切入：

比較項目	Stack	Queue
取出規則	LIFO	FIFO
加入位置	頂端	尾端
移除位置	頂端	前端
常見應用	函式呼叫、遞迴、括號配對、DFS	排程、列印工作、訊息緩衝、BFS

例如依序加入 $A、B、C$：

• Stack 取出順序為 $C、B、A$。
• Queue 取出順序為 $A、B、C$。

兩者的基本加入與移除操作通常皆可在 $O(1)$ 時間完成。

解題技巧

看到「後進先出」立即聯想到 Stack；看到「先進先出」立即聯想到 Queue。深度優先搜尋通常使用 Stack，廣度優先搜尋通常使用 Queue。

---

(b) Pass-by-Value vs. Pass-by-Reference

核心觀念

**Pass-by-Value（傳值呼叫）**會將實際參數的值複製一份，傳給函式內的形式參數。函式內修改形式參數，不會影響原始變數。

**Pass-by-Reference（傳址／傳參照呼叫）**會將原始變數的參照或記憶體位置傳入函式。形式參數與原始變數指向同一份資料，因此函式內的修改會影響原始變數。

解題方法

判斷兩者差異時，觀察「函式取得的是資料副本，還是原始資料的參照」。

以交換函式為例：

swap(a, b):
    temp = a
    a = b
    b = temp

若使用 Pass-by-Value，函式修改的是 $a$、$b$ 的副本，函式結束後，呼叫端的兩個變數不會交換。

若使用 Pass-by-Reference，函式中的 $a$、$b$ 直接對應呼叫端變數，因此函式結束後，呼叫端的值會完成交換。

比較項目	Pass-by-Value	Pass-by-Reference
傳入內容	值的副本	原始變數的參照或位址
函式內修改是否影響原變數	不會	會
額外複製成本	可能較高	通常較低
副作用	較少	較容易產生
適合情境	保護原始資料	需要修改原始資料或避免大型資料複製

解題技巧

可用「交換兩個變數」快速判斷：若函式執行後呼叫端的變數確實交換，代表具有 Pass-by-Reference 效果。

實際程式語言的實作需依語言規則判斷。例如 C++ 可使用參照參數；C 語言通常透過指標傳址；Java 的基本型別以傳值方式傳遞，而物件參考本身也是以傳值方式傳遞。

---

(c) Relational Databases vs. NoSQL Databases

核心觀念

**Relational Database（關聯式資料庫）**以表格作為主要資料結構，資料由：

• 欄（Column）
• 列（Row）
• 主鍵（Primary Key）
• 外鍵（Foreign Key）
• 表格間的關聯

所組成。

資料通常具有明確且固定的結構，並以 SQL 進行查詢。關聯式資料庫重視資料一致性，常遵循 ACID 特性：

• Atomicity：原子性
• Consistency：一致性
• Isolation：隔離性
• Durability：持久性

NoSQL Database 泛指非傳統關聯式資料庫，常見資料模型包括：

• Document Database：文件型資料庫
• Key-Value Database：鍵值型資料庫
• Column-Family Database：欄式資料庫
• Graph Database：圖形資料庫

(a) 最終 BST

        15
       /  \
      9    20
     / \   / \
    6  12 17 25
      / \  \
     11 14 19

（插入順序依次得到上圖，圖中每個節點皆符合左子樹 < 父節點 < 右子樹的 BST 性質）

(b) 三種遍歷序列

• 前序（Preorder）： $15,\;9,\;6,\;12,\;11,\;14,\;20,\;17,\;19,\;25$
• 中序（Inorder）： $6,\;9,\;11,\;12,\;14,\;15,\;17,\;19,\;20,\;25$

核心觀念

本題綜合考查機器學習的四組基礎概念：

1. 監督式學習與非監督式學習：資料是否具有標籤，以及常見演算法與應用。
2. 過度擬合與擬合不足：模型複雜度與泛化能力的關係。
3. 訓練集、驗證集與測試集：模型訓練、調參與最終評估的分工，以及資料洩漏對評估結果的影響。
4. 參數與超參數：哪些數值由模型從資料中學得，哪些數值由使用者事先設定。

---

(a) 監督式學習與非監督式學習

核心觀念

**監督式學習（supervised learning）**的資料包含輸入與正確答案：

$$\mathcal{D}=\{(x_i,y_i)\}_{i=1}^{n}$$

其中 $x_i$ 是特徵，$y_i$ 是標籤。模型透過學習 $x$ 與 $y$ 的關係，建立預測函數：

$$\hat{y}=f_{\theta}(x)$$

常見任務包括：

• 分類（classification）：預測離散類別，例如是否為垃圾郵件。
• 迴歸（regression）：預測連續數值，例如房價。

常見演算法包括：

• 線性迴歸（linear regression）
• 邏輯斯迴歸（logistic regression）
• 決策樹（decision tree）
• 支援向量機（SVM）
• 隨機森林（random forest）
• 神經網路（neural network）

**非監督式學習（unsupervised learning）**的資料只有輸入特徵，沒有明確標籤：

$$\mathcal{D}=\{x_i\}_{i=1}^{n}$$

模型的目標是找出資料本身的結構、群組或低維表示。常見任務包括：

• 分群（clustering）
• 降維（dimensionality reduction）
• 異常偵測（anomaly detection）

常見演算法包括：

• $k$-means
• 階層式分群（hierarchical clustering）
• DBSCAN
• 主成分分析（PCA）
• 自編碼器（autoencoder）

比較

比較項目	監督式學習	非監督式學習
資料需求	需要輸入資料與標籤	通常只有輸入資料
學習目標	預測標籤或數值	發現資料的內在結構
典型任務	分類、迴歸	分群、降維、異常偵測
代表演算法	決策樹、SVM、神經網路	$k$-means、PCA、DBSCAN
評估方式	準確率、F1-score、均方誤差等	輪廓係數、重建誤差或人工分析

使用例

• 監督式學習：使用已標記的信用卡交易資料，訓練分類模型判斷新交易是否為詐欺交易。
• 非監督式學習：沒有客戶分類標籤時，利用 $k$-means 依照消費行為將客戶分成數個群組，進行市場區隔。

---

(b) 過度擬合與擬合不足

核心觀念

模型的預測誤差通常可分解為偏差（bias）、變異（variance）與不可避免的雜訊：

$$\text{Expected Error} = \text{Bias}^2+\text{Variance}+\text{Noise}$$

• 模型過於簡單，容易產生高偏差，形成擬合不足。
• 模型過於複雜，容易產生高變異，形成過度擬合。

過度擬合（overfitting）

過度擬合是模型過度記憶訓練資料，連同訓練資料中的雜訊也學進去，因此在訓練集表現很好，但在未見過的資料上表現變差。

典型現象：

$$\text{Training Error}\ \text{很低},\qquad \text{Validation/Test Error}\ \text{明顯較高}$$

例如，高次多項式模型可能幾乎通過所有訓練資料點，但對新資料的預測曲線劇烈震盪。

偵測方法

1. 比較訓練集與驗證集的表現。
2. 觀察 learning curve：訓練誤差持續下降，但驗證誤差先下降後上升。
3. 使用交叉驗證，檢查模型在不同資料切分下是否穩定。
4. 檢查模型複雜度，例如樹的深度過深、特徵數過多或神經網路訓練過久。

改善方法

• 增加訓練資料。

• 降低模型複雜度，例如限制決策樹深度。

• 移除不重要或高度雜訊的特徵。

• 使用正規化（regularization）：

  $$\min_{\theta}\; L(\theta)+\lambda\|\theta\|_2^2$$

  其中 $\lambda$ 越大，越限制模型參數的大小。

• 使用 dropout。

• 使用 early stopping，在驗證誤差開始上升前停止訓練。

• 使用資料增強或交叉驗證。

擬合不足（underfitting）

擬合不足是模型過於簡單，無法捕捉資料中的重要規律，因此連訓練資料都無法準確描述。

典型現象：

$$\text{Training Error}\ \text{較高},\qquad \text{Validation/Test Error}\ \text{也較高}$$

偵測方法

1. 觀察訓練集與驗證集的誤差是否同時偏高。
2. 檢查模型是否具有過強的正規化。
3. 觀察模型是否使用過少特徵，或模型形式與資料關係不符。
4. 以 learning curve 判斷模型是否在訓練資料上仍未充分學習。

改善方法

• 提高模型複雜度，例如增加樹深度或神經網路層數。
• 加入具有預測力的新特徵。
• 減弱正規化強度，降低 $\lambda$。
• 增加訓練時間或調整最佳化方法。
• 使用能表達非線性關係的模型。

解題技巧

判斷兩者最有效的方式，是先比較訓練誤差與驗證誤差：

情況	訓練誤差	驗證誤差	判斷
模型過度簡單	高	高	擬合不足
模型適當	低	低且接近	泛化良好
模型記住訓練資料	很低	明顯較高	過度擬合

---

(c) 訓練集、驗證集與測試集

核心觀念

資料切分的目的，是將「學習模型」、「選擇模型」與「最終評估模型」分開。

訓練集（training set）

訓練集用來學習模型參數，例如線性迴歸中的係數：

$$\hat{\theta} = \arg\min_{\theta} L_{\text{train}}(\theta)$$

模型會直接根據訓練集更新參數。

(a) 初始中心點 C₁=(1,1)（點 1） 與 C₂=(5,7)（點 4）
第一次指派後得到

• 群 A：點 1、2、3
• 群 B：點 4、5、6、7

重新計算質心

$C_A^{(1)}=\left(\frac{1+1.5+3}{3},\frac{1+2+4}{3}\right)=(1.8333,\;2.3333)$

$C_B^{(1)}=\left(\frac{5+3.5+4.5+3.5}{4},\frac{7+5+5+4.5}{4}\right)=(4.125,\;5.375)$

第二次指派後得到

• 群 A：點 1、2
• 群 B：點 3、4、5、6、7

再算質心

$C_A^{(2)}=\left(\frac{1+1.5}{2},\frac{1+2}{2}\right)=(1.25,\;1.5)$

$C_B^{(2)}=\left(\frac{3+5+3.5+4.5+3.5}{5},\frac{4+7+5+5+4.5}{5}\right)=(3.9,\;5.1)$

此時指派結果不再變化，演算法收斂。