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

核心觀念

本題的核心在於「陣列合併（Merging）」與「內部排序（Internal Sorting）」的演算法設計與時間複雜度分析，涉及以下關鍵理論：

1. 比較排序法（Comparison-based Sort）的理論下限： 對於任意未排序的 $K$ 個元素，基於比較的排序演算法在最差及平均情況下的時間複雜度下限為 $\Omega(K \log K)$。常見能達到最優執行時間（$O(K \log K)$）的演算法包含合併排序法（Merge Sort）與堆積排序法（Heap Sort）。
2. 已排序序列的雙指標合併法（Two-pointer Merge）： 若兩數列已分別由小到大排序，可利用雙指標進行線性掃描比對，在 $O(m+n)$ 的最佳線性時間內完成合併。
3. 時間複雜度表示法（Big-$O$ Notation）： 以輸入規模 $m$ 與 $n$ 同步評估運算步數。

解題方法

本題題幹未明確註記輸入陣列 $M$ 與 $N$ 是否「已事先由小到大排序」；在歷屆公職考試命題中，此類題目常有兩種命題意圖。為求解答嚴謹周全，以下依兩種情境分別給出最佳演算法設計與複雜度推導：

（一）演算法設計 $\mathrm{Sort}(M,N,P,m,n)$

情境一：$M$ 與 $N$ 為任意數列（未預先排序，一般情況）

若 $M$ 與 $N$ 初始狀態未排序，最佳策略為：將 $M$ 與 $N$ 依序複製至長度為 $m+n$ 的陣列 $P$ 中，接著對陣列 $P$ 執行最佳比較排序演算法（此處採用時間複雜度穩定且最差情況仍為 $O(K \log K)$ 的合併排序法 $\mathrm{MergeSort}$）。

演算法虛擬碼（Pseudocode）：

Algorithm Sort(M, N, P, m, n)
Input: 
 M: 大小為 m 的數列陣列（索引 1 至 m）
 N: 大小為 n 的數列陣列（索引 1 至 n）
 m, n: 陣列 M 與 N 的元素個數
Output: 
 P: 大小為 m + n 的已由小到大排序陣列（索引 1 至 m + n）

1. // 步驟一：將 M 與 N 的元素複製到新陣列 P
2. for i <- 1 to m do
3. P[i] <- M[i]
4. for j <- 1 to n do
5. P[m + j] <- N[j]

6. // 步驟二：對陣列 P 進行合併排序
7. MergeSort(P, 1, m + n)
end Sort

Algorithm MergeSort(A, left, right)
1. if left < right then
2. mid <- floor((left + right) / 2)
3. MergeSort(A, left, mid)
4. MergeSort(A, mid + 1, right)
5. Merge(A, left, mid, right)
end MergeSort

情境二：$M$ 與 $N$ 各自已依由小到大排序（特例情況／經典合併程序）

若命題者將「合併兩已排序陣列」簡稱為「$\mathrm{Sort}$」，則無須重新排序，直接採用雙指標比對法（Two-pointer Merge）即可在線性時間內完成，此時執行時間最優。

演算法虛擬碼（Pseudocode）：

核心觀念

本題評量資料結構中「堆疊（Stack）」之核心應用——後置運算式（Postfix Expression / 逆波蘭表示法 RPN）之求值演算法與程式追蹤（Tracing）能力。

1. 後置運算式特性： 運算子（Operator）位於其對應的運算元（Operand）之後。其最大優勢在於不需括號與運算子優先權比較，只要由左至右掃描即可完成求值。
2. 堆疊（Stack）的 LIFO（後進先出）特性：

• 遇運算元（數值）：直接推入（Push）堆疊暫存。
• 遇雙元運算子：自堆疊連續彈出（Pop）兩個數值進行計算，並將計算結果推回（Push）堆疊中。

3. 左右運算元的順序性（關鍵重點）： 因堆疊為後進先出，當彈出兩個運算元時：

