114 公務人員升官等薦任 統計 資料處理 考古題詳解

核心觀念

本題考查功能相依、屬性閉包、候選鍵，以及第二、第三正規化（2NF、3NF）的分解。

• 若 $X\rightarrow Y$，表示在關係中，只要兩筆資料的 $X$ 值相同，其 $Y$ 值也必須相同。
• 屬性集合 $X$ 的閉包 $X^+$，是由已知功能相依性可推得、由 $X$ 決定的所有屬性。
• 若 $X^+$ 包含關係的全部屬性，則 $X$ 是超鍵；若 $X$ 的任何真子集都不是超鍵，則 $X$ 是候選鍵。
• 部分相依是非主屬性依賴於複合候選鍵的真子集；2NF 要求消除部分相依。
• 傳遞相依是非主屬性依賴於鍵以外的決定因素；3NF 要求每個非平凡功能相依 $X\rightarrow Y$ 至少符合下列一項：$X$ 是超鍵，或 $Y$ 中每個屬性都是主屬性（屬於某候選鍵）。

本題沒有法條適用。

解題方法

先找出必須進入每個候選鍵的屬性，再計算閉包；接著依候選鍵檢查部分相依，完成 2NF 分解；最後將各關係中的傳遞相依拆開，使每個關係符合 3NF。

（一）決定主鍵

觀察功能相依右側的屬性，可得：

• $D$ 沒有出現在任何功能相依右側，因此無法由其他屬性推得，任何候選鍵都必須包含 $D$。
• $E$ 也沒有出現在任何功能相依右側，因此任何候選鍵都必須包含 $E$。

計算 $DE$ 的閉包：

由 $E\rightarrow A$，加入 $A$；再由 $A\rightarrow B,C$，加入 $B,C$；由 $B\rightarrow C,F,H$，加入 $F,H$；由 $F\rightarrow E,G$，加入 $G$。因此：

$DE$ 能決定全部屬性，且 $D$、$E$ 各自都不能單獨決定全部屬性，因此 $DE$ 是候選鍵。又因任何候選鍵都必須包含 $D$、$E$，而 $DE$ 已是超鍵，所以它是唯一候選鍵。

（二）分解至第二正規化

唯一候選鍵是複合鍵 $DE$，故主屬性為 $D,E$，非主屬性為 $A,B,C,F,G,H$。

檢查候選鍵的真子集：

• $E\rightarrow A$，而 $E\subset DE$，故非主屬性 $A$ 部分相依於候選鍵。
• $D$ 沒有決定其他屬性的功能相依。

將 $E\rightarrow A$ 所涉及的屬性獨立成一個關係，並保留原關係中其餘屬性：

核心觀念

本題考查區域網路中常見設備的功能分工，重點在於辨認各設備主要處理的層次與工作：

• **交換器（Switch）**主要在區域網路內轉送資料，依據目的端的 MAC 位址決定轉送埠。
• **路由器（Router）**連接不同的 IP 網路，依據目的 IP 位址與路由表選擇封包的傳送路徑。
• IP 分享器通常整合路由器、網路位址轉換（NAT）、DHCP 與無線基地台等功能，讓多部裝置共用一個對外網路連線。
• **防火牆（Firewall）**依據安全規則檢查並控制網路流量，以允許合法連線、阻擋未授權或不符合規則的流量。

解題方法

以「主要判斷依據」區分四種設備最清楚：Switch 看 MAC 位址、Router 看 IP 位址與路由表、IP 分享器負責 多裝置共用對外連線、Firewall 負責 依安全規則過濾流量。作答時依序說明每種設備的用途與典型功能，即可完整回答。

各設備主要功能

一、路由器（Router）

路由器連接兩個或多個不同的 IP 網路，收到 IP 封包後，依封包的目的 IP 位址查詢路由表，選擇適當的下一個傳送方向，將封包轉送至目的網路。家用或機關網路中的路由器，通常負責區域網路與外部網路（如網際網路）之間的連接。

二、IP 分享器

IP 分享器常用於家庭或小型辦公室，讓多部電腦、手機等裝置透過同一個對外連線上網。常見功能包括：

• 透過 NAT，將內部網路的私有 IP 位址轉換為對外使用的 IP 位址。
• 透過 DHCP，自動分配內部裝置的 IP 位址及相關網路設定。

核心觀念

本題比較兩種常見的比較式排序法：合併排序（Merge Sort）與快速排序（Quick Sort）。比較時要分清楚三件事：

1. 時間複雜度：演算法執行所需時間如何隨資料筆數 $n$ 增長。
2. 額外空間複雜度：除原始資料外，排序時另需多少記憶體。
3. 排序特性與適用情境：是否穩定、能否處理大於主記憶體的資料，以及資料結構對實作的影響。

解題方法

依題目指定的五個面向逐項比較，並說明常見實作下的複雜度。複雜度分析以陣列為主要例子；Quick Sort 的空間複雜度另計遞迴堆疊，不把原地分割所用的少量變數算入主要額外空間。

核心觀念

矩陣相乘的維度規則是：若 $X$ 為 $r\times s$ 矩陣、$Y$ 為 $s\times t$ 矩陣，則 $XY$ 有定義，結果為 $r\times t$ 矩陣，其元素為

題目中 $A$ 為 $l\times m$、$B$ 為 $m\times n$、$C$ 為 $m\times p$。先算 $AB$，其維度為 $l\times n$；但要接著計算 $(AB)C$，$AB$ 的欄數 $n$ 必須等於 $C$ 的列數 $m$，因此須滿足 $n=m$。若先算 $BC$，則 $B$ 的欄數 $n$ 必須等於 $C$ 的列數 $m$，同樣須滿足 $n=m$。

解題方法

本題未明示 $n=m$，因此三個矩陣依題示維度一般不能直接相乘。以下以矩陣乘積有定義為前提，即 $n=m$，採用由左至右計算的方式：

1. 先計算 $E=AB$。$E$ 為 $l\times n$ 矩陣，且

2. 再計算 $D=EC$。因 $n=m$，$E$ 的欄數與 $C$ 的列數相同，結果 $D$ 為 $l\times p$ 矩陣，且

近似程式語言如下：