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

核心觀念

本題考查功能相依、候選鍵、第二正規化（2NF）與第三正規化（3NF），以及以正規化後的資料表進行 SQL 查詢。

• 若 $X\rightarrow Y$，表示任兩筆資料只要 $X$ 相同，$Y$ 就必須相同。
• 超級鍵是能決定資料表全部屬性的屬性組合；候選鍵是最小超級鍵；選定的候選鍵即為主鍵。
• 2NF 要求每個非主屬性完全相依於整個候選鍵，不得只相依於複合鍵的一部分。
• 3NF 要求每個非主屬性不得透過非鍵屬性間接相依於候選鍵。正式判準為：對每個非平凡功能相依 $X\rightarrow A$，$X$ 是超級鍵，或 $A$ 是主屬性。

本題有多值電話：一位學生可有多支學生電話，因此每筆「學生修課」資料還須以學生電話區分。依題目給定的相依性，學生電話不由學號決定。

（一）推導主鍵

先求能決定所有屬性的最小屬性組合。

學號不能省略，因為其他資料並不能決定學生姓名、住址等學生資料；課程編號也不能省略，因為成績由學號與課程編號共同決定。學生電話同樣不能省略，因為同一學生可有多支電話，而題目沒有給定能由其他屬性決定學生電話的功能相依。

令

計算 $K$ 的閉包：

1. 學號決定學生姓名、學生住址、聯絡人姓名、聯絡人電話、指導老師證號。
2. 指導老師證號決定指導老師姓名、研究室、實驗室名稱。
3. 實驗室名稱決定實驗室地點及指導老師證號。
4. 課程編號決定課程名稱、學分。
5. 學號與課程編號決定成績。
6. 聯絡人姓名與聯絡人電話決定聯絡人地址。
7. 學生電話已在 $K$ 中。

因此 $K^+$ 涵蓋題目所列全部屬性，$K$ 是超級鍵。上述三個屬性各自都不能省略，故 $K$ 是候選鍵，並選作主鍵。

（二）分解為符合 2NF 的資料表

候選鍵是複合鍵「學號、學生電話、課程編號」。其中：

• 學生資料及指導老師資料由學號決定。
• 課程名稱及學分由課程編號決定。
• 成績由學號與課程編號共同決定；學生電話不影響成績。

因此將只相依於候選鍵一部分的屬性移出，保留完整相依於複合鍵的資料。可分解為：

1. 學生電話（學號、學生電話）
2. 學生資料（學號、學生姓名、學生住址、聯絡人姓名、聯絡人電話、聯絡人地址、指導老師證號、指導老師姓名、研究室、實驗室名稱、實驗室地點）
3. 課程（課程編號、課程名稱、學分）
4. 修課成績（學號、課程編號、成績）

粗體屬性為主鍵；「學生電話」表以學號與學生電話組成複合主鍵，「修課成績」表以學號與課程編號組成複合主鍵。

此分解消除了部分相依：學生電話只依賴學號，課程資訊只依賴課程編號；成績則依賴學號與課程編號的組合，符合 2NF。

（三）分解為符合 3NF 的資料表

再檢查 2NF 的「學生資料」表，其中有以下傳遞相依：

核心觀念

二維陣列在程式中有「列」與「欄」兩個維度，但記憶體是一段連續的一維空間。儲存順序決定陣列元素如何依序映射到這段空間：

• Row-major（列主序）：同一列的元素連續儲存；先存完第 1 列，再存第 2 列，依此類推。C、C++ 等語言常採此順序。
• Column-major（欄主序）：同一欄的元素連續儲存；先存完第 1 欄，再存第 2 欄，依此類推。Fortran、MATLAB 等常採此順序。

若陣列有 $m$ 列、$n$ 欄，元素以 $A[i][j]$ 表示，且索引從 $0$ 開始：

• Row-major 中，$A[i][j]$ 相對於陣列起點的元素位移為 $i n+j$。
• Column-major 中，位移為 $j m+i$。

解題方法

讀取整個大型二維陣列時，應依照實際儲存順序，讓程式沿著連續記憶體位置逐一讀取。如此能充分利用快取（cache）載入相鄰資料的特性，減少快取未命中，提升讀取效率。