• 第一個彈出者為右運算元（Right Operand，設為 $op_2$）。
• 第二個彈出者為左運算元（Left Operand，設為 $op_1$）。
• 運算時必須以 $op_1 \text{ [運算子] } op_2$ 計算，此順序對非交換律的運算（減法「$-$」、除法「$/$」）至關重要。

解題方法

（一）演算法設計

依題意，題目已規範以下內建副程式：

• EMPTY(PFExp)：判斷字串是否已空。
• First_Char(PFExp)：取出並移除字串首字元。
• DECV(C)：將字元數字轉為對應整數。
• PUSHStack(Stack, V)：將數值置入堆疊頂端。
• POPStack(Stack)：彈出堆疊頂端數值。

演算法虛擬碼（Pseudocode）：

int postfix_math(string PFExp) {
 Stack S; // 宣告並初始化堆疊 S
 char token; // 存放當前讀取的字元
 int op1, op2; // op1 為左運算元，op2 為右運算元
 int result; // 存放單步運算結果

 while (!EMPTY(PFExp)) {
 token = First_Char(PFExp); // 取得並移除 PFExp 第一個字元

 // 若為運算元（0~9之單一位數整數）
 if (token >= '0' && token <= '9') {
 PUSHStack(S, DECV(token));
 } 
 // 若為運算子（+、-、*、/）
 else {
 op2 = POPStack(S); // 先彈出者為右運算元
 op1 = POPStack(S); // 後彈出者為左運算元

 switch (token) {
 case '+':
 result = op1 + op2;
 break;
 case '-':
 result = op1 - op2;
 break;
 case '*':
 result = op1 * op2;
 break;
 case '/':
 result = op1 / op2;
 break;
 }
 PUSHStack(S, result); // 將運算結果推回堆疊
 }
 }

 // 迴圈結束後，堆疊頂端即為最終運算式之解
 return POPStack(S);
}

（二）逐步追蹤執行過程

輸入運算式：$\mathrm{PFExp} = \text{“62/3-42*+”}$。 注意：題意定義 First_Char(PFExp) 會移除最前面的字元，因此每讀取一個字元後，$\mathrm{PFExp}$ 長度即減少 $1$。

核心觀念

本題評量關聯式資料庫理論中「功能相依（Functional Dependency, FD）」與「正規化（Normalization）」的推導能力：

1. 候選鍵（Candidate Key）與主要鍵（Primary Key, PK）：

• 若屬性子集合 $K$ 能決定表格之全體屬性（即屬性閉包 $K^+ = U$），且其任何真子集皆無法決定全體屬性（具備極小性 Minimality），則 $K$ 為候選鍵。
• 若候選鍵只有一組，該候選鍵即為最適之主要鍵。

2. 第一正規化（1NF）：表格中所有屬性之值皆為不可再分割的單一原子值（Atomic value）。題目已給定 $T$ 符合 1NF。
3. 第二正規化（2NF）：

• 符合 1NF。
• 消除部分功能相依（Partial Functional Dependency）：每個「非主屬性（Non-prime attribute）」都必須完全功能相依於候選鍵，不可僅相依於候選鍵的真子集。

4. 第三正規化（3NF）：

• 符合 2NF。
• 消除傳遞功能相依（Transitive Functional Dependency）：表格中不可存在非主屬性傳遞相依於候選鍵。換言之，對於表格中每一個非平庸功能相依 $X \rightarrow Y$，$X$ 必須為超鍵（Superkey），或 $Y$ 必須為主屬性。

解題方法與推導過程

（一）決定表格 $T$ 最合適的主要鍵

• 屬性全體集合：$U = \{A, B, C, D, E, F, G, H\}$
• 已知功能相依集合 $F$： $BC \rightarrow GH,\quad AD \rightarrow E,\quad A \rightarrow H,\quad E \rightarrow BCF,\quad G \rightarrow H$

1. 分析屬性出現位置：

