107 高普考高考三級 統計 資料處理 考古題詳解

核心觀念

1. AVL 樹（Adelson-Velsky and Landis Tree）定義：

• 本質是一棵「二元搜尋樹」（Binary Search Tree, BST），對任何節點而言，左子樹所有節點值 $<$ 該節點值 $<$ 右子樹所有節點值。
• 具備高度平衡性質：樹中任一節點的「平衡係數」（Balance Factor, $BF$）只能為 $-1$、$0$ 或 $+1$。
• 平衡係數定義為： $BF = h_L - h_R$ 其中 $h_L$ 為左子樹高度，$h_R$ 為右子樹高度（空樹高度計為 $0$ 或葉節點高度計為 $1$）。

2. 不平衡的四種旋轉型態： 當新節點插入後，從新節點向上回溯，找到「最深（最低）的失衡節點 $A$」（即 $|BF(A)| > 1$），依據新節點相對於 $A$ 的路徑進行旋轉修正：

• LL 型（左-左）：新節點插入於 $A$ 之左子節點的左子樹 $\implies$ 對 $A$ 進行單右旋（Right Rotation）。
• RR 型（右-右）：新節點插入於 $A$ 之右子節點的右子樹 $\implies$ 對 $A$ 進行單左旋（Left Rotation）。
• LR 型（左-右）：新節點插入於 $A$ 之左子節點的右子樹 $\implies$ 先對左子節點進行左旋，再對 $A$ 進行右旋。
• RL 型（右-左）：新節點插入於 $A$ 之右子節點的左子樹 $\implies$ 先對右子節點進行右旋，再對 $A$ 進行左旋。

3. 二元樹中序追蹤（In-order Traversal）：

• 走訪順序為：左子樹（Left） $\to$ 根節點（Data） $\to$ 右子樹（Right）。
• 二元搜尋樹的中序追蹤結果，數學上必然為嚴格遞增的由小到大排序。

---

解題方法

將給定數列 $2, 1, 5, 9, 8, 3, 4, 6$ 依序插入初始為空的 AVL 樹中，逐步推導如下：

步驟 1：依序插入 $2, 1, 5$

• 插入 $2$：作為樹根。
• 插入 $1$：$1 < 2$，置於 $2$ 之左子節點。
• 插入 $5$：$5 > 2$，置於 $2$ 之右子節點。
• 樹狀結構如下，各節點 $BF$ 均在允許範圍內，無須調整：

 2 (BF = 0)
 / \
 1 5

步驟 2：插入 $9$

• $9 > 2 \to 9 > 5$，置於 $5$ 之右子節點。
• 計算平衡係數：$BF(9) = 0$、$BF(5) = 0 - 1 = -1$、$BF(2) = 1 - 2 = -1$。全樹平衡。

 2 (BF = -1)
 / \
 1 5 (BF = -1)
 \
 9

步驟 3：插入 $8$（觸發第一次旋轉）

• $8 > 2 \to 8 > 5 \to 8 < 9$，置於 $9$ 之左子節點。
• 回溯檢視各節點平衡係數：
• 節點 $9$：$BF(9) = 1 - 0 = +1$
• 節點 $5$：左子樹高 $0$，右子樹高 $2 \implies BF(5) = 0 - 2 = -2$（失衡）
• 最深失衡節點為 $5$。
• 判斷型態：相對於節點 $5$，新節點位於其「右子節點（$9$）的左子樹（$8$）」，屬於 RL 型。
• 執行 RL 雙旋轉：

1. 對節點 $9$ 進行右旋：節點 $8$ 升為節點 $5$ 的右子節點，節點 $9$ 變為節點 $8$ 的右子節點。
2. 對節點 $5$ 進行左旋：節點 $8$ 取代節點 $5$ 的位置，$5$ 降為 $8$ 的左子節點，$9$ 保持為 $8$ 的右子節點。

• 調整後子樹接回原父節點 $2$ 的右方：

 2 (BF = -1)
 / \
 1 8 (BF = 0)
 / \
 5 9

核心觀念

本題旨在測驗資料庫概念設計（Conceptual Design）的核心技術——實體－關係模型（Entity-Relationship Model，簡稱 E-R Model）​之塑模能力。解題需精確掌握以下四大概念：

