109 地方特考四等 資訊處理 資料處理概要 考古題詳解

核心觀念

1. 生成樹（Spanning Tree）的定義 對於一個具有 $n$ 個頂點的連通無向圖形 $G=(V, E)$，其生成樹為包含圖中所有 $n$ 個頂點、且邊數恰好為 $n-1$ 條的無迴圈（Acyclic）連通子圖。
2. 最小生成樹（Minimum Spanning Tree, MST） 在有權重的連通圖中，所有可能的生成樹中，各邊權重總和（$\sum \text{weight}$）最小的生成樹稱為最小生成樹。
3. 求解演算法（貪婪法，Greedy Algorithm）

• Kruskal 演算法（邊導向）：將圖形中所有邊按權重由小到大排序，依序挑選權重最小的邊；若該邊的加入不會造成迴圈則納入，若會造成迴圈則捨棄，直到選滿 $n-1$ 條邊為止。
• Prim 演算法（頂點導向）：由任意起始頂點出發，每次挑選與目前已生成子樹相鄰、且權重最小的邊擴展，逐步加入新頂點，直到所有頂點皆被涵蓋。

---

解題方法

本題給定頂點集合 $V=\{A, B, C, D, E, F\}$，頂點數 $|V| = 6$。因此，最小生成樹必須恰好包含 $6 - 1 = 5$ 條邊，且涵蓋所有 6 個頂點。

本題邊集合資訊完整，採用國考作答最直觀且易於條理化呈現的 Kruskal 演算法 進行求解。

步驟一：邊的權重遞增排序

將圖形 $G$ 中的 7 條邊依權重由小到大排列：

1. $\{A, B\}$，權重：$2$
2. $\{C, D\}$，權重：$4$
3. $\{C, E\}$，權重：$5$
4. $\{A, C\}$，權重：$6$
5. $\{B, D\}$，權重：$7$
6. $\{E, F\}$，權重：$9$
7. $\{D, F\}$，權重：$10$

步驟二：依序挑選邊並檢驗迴圈

• 第 1 步：考慮邊 $\{A, B\}$（權重 2）

• 檢驗：目前無任何邊，不形成迴圈。

• 處置：選入。

• 目前邊集合：$\{\{A, B\}\}$（已選 1 條邊）。

• 第 2 步：考慮邊 $\{C, D\}$（權重 4）

• 檢驗：連接頂點 $C$ 與 $D$，不形成迴圈。

• 處置：選入。

• 目前邊集合：$\{\{A, B\}, \{C, D\}\}$（已選 2 條邊）。

• 第 3 步：考慮邊 $\{C, E\}$（權重 5）

• 檢驗：連接頂點 $E$ 至子圖 $\{C, D\}$，不形成迴圈。

• 處置：選入。

• 目前邊集合：$\{\{A, B\}, \{C, D\}, \{C, E\}\}$（已選 3 條邊）。

• 第 4 步：考慮邊 $\{A, C\}$（權重 6）

• 檢驗：連接子圖 $\{A, B\}$ 與子圖 $\{C, D, E\}$，不形成迴圈。

• 處置：選入。

• 目前邊集合：$\{\{A, B\}, \{C, D\}, \{C, E\}, \{A, C\}\}$（已選 4 條邊）。

• 第 5 步：考慮邊 $\{B, D\}$（權重 7）

• 檢驗：頂點 $B$ 與 $D$ 經由已選入的邊 $B-A-C-D$ 已經相連。若加入邊 $\{B, D\}$，將形成迴圈（Cycle: $A-B-D-C-A$）。

• 處置：捨棄（不選入）。

• 目前邊集合維持 4 條邊。

• 第 6 步：考慮邊 $\{E, F\}$（權重 9）

• 檢驗：連接孤立頂點 $F$ 至子圖 $\{A, B, C, D, E\}$，不形成迴圈。

核心觀念

本題測驗關聯式資料庫結構化查詢語言（SQL）的基礎查詢與分組彙總功能，核心在於掌握以下語法要素：

1. 聚合函數（Aggregate Functions）：

• AVG(欄位名)：計算指定數值欄位的算術平均值。
• COUNT(*) 或 COUNT(欄位名)：統計符合條件的資料列（筆數）。

2. 分組子句（GROUP BY）：

• 當題目出現「各……」、「每……」（如「各部門」）的需求時，必須依該分類欄位將資料列分組後再進行彙總運算。
• 規則：出現在 SELECT 清單中的非聚合欄位，必須列於 GROUP BY 子句中。

3. 資料篩選子句（WHERE）：

• 用於在「資料分組與聚合運算之前」，先過濾出符合特定條件的個別資料列（如篩選性別為男性）。

---

解題方法

第一問：查詢各部門的員工平均薪資

1. 確定資料來源：資料表為「員工」（FROM 員工）。
2. 確定分組依據：依部門別分類，使用 GROUP BY 部門別。
3. 確定運算與輸出欄位：

• 輸出分組欄位「部門別」。
• 使用聚合函數 AVG(薪資) 計算各部門員工的薪資平均值，可加上別名（如 平均薪資）以提升可讀性。

4. 組合成 SQL 語句：

SELECT 部門別, AVG(薪資) AS 平均薪資
FROM 員工
GROUP BY 部門別;