• 出現在箭頭右方（被決定者）的屬性集合： $\{G, H\} \cup \{E\} \cup \{H\} \cup \{B, C, F\} \cup \{H\} = \{B, C, E, F, G, H\}$
• 未出現在箭頭右方的屬性集合： $U \setminus \{B, C, E, F, G, H\} = \{A, D\}$
• 由於屬性 $A$ 與 $D$ 從未被任何其他屬性決定，因此任何候選鍵都必須包含屬性組合 $\{A, D\}$。

2. 計算屬性閉包 $\{A, D\}^+$：

• 初始：$\{A, D\}^+ = \{A, D\}$
• 依 $AD \rightarrow E$：加入 $E \implies \{A, D, E\}$
• 依 $E \rightarrow BCF$：加入 $B, C, F \implies \{A, B, C, D, E, F\}$
• 依 $BC \rightarrow GH$：加入 $G, H \implies \{A, B, C, D, E, F, G, H\} = U$
• 由於 $\{A, D\}^+$ 涵蓋全體屬性，故 $\{A, D\}$ 為超鍵（Superkey）。

3. 檢驗極小性（Minimality）：

• 檢查真子集 $\{A\}$ 之閉包：依 $A \rightarrow H$，得 $\{A\}^+ = \{A, H\} \neq U$。
• 檢查真子集 $\{D\}$ 之閉包：$D$ 無法單獨決定其他屬性，得 $\{D\}^+ = \{D\} \neq U$。
• $\{A, D\}$ 之任何真子集皆無法決定全體屬性，故 $\{A, D\}$ 為極小超鍵（即候選鍵）。

4. 判定主要鍵：

• 因所有候選鍵必含 $\{A, D\}$，而 $\{A, D\}$ 本身已為候選鍵，故不存在其他候選鍵。$\{A, D\}$ 為全表唯一的候選鍵，即為最合適的主要鍵。

（二）將 $T$ 轉化成符合第二正規化（2NF）要求的關聯表格

1. 找出違反 2NF 的部分功能相依：

• 主要鍵為 $\{A, D\}$。
• 主屬性（屬於候選鍵之屬性）：$\{A, D\}$。
• 非主屬性：$\{B, C, E, F, G, H\}$。
• 檢視給定之功能相依：$A \rightarrow H$。 決定者 $A$ 為主要鍵 $\{A, D\}$ 的真子集，而被決定者 $H$ 為非主屬性。此即部分功能相依，違反 2NF。

2. 進行 2NF 分解：

• 將造成部分相依的屬性獨立建立新表格：
• 取出屬性 $\{A, H\}$ 建立關聯表格 $T_1(A, H)$，其主要鍵為 $A$。
• 原表格中移除已抽離的非主屬性 $H$，保留主要鍵及其完全功能相依之其餘屬性：
• 建立關聯表格 $T_2(A, B, C, D, E, F, G)$，其主要鍵為 $\{A, D\}$。

3. 檢驗 2NF 符合性：

• 表格 $T_1(\underline{A}, H)$：主要鍵為單一屬性 $A$，不存在主鍵真子集，符合 2NF。

核心觀念

本題考驗程式語言（Programming Languages）中程序呼叫與參數傳遞機制（Parameter Passing Mechanisms）的底層運作原理，以及對形式參數（Formal Parameters）與實際引數（Actual Arguments）位置綁定的細心度：

1. 參數對稱陷阱（Position vs. Identifier Binding）： 副程式定義為 p(int y, int x, int z)，主程式呼叫為 p(x, y, 3)。參數傳遞依「位置」對應而非「變數名稱」：

• 形參 y 對應主程式的變數 x。
• 形參 x 對應主程式的變數 y。
• 形參 z 對應常數值 3。

2. 三大參數傳遞機制之定義：