因此：

• Row-major 陣列：外層迴圈走列索引 $i$，內層迴圈走欄索引 $j$，使欄索引變化最快。
• Column-major 陣列：外層迴圈走欄索引 $j$，內層迴圈走列索引 $i$，使列索引變化最快。

程式範例

以下以 C 語言的 Row-major 陣列為例：

核心觀念

本題考查：

• 樹狀 BOM 的父子相依關係。
• 拓撲排序（Topological Sort）：所有前置零組件完成後，才能處理其父零組件。
• 後序走訪（Postorder Traversal）：先處理子節點，再處理父節點。
• 在機器與原物料充足時，不同子樹可同時製作，因此總時間由最長的關鍵路徑決定。

設 BOM 樹共有 $n$ 個節點。樹的邊數為 $n-1$，因此線性演算法的時間複雜度為 $O(n)$。

（一）列印零組件製程順序

解題方法

由於父節點的製程必須等待所有子節點完成，因此列印順序必須滿足：

直接對 BOM 樹進行後序走訪即可。

演算法

Postorder(N):
 for each child C of N:
 Postorder(C)
 print(N)

對根節點 $C_0$ 呼叫：

Postorder(C0)

範例結果

以題目中的 BOM 為例，合法列印順序可為：

其中：

• $C_{21}$、$C_{22}$ 均先於 $C_{12}$。
• $C_{11}$、$C_{12}$、$C_{13}$ 均先於 $C_0$。
• 同一層中彼此沒有相依關係的節點，其先後順序不限。

因此，$C_{11}$、$C_{13}$、$C_{21}$、$C_{22}$ 的相對順序可以依資料結構中的排列順序決定。

複雜度

每個節點拜訪一次，每條樹邊檢查一次，因此：

遞迴堆疊及樹的儲存空間為：

解題技巧

判斷是否應採用後序走訪的關鍵是：

子零組件必須先完成，父零組件才能製作。

因此是「子節點先、父節點後」，不可使用前序走訪，因為前序走訪會先列印父節點。

（二）計算產品 $P$ 的最快生產時間

核心觀念

因為機器及原物料充足，同一節點的各個子零組件可以同時製作，所以父節點必須等待「最晚完成」的子零組件。

設：

• $T_c(N)$：節點 $N$ 本身的製程時間。
• $F(N)$：從開始製作節點 $N$ 的零組件，到完成該零組件所需的最短時間。
• $Children(N)$：節點 $N$ 的所有子節點。

若 $N$ 為葉節點，沒有前置零組件，則：

若 $N$ 有子節點，必須等所有子節點完成，因此：

核心觀念

IEEE 802.11 的 MPDU 訊框標頭包含 **Frame Control（訊框控制）**欄位。它長 2 位元組，分成 11 個子欄位，用來標示訊框類型、傳送狀態、加密與排序等控制資訊。回答時要依序說明各子欄位的用途。

解題方法

按照 Frame Control 欄位的標準排列，逐項列出名稱與功能。前兩項 Protocol Version 與 Type 用來辨識協定版本及訊框類別；其餘欄位則描述子類型、傳送方向、分段、重傳、電源管理、安全性及資料排序等狀態。

11 項目資訊及用途

1. Protocol Version（協定版本）：指出所使用的 IEEE 802.11 協定版本；接收端可據此辨識訊框格式。
2. Type（類型）：指出訊框屬於管理（Management）、控制（Control）或資料（Data）訊框。
3. Subtype（子類型）：進一步指出該類型訊框的具體用途，例如 Beacon、Probe Request、ACK 或一般資料訊框。
4. To DS（傳送至分散式系統）：指出訊框是否送往 Distribution System（DS）。
5. From DS（來自分散式系統）：指出訊框是否由 DS 傳出。To DS 與 From DS 的組合也用於判斷位址欄位及訊框傳送方向。
6. More Fragments（尚有分段）：表示目前訊框是否仍有同一 MSDU 的後續分段；若設為 1，表示後面還有分段。
7. Retry（重傳）：表示此訊框是先前訊框的重傳版本，接收端可用來辨識重複訊框。