112 專技高考高等考試 資訊技師 資料結構與資料庫及資料探勘 考古題詳解

核心觀念

本題考查中序式轉換為後序式（Postfix）與前序式（Prefix），關鍵是依運算子的優先次序決定運算結構，再依結合性處理同一優先層級的運算子。

優先次序由高至低為：

其中 $\hat{}$ 為右結合，因此 $p\hat{}q\hat{}r$ 解析為 $p\hat{}(q\hat{}r)$；其他二元運算子皆為左結合。

解題方法

先依優先次序與括號，將原式分層：

括號內先算 $6*z$；乘除優先於加減；$\hat{}$ 優先於乘法，且連續的 $\hat{}$ 由右向左結合。因此整體結構為：

（一）後序式

後序式的規則是：先列出左運算元，再列出右運算元，最後列出運算子。

各子式依序轉換：

• $(6*z)$：6 z *
• $y/(6*z)$：y 6 z * /
• $x-y/(6*z)$：x y 6 z * / -
• $(q\hat{}r)$：q r ^
• $p\hat{}(q\hat{}r)$：p q r ^ ^
• $8*(p\hat{}(q\hat{}r))$：8 p q r ^ ^ *

最後將兩個加法運算元合併：

核心觀念

Kruskal 演算法依邊的權重由小到大檢查，每次選取一條不會形成環的邊；若加入後會形成環，就略過。直到選出 $|V|-1$ 條邊為止，即得到最小生成樹。

本圖有 $7$ 個頂點，因此 MST 必須包含 $7-1=6$ 條邊。

解題方法與逐步過程

先將所有邊依權重遞增排列，再依序判斷是否形成環：

核心觀念

本題考查 SQL 外部連接（Outer Join）及排序：

• LEFT JOIN 保留左表的所有資料列；右表找不到符合的資料時，右表欄位為 NULL。
• RIGHT JOIN 保留右表的所有資料列；左表找不到符合的資料時，左表欄位為 NULL。
• ON 子句指定兩表的連接條件；ORDER BY 指定結果排序。ASC 為遞增，DESC 為遞減。
• 題目要求欄位名稱前附表格名稱，且禁止使用別名，因此欄位須寫成 Employees.FirstName 等完整形式。

解題方法

先依題目指定的 JOIN 類型，從兩表中選出需要的欄位，再以共同鍵值建立連接條件。Orders.EmployeeID 對應 Employees.EmployeeID；Orders.ShipperID 對應 Shippers.ShipperID。最後依指定欄位排序。

（一）列出訂單編號及員工名字

以 Orders 為左表、Employees 為右表，透過員工編號連接。由於使用 LEFT JOIN，每筆 Orders 訂單都會保留；若訂單沒有對應員工，Employees.FirstName 為 NULL。

SELECT Orders.OrderID, Employees.FirstName
FROM Orders
LEFT JOIN Employees
 ON Orders.EmployeeID = Employees.EmployeeID
ORDER BY Employees.FirstName ASC;

（二）列出訂單編號及託運商名稱

核心觀念

分散式資料庫會把資料配置在不同地點的多個節點上。設計時要決定資料如何分布，常用的兩種策略是資料複製（Data Replication）與資料片段化（Data Fragmentation）；實務上通常會搭配使用。

• 資料複製：同一份資料在多個節點保存副本。
• 資料片段化：將資料切分成多個片段，分別配置到不同節點；各片段合起來仍可重建原資料。

解題方法

作答時分別說明兩種策略的資料配置方式、主要優點與代價，再補充兩者如何結合。

一、資料複製（Data Replication）

資料複製是把資料的副本儲存在兩個以上的節點。複製可分為：

• 完全複製：每個節點都保存整個資料庫。
• 部分複製：只將特定資料或片段複製到部分節點。

優點：

1. 提高可用性與可靠度：某節點故障時，其他節點仍可能提供資料。
2. 改善讀取效能：使用者可就近讀取副本，減少遠端存取與網路傳輸。
3. 支援負載分散：多個節點可分擔讀取需求。

代價與設計課題：

1. 增加儲存空間需求：副本愈多，占用的儲存空間愈大。
2. 維持副本一致性：資料更新後，需將變更傳播至相關副本；若更新未同步完成，讀取結果可能不一致。
3. 增加更新成本：涉及多個副本的寫入作業，需要處理更新順序、同步或交易一致性。

因此，資料複製的核心取捨是：以額外的儲存與更新管理成本，換取較高的讀取效率及可用性。

二、資料片段化（Data Fragmentation）

資料片段化是將關係或資料集合分割成較小的片段，再把各片段配置到不同節點。常見方式如下：

1. 水平片段化（Horizontal Fragmentation） 依資料列條件切分，同一關係的各片段具有相同屬性，但包含不同資料列。例如，依地區將客戶資料分成北區與南區片段。各片段可透過聯集重建原關係： $R = R_1 \cup R_2 \cup \cdots \cup R_n$

核心觀念

K-means 是一種以距離為基礎的分割式群集分析方法。給定 $n$ 個樣本及群集數 $K$，演算法將樣本分成 $K$ 群，並以各群的質心代表該群。質心是群內樣本各維度的算術平均。

演算法的目標是最小化群內平方誤差（within-cluster sum of squared errors，SSE）：

其中 $C_j$ 是第 $j$ 群，$\mu_j$ 是該群質心。K-means 透過反覆執行「分派樣本」與「更新質心」來降低 SSE，直到分群結果收斂。

解題方法

依題目給定的資料集 $D$ 與群集數 $K$，演算法步驟如下：

1. 初始化質心：從 $D$ 中選取 $K$ 個樣本作為初始質心 $\mu_1,\ldots,\mu_K$。
2. 分派樣本：計算每個樣本 $x_i$ 與各質心的距離，將 $x_i$ 分派到距離最近的質心所屬群集：

3. 更新質心：對每個群集，重新計算其樣本平均：