• 傳值呼叫（Passed by Value）：將實參的數值複製給形參。副程式在獨立的記憶體堆疊（Stack Frame）中運作，內部對參數的任何修改皆為區域操作，不影響主程式的原始變數。
• 傳址呼叫（Passed by Reference）：將實參的記憶體位址傳遞給形參，形參成為實參的「別名（Alias）」。副程式內部對形參的讀寫，直接作用於主程式對應的記憶體空間。若實參為常數（如 3），編譯器會配置臨時匿名空間傳入。
• 傳名呼叫（Passed by Name）：源自 Algol 60 的代換規則（Textual Substitution），其本質為延遲求值（Lazy Evaluation / Thunk）。副程式本體內的形參直接被實參表達式的「文字」取代，每次執行該敘述時，皆在呼叫端的環境中重新求值。

解題方法

在追蹤程式執行前，先建立參數對照關係表：

（一）傳名呼叫（Passed by Name）之推導

將副程式 p 中的形式參數，以主程式傳入的實際引數進行純文字巨集代換：

• 所有 y 替換為 x（代表主程式的變數 x）
• 所有 x 替換為 y（代表主程式的變數 y）
• 所有 z 替換為 3

文字代換後的程式碼展開如下：

y = y + 3; // 對應原式：x = x + z;
3 = y + 1; // 對應原式：z = x + 1;
y = x + 3; // 對應原式：x = y + z;
x = 3; // 對應原式：y = z;

逐步追蹤分析：

1. y = y + 3; $\implies$ 主程式的 $y = 5 + 3 = 8$。
2. 3 = y + 1; $\implies$ 語法／執行錯誤。常數 3 屬於純右值（R-value），不可作為被賦值的左值（L-value）。在 Algol 60 標準規範下，對常數引數指派會產生編譯錯誤或執行時期中斷（Error），無法正常印出結果。
3. 若考題假設「常數不可指派而略過該錯誤行（或常數指派無效）」進行純文字代換：

• 第 3 行 y = x + 3; $\implies y = 2 + 3 = 5$（此時主程式 $x=2$）。
• 第 4 行 x = 3; $\implies$ 主程式 $x = 3$。
• 最終主程式輸出為 $x = 3,\ y = 5$。

（二）傳址呼叫（Passed by Reference）之推導

核心觀念

本題考 Ethernet 交換器（Switch）的自動學習、查表轉送與未知目的位址泛洪：

• 交換器收到框架時，依來源 MAC 位址及進入埠學習並更新 MAC 位址表。
• 再依目的 MAC 位址查表：查得到，就只從對應埠轉送；查不到，就向同一 VLAN 的其他埠泛洪，不送回來源埠。
• 交換器轉送時不改變框架的來源、目的 MAC 位址或上層資料內容。

（一）PC1 傳送資料給 PC3

假設兩台交換器剛啟動、MAC 位址表皆為空，且 PC1 已取得 PC3 的目的 MAC 位址。PC1 的 MAC 位址是 00-13-46-9A-63-74，PC3 的是 00-F1-EE-50-DC-92。

1. Switch 1 收到框架：框架由 fa0/1 進入。Switch 1 學到 00-13-46-9A-63-74 → fa0/1。因為查不到 PC3 的 MAC 位址，便由 fa0/2、fa0/3、fa0/4 泛洪，不送回 fa0/1。
2. Switch 2 收到框架：框架由 fa0/4 進入。Switch 2 學到 00-13-46-9A-63-74 → fa0/4。由於也查不到 PC3 的位置，便由 fa0/1、fa0/2、fa0/3 泛洪，不送回 fa0/4。
3. PC3 收到框架：PC3 確認目的 MAC 位址是自己的，接收資料；其他收到框架副本的主機因目的位址不符而丟棄。

此時已學到的位址表項目如下：

（二）PC5 傳送資料給 PC1

PC5 的 MAC 位址是 00-03-FF-C0-CD-98，目的 PC1 的 MAC 位址是 00-13-46-9A-63-74。PC1 的位置已在前一段傳輸中被兩台交換器學到。

1. Switch 2 收到框架：框架由 fa0/2 進入。Switch 2 學到 00-03-FF-C0-CD-98 → fa0/2。