1. 實體（Entity）與屬性（Attribute）：

• 實體以「矩形」表示；屬性以「橢圓形」表示，並以直線連至所屬實體。
• 主鍵（Primary Key）：為能唯一識別實體之屬性，在屬性名稱下方加繪實線底線。

2. 關係（Relationship）：

• 實體間的互動或聯繫以「菱形」表示，並以直線連至相關實體。

3. 基數比例（Cardinality Ratio）：

• 代表實體之間關聯的數量對應關係，常見有一對一（$1:1$）、一對多（$1:N$）及多對多（$M:N$）。

4. 參與限制（Participation Constraint）：

• 全面參與（Total Participation / 存在相依）：若一實體集合中的每個實體「必定」參與該關係，在 E-R 圖中以雙線（Double Line）​表示（或以 $(min, max)$ 標示為 $min \ge 1$）。
• 部分參與（Partial Participation）：實體集合中僅有部分實體參與該關係，以單線（Single Line）​表示（$min = 0$）。

---

解題方法與實體關係規格分析

本題為非選擇題的系統分析塑模題，解題切入點為依序拆解題目（一）至（四）項之資料需求，嚴格對應出實體、屬性、關係、基數比與參與約束：

1. 實體與屬性界定

• 員工（Employee）：
• 屬性：Employee_name、Employee_seniority。
• 主鍵：Employee_no（題目明定唯一，繪製時加底線）。
• 訂單（Order）：
• 屬性：Order_date。
• 主鍵：Order_no（題目明定唯一，加底線）。
• 部門（Department）：
• 屬性：Department_name。
• 主鍵：Department_no（部門代號為慣常唯一鍵，加底線）。
• 產品（Product）：
• 屬性：Product_name、Product_quantity（庫存數量）。
• 主鍵：Product_no（產品編號具唯一性，加底線）。

2. 關係與基數、參與度分析

• 關係一：部門與員工之「隸屬」（Belong_to）關係
• 基數比：「每個部門有多個員工，且每個員工必要隸屬於一個部門」$\rightarrow$ 部門對員工為 $1:N$。
• 參與度：題目明定「每個員工必要隸屬於一個部門」，故員工端為全面參與（Total Participation，雙線）；部門端可先成立再招募人員，故為部分參與（單線）。
• 關係二：員工與訂單之「承接／負責」（Process / Handle）關係
• 基數比：「訂單必定由一個員工負責承接」，而一位員工可處理多筆訂單 $\rightarrow$ 員工對訂單為 $1:N$。
• 參與度：題目明定「訂單必定由一個員工負責承接」，故訂單端為全面參與（雙線）；員工端並非每位皆有成單紀錄，為部分參與（單線）。
• 關係三：訂單與產品之「包含／明細」（Contain / Include）關係
• 基數比：「每一筆訂單包含多筆產品」，且一項產品亦可被多筆訂單所訂購 $\rightarrow$ 訂單對產品為 $M:N$。
• 參與度：題目明定「一個訂單中必須包含至少一項產品」，故訂單端為全面參與（雙線）；產品端可能尚未售出，為部分參與（單線）。

---

解題技巧與常見陷阱

1. 全面參與（雙線）的遺漏：

• 國考評分關鍵在於「題目文字細節轉換為約束條件」。題幹出現「必定由一個員工負責」、「必要隸屬於一個部門」、「必須包含至少一項產品」，在 Chen 氏 E-R 圖中必須以雙線（Double line）精確標示於該實體至關係的連接線上。

2. 數量的屬性配置陷阱：

• 題目直接將「數量（Product_quantity）」列於產品（Product）項下，此時標準作法是將其直接作為 Product 實體的屬性（代表該產品的庫存量）。

核心觀念

1. 氣泡排序法（Bubble Sort）定義與原理： 氣泡排序法屬於「交換排序法」（Exchange Sort）。其基本運作方式為：由左至右依序比較相鄰的兩個元素，若其先後順序不合目標要求（以由小到大排序為例，即「前者大於後者」），則將兩者位置交換。每一回合（Pass）執行完畢後，未排序區間中的最大值會如同氣泡般浮動至該區間的最右端定位。
2. 回合數與比較次數： 對於長度為 $n$ 的資料序列：