第二問：查詢各部門的男性員工人數

1. 前置篩選條件：需先剔除非男性員工，故在分組前下達 WHERE 性別 = '男'。
2. 確定分組依據：依部門別分組，使用 GROUP BY 部門別。
3. 確定運算與輸出欄位：

• 輸出分組欄位「部門別」。

核心觀念

本題測驗關聯式資料庫（Relational Database）的 SQL 多資料表結合查詢（Multi-table Join Query） 與 條件篩選（Selection），核心考點包含：

1. 多對多（$M:N$）關聯架構與中介資料表：

• 「員工」與「專案」為多對多關係（一名員工可參與多個專案，一個專案可由多名員工組成）。
• 「專案管理」為兩者之間的關聯實體（Associative Entity / Junction Table），以複合主鍵（Composite Primary Key，即 專案編號 與 員工編號）串接「員工」與「專案」，並儲存關係屬性「工作角色」。

2. 內部結合（INNER JOIN）與結合條件數量法則：

• 若要從 $N$ 個資料表中整合資料，在 WHERE 或 ON 子句中至少需要 $N - 1$ 個結合條件（Join Conditions），否則會產生無效的笛卡兒乘積（Cartesian Product / Cross Join）。
• 本題涉及 3 個資料表，故必須具備至少 $3 - 1 = 2$ 個結合條件。

3. 欄位名稱歧異性（Column Ambiguity）處理：

• 當多個資料表具有相同名稱的欄位（如「專案編號」存在於專案與專案管理；「員工編號」存在於員工與專案管理），在 SELECT 投影子句及結合條件中，必須使用「資料表名稱.欄位名稱」或「資料表別名.欄位名稱」進行明確限定，避免引發語法歧異錯誤。

---

解題方法

解題切入點採標準 SQL 結構化拆解法，依序確定輸出欄位、來源表格、關聯路徑與篩選準則：

1. 確定輸出欄位（SELECT 子句）：

• 題目指定輸出：專案編號、員工編號、姓名、專長、工作角色。
• 由於「專案編號」與「員工編號」重疊，明確指定來源（例如取自「專案管理」或對應的主表）： 專案管理.專案編號, 專案管理.員工編號, 姓名, 專長, 工作角色。

2. 確定資料來源與串接路徑（FROM 與結合子句）：

• 查詢條件「專案類別」在「專案」表。
• 輸出欄位「姓名」、「專長」在「員工」表。
• 輸出欄位「工作角色」在「專案管理」表。
• 因此必須同時結合「員工」、「專案」、「專案管理」三張資料表：
• 路徑一（專案 與 專案管理）：透過 專案.專案編號 = 專案管理.專案編號 關聯。
• 路徑二（員工 與 專案管理）：透過 員工.員工編號 = 專案管理.員工編號 關聯。

3. 設定資料篩選條件（WHERE 子句）：

• 專案類別限制為「大數據分析」：專案類別 = '大數據分析'（文字型別需加上單引號 '）。

---

選項分析

本題為國家考試之申論問答題（非選擇題），無選項分析。在國考閱卷標準中，本題主要採計以下四個給分要點：

核心觀念

1. 二元樹（Binary Tree）架構： 二元樹為有限節點的集合，每個節點至多擁有兩個子節點（分別稱為「左子節點」與「右子節點」）。依公職考試慣例，當題目以未指定方向的無向邊集合給定樹狀圖、且未特別註明左右時，同一個父節點連接的兩個子節點，預設依英文字母順序排列，字母在前者為「左子節點」，在後者為「右子節點」。
2. 中序拜訪（In-order Traversal）： 走訪規則為「左子樹 $\to$ 樹根節點 $\to$ 右子樹」（簡記為 L-V-R），採遞迴定義：

• 先以中序拜訪拜訪左子樹。
• 拜訪當前節點（樹根）。
• 再以中序拜訪拜訪右子樹。

---

解題方法

步驟一：依題目條件繪製二元樹

題目給定頂點集合 $V=\{A,B,C,D,E,F,G,H,I\}$，以 $A$ 為樹根，各邊連接關係推導如下：

1. 樹根為 $A$，相鄰節點為 $\{A,B\}$ 與 $\{A,C\}$：

• 字母順序 $B < C$，故 $B$ 為 $A$ 的左子節點，$C$ 為 $A$ 的右子節點。

2. 節點 $B$ 相鄰節點為 $\{B,D\}$ 與 $\{B,E\}$：

• 字母順序 $D < E$，故 $D$ 為 $B$ 的左子節點，$E$ 為 $B$ 的右子節點。

3. 節點 $E$ 相鄰節點為 $\{E,F\}$ 與 $\{E,G\}$：

• 字母順序 $F < G$，故 $F$ 為 $E$ 的左子節點，$G$ 為 $E$ 的右子節點。

4. 節點 $G$ 相鄰節點為 $\{G,H\}$ 與 $\{G,I\}$：

• 字母順序 $H < I$，故 $H$ 為 $G$ 的左子節點，$I$ 為 $G$ 的右子節點。

二元樹結構圖如下：

 A
 / \
 B C
 / \
 D E
 / \
 F G
 / \
 H I

步驟二：執行中序拜訪（L-V-R）

採由下而上的遞迴推導方式：