• 第 $i$ 回合需要比較的次數為 $n - i$ 次。
• 傳統演算法共需執行 $n - 1$ 回合。若加上「交換旗標」（Flag）機制，可在某一回合完全沒有發生任何交換時，提早結束演算法。

3. 最壞情況時間複雜度（Worst-Case Time Complexity）： 當輸入資料呈現「完全反序」（由大到小反向排列）時，會觸發最壞情況。此時每一回合的每一次比較都必須進行交換，總比較次數達到最大值： $\sum_{i=1}^{n-1} (n - i) = (n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{n^2 - n}{2}$ 依大 $\mathcal{O}$ 漸近符號定義，最壞情況下之時間複雜度為 $\mathcal{O}(n^2)$。

---

解題方法

本題資料筆數 $n = 7$，初始數列為： $[27, 10, 9, 68, 56, 40, 23]$ 目標為依由小到大（遞增）​進行排序。

一、排序流程（逐回合追蹤）

• 初始狀態： $[27, 10, 9, 68, 56, 40, 23]$

• 第 1 回合（Pass 1）：比較相鄰元素，將目前最大值移動至最後一位（比較 6 次）

1. 比較 $27$ 與 $10$：$27 > 10$，交換 $\rightarrow [10, 27, 9, 68, 56, 40, 23]$
2. 比較 $27$ 與 $9$：$27 > 9$，交換 $\rightarrow [10, 9, 27, 68, 56, 40, 23]$
3. 比較 $27$ 與 $68$：$27 \le 68$，不交換 $\rightarrow [10, 9, 27, 68, 56, 40, 23]$
4. 比較 $68$ 與 $56$：$68 > 56$，交換 $\rightarrow [10, 9, 27, 56, 68, 40, 23]$
5. 比較 $68$ 與 $40$：$68 > 40$，交換 $\rightarrow [10, 9, 27, 56, 40, 68, 23]$
6. 比較 $68$ 與 $23$：$68 > 23$，交換 $\rightarrow [10, 9, 27, 56, 40, 23, \mathbf{68}]$ 第 1 回合結束結果：$[10, 9, 27, 56, 40, 23, \mathbf{68}]$（$68$ 已定位）

• 第 2 回合（Pass 2）：處理前 6 個未排序元素（比較 5 次）

1. 比較 $10$ 與 $9$：$10 > 9$，交換 $\rightarrow [9, 10, 27, 56, 40, 23, 68]$
2. 比較 $10$ 與 $27$：$10 \le 27$，不交換 $\rightarrow [9, 10, 27, 56, 40, 23, 68]$
3. 比較 $27$ 與 $56$：$27 \le 56$，不交換 $\rightarrow [9, 10, 27, 56, 40, 23, 68]$
4. 比較 $56$ 與 $40$：$56 > 40$，交換 $\rightarrow [9, 10, 27, 40, 56, 23, 68]$
5. 比較 $56$ 與 $23$：$56 > 23$，交換 $\rightarrow [9, 10, 27, 40, 23, \mathbf{56}, 68]$ 第 2 回合結束結果：$[9, 10, 27, 40, 23, \mathbf{56}, \mathbf{68}]$（$56$ 已定位）

• 第 3 回合（Pass 3）：處理前 5 個未排序元素（比較 4 次）

1. 比較 $9$ 與 $10$：$9 \le 10$，不交換 $\rightarrow [9, 10, 27, 40, 23, 56, 68]$
2. 比較 $10$ 與 $27$：$10 \le 27$，不交換 $\rightarrow [9, 10, 27, 40, 23, 56, 68]$
3. 比較 $27$ 與 $40$：$27 \le 40$，不交換 $\rightarrow [9, 10, 27, 40, 23, 56, 68]$
4. 比較 $40$ 與 $23$：$40 > 23$，交換 $\rightarrow [9, 10, 27, 23, \mathbf{40}, 56, 68]$ 第 3 回合結束結果：$[9, 10, 27, 23, \mathbf{40}, \mathbf{56}, \mathbf{68}]$（$40$ 已定位）

• 第 4 回合（Pass 4）：處理前 4 個未排序元素（比較 3 次）

1. 比較 $9$ 與 $10$：$9 \le 10$，不交換 $\rightarrow [9, 10, 27, 23, 40, 56, 68]$
2. 比較 $10$ 與 $27$：$10 \le 27$，不交換 $\rightarrow [9, 10, 27, 23, 40, 56, 68]$

核心觀念

本題評量作業系統中「處理器管理」（Processor Management）的核心機制——CPU 排程（CPU Scheduling）。 在多元程式規劃（Multiprogramming）與分時系統（Time-sharing System）環境下，多個行程（Process）會同時處於就緒狀態，作業系統必須透過 CPU 排程器（CPU Scheduler，又稱短期排程器 Short-term Scheduler）決定由哪一個行程獲得 CPU 執行權。

答題應掌握以下評估指標與核心概念：

1. 排程準則（Scheduling Criteria）：

• CPU 使用率（CPU Utilization）：使 CPU 保持忙碌的時間比例，追求最大化。
• 產能／吞吐量（Throughput）：單位時間內所完成的行程總數，追求最大化。
• 周轉時間（Turnaround Time）：從行程提交（Submission）到完全執行結束（Completion）所經歷的總時間，追求最小化。
• 等待時間（Waiting Time）：行程在就緒佇列（Ready Queue）中等待獲得 CPU 的時間總和，追求最小化。
• 回應時間（Response Time）：從發出請求到系統產生「第一次反應」所經歷的時間，追求最小化。

2. 搶占性分類：

• 不可搶占（Non-preemptive）：行程一旦獲得 CPU，即持續執行直到自行結束或因 I/O 等待而釋放 CPU。
• 可搶占（Preemptive）：系統可依中斷、時間配額或優先權等條件，強制剝奪正在執行之行程的 CPU 控制權。

---

解題方法

本題為標準的觀念申論題，版面應採「兩段式階層結構」呈現：

1. 第一部分：說明 CPU 排程的目的： 切入點不可僅泛稱「分配工作」，必須點出「多元程式規劃下資源最大化利用」之根本目標，並具體列舉作業系統所追求的效能指標（CPU 使用率、吞吐量、周轉時間、等待時間、回應時間與系統公平性）。
2. 第二部分：分項闡述四種排程方式： 每個演算法皆應以一致的架構解析：

• 核心原理（排序與選取規則）
• 搶占特性（Preemptive / Non-preemptive）
• 主要優點
• 潛在缺點與衍生問題（如護衛效應、飢餓現象、時間配額設定）

---

解題技巧

1. 關鍵術語必備：評分委員重點在檢視專業術語。說明 FCFS 時務必寫出「護衛效應（Convoy Effect）」；說明 SJF 與 Priority 時務必提及「飢餓現象（Starvation）」及解決之道「老化（Aging）機制」；說明 RR 時務必討論「時間配額（Time Quantum）」與「內文交換（Context Switch）成本」的權衡。
2. 搶占性標註：每提到一種演算法，第一眼就要標示其為 Preemptive 還是 Non-preemptive，這是考卷版面上展現專業度的關鍵。
3. 對比強化：SJF 在理論上保證「最小平均等待時間」，但實務上難以精確預知下一個 CPU 叢發時間（CPU Burst Time），此限制不可遺漏。

---

【答案】

一、CPU 排程演算法的目的

CPU 排程的主要目的，是在多元程式規劃（Multiprogramming）環境中，透過短期排程器（Short-term Scheduler）自就緒佇列（Ready Queue）中挑選適當的行程並指派 CPU 執行，以達成系統資源的最佳化配置與工作效率的最大化。具體目標包含以下六項準則：

1. 提高 CPU 使用率（CPU Utilization）：減少 CPU 閒置時間，使其保持忙碌狀態（理想目標通常為 40% 至 90%）。
2. 增加系統吞吐量（Throughput）：使單位時間內完成執行的行程數量達到最大。
3. 縮短周轉時間（Turnaround Time）：將行程從提交至系統到完全執行完畢所消耗的總時間降至最低。
4. 減少等待時間（Waiting Time）：使行程停留在就緒佇列中等待被配置 CPU 的累積時間最短。
5. 加速回應時間（Response Time）：對於交談式或互動式系統，使行程從提交請求到產生第一個輸出回應的時間降至最低。
6. 兼顧系統公平性（Fairness）：避免任何行程遭遇無限期延遲執行（即防止飢餓現象）。

---

二、四種常見 CPU 排程方式之詳細解釋