110 地方特考四等 統計 資料處理概要 考古題詳解

核心觀念

本題考查作業系統中「死結（deadlock）」的必要條件，亦稱為 Coffman 四項條件。死結是指一組程序彼此等待對方所持有的資源，導致所有程序都無法繼續執行。

資料處理程序產生死結，必須同時具備下列四項條件：

1. 互斥（Mutual Exclusion）
2. 持有並等待（Hold and Wait）
3. 不可剝奪（No Preemption）
4. 循環等待（Circular Wait）

這四項是死結發生的必要條件；缺少其中任何一項，即可避免形成死結。

解題方法

判斷死結時，應逐項檢查資源與程序之間的關係：

一、互斥

至少有一項資源在同一時間只能由一個程序使用，不能同時分配給多個程序。

例如：

• 印表機
• 唯一的資料庫鎖
• 某一不可共享的記憶體區段

若所有資源都能被多個程序同時共享，就不會因資源獨占而形成死結。

二、持有並等待

某一程序已經持有至少一項資源，同時又等待取得其他資源。

例如程序 $P_1$ 已持有資源 $R_1$，但還需要資源 $R_2$ 才能繼續執行。此時 $P_1$ 不釋放 $R_1$，並持續等待 $R_2$。

若程序在申請新資源前，必須先釋放已持有的全部資源，就可破壞此條件。

三、不可剝奪

程序已取得的資源不能被系統強制收回，只能由持有該資源的程序自行使用完畢後釋放。

例如某程序正在使用印表機時，系統不能直接將印表機強制收回並交給另一程序使用。

若系統可以強制剝奪資源，就能中斷等待鏈，避免死結形成。

四、循環等待

存在一個程序與資源的封閉等待鏈：

$$P_1 \rightarrow R_2 \rightarrow P_2 \rightarrow R_3 \rightarrow \cdots \rightarrow P_n \rightarrow R_1 \rightarrow P_1$$

以兩個程序為例：

核心觀念

本題考查設計關聯式資料庫時，如何由「分析需求」逐步建立「資料結構」，並透過正規化降低資料重複與維護錯誤。三項技術的功能可分別概括如下：

1. 實體關係模型：分析現實世界中的資料對象及其關聯。
2. 資料庫綱目：將分析結果具體定義為資料庫的整體結構。
3. 資料正規化：檢驗並分解資料表，以減少冗餘及避免異常。

三者的設計流程通常是：

$$\text{需求分析} \rightarrow \text{實體關係模型} \rightarrow \text{資料庫綱目} \rightarrow \text{正規化檢驗與修正}$$

---

一、實體關係模型（Entity-Relationship Model）

1. 定義與功能

實體關係模型是一種資料庫概念設計工具，用來描述系統中的：

• 實體（Entity）
• 屬性（Attribute）
• 實體間的關係（Relationship）
• 實體的基數與參與限制

它著重於「資料在現實世界中代表什麼」，尚未涉及特定資料庫管理系統的實際儲存方式。

2. 實體

實體是現實世界中可以被辨識、描述及區分的對象，例如：

• 考生
• 科目
• 考試
• 成績
• 機關

例如在考試資料庫中，可以將「考生」視為一個實體，其唯一識別值可能是考生編號。

3. 屬性

屬性是用來描述實體特徵的資料項目。例如「考生」實體可具有：

• 考生編號
• 姓名
• 出生日期
• 報考類科

其中，能唯一辨識一筆實體資料的屬性稱為候選鍵；選定作為主要識別用途者稱為主鍵（Primary Key）。

4. 關係

關係表示不同實體間的業務關聯。例如：

• 考生「報考」考試
• 考生「取得」成績
• 科目「屬於」考試

關係通常必須說明基數，常見類型包括：

• 一對一（1:1）：一位員工對應一個員工識別證。
• 一對多（1:N）：一個系所包含多位學生。
• 多對多（M:N）：一位考生可報考多個科目，一個科目也有多位考生。

多對多關係在轉換成關聯式資料庫時，通常需要建立中介資料表。例如：

$$\text{考生}(\text{考生編號}, \text{姓名})$$ $$\text{科目}(\text{科目編號}, \text{科目名稱})$$ $$\text{報考}(\text{考生編號}, \text{科目編號}, \text{成績})$$

「報考」表即為連結考生與科目的關聯表。

5. 實體關係模型的主要作用

實體關係模型具有下列功能：

• 協助分析使用者需求。
• 清楚辨識資料項目及其相互關係。
• 決定主鍵、外鍵及關係基數。
• 以圖形化方式與使用者溝通。
• 作為後續建立資料表及資料庫綱目的基礎。
• 在實際建置前發現資料結構上的缺漏或矛盾。

---

二、資料庫綱目（Database Schema）

1. 定義

資料庫綱目是資料庫的整體邏輯結構與定義，說明資料庫中有哪些資料表、各表包含哪些欄位、欄位的資料型態、鍵值及表格間的關聯。

資料庫綱目描述的是「資料庫如何被組織」，而資料庫實例（Database Instance）則是某一時間點實際儲存的資料內容。

例如：

$$\text{學生}(\text{學號}, \text{姓名}, \text{系所編號})$$ $$\text{系所}(\text{系所編號}, \text{系所名稱})$$

此處的資料表名稱、欄位、主鍵與外鍵定義，均屬於資料庫綱目的一部分。

2. 綱目所包含的內容

資料庫綱目通常包括：

• 資料表名稱。
• 欄位名稱及意義。
• 欄位資料型態與長度。
• 主鍵（Primary Key）。
• 外鍵（Foreign Key）。
• 唯一性限制。
• 不可為空值限制。
• 預設值。
• 實體完整性限制。
• 參照完整性限制。
• 表格之間的關聯。
• 視觀表、索引及其他資料庫物件的定義。

3. 主鍵與外鍵

主鍵的功能是唯一識別資料表中的每一筆紀錄，必須具備唯一性，且通常不得為空值。

外鍵則是某一資料表中的欄位，用來參照另一資料表的主鍵。例如：

$$\text{學生}(\underline{\text{學號}}, \text{姓名}, \text{系所編號})$$ $$\text{系所}(\underline{\text{系所編號}}, \text{系所名稱})$$

「學生」表中的系所編號是外鍵，參照「系所」表的主鍵。如此可避免學生資料指向不存在的系所。

4. 資料庫綱目的主要作用

資料庫綱目的功能包括：

• 將概念模型轉換為可實作的關聯式結構。
• 規範資料表與欄位的組織方式。
• 定義資料間的完整性與一致性。
• 提供資料庫管理系統建立資料表的依據。
• 協助程式設計、查詢、維護與權限管理。
• 形成應用程式與資料庫之間共同遵循的資料結構規格。

資料庫綱目屬於資料庫的結構定義，資料內容的新增、修改與刪除不會改變綱目本身。

---

三、資料正規化（Data Normalization）

1. 定義與目的

資料正規化是依據函數相依關係，將資料分解成結構良好的資料表，以降低資料冗餘、避免資料不一致，並減少資料更新時所產生的異常。

正規化主要解決三類問題：

• 插入異常（Insertion Anomaly）：無法單獨新增某項資料，必須同時附帶其他不必要資料。
• 更新異常（Update Anomaly）：同一資料重複儲存，更新時只修改部分紀錄，造成不一致。
• 刪除異常（Deletion Anomaly）：刪除某筆資料時，連帶刪除原本仍需保留的其他資訊。

2. 函數相依

若屬性 $B$ 的值由屬性 $A$ 唯一決定，則稱為：

核心觀念

本題考查二維陣列的位址計算。假設陣列中：

• 同一列向右移動一個欄位，位址增加 $c$
• 向下移動一個列，位址增加 $r$

因此，二維陣列位址可表示為：

$$\operatorname{Addr}(i,j)=\operatorname{Addr}(1,1)+(i-1)r+(j-1)c$$

其中 $r$、$c$ 分別代表列間距與欄間距。

解題方法

由已知位址建立兩個差分方程。

由 $a(2,3)$ 移至 $a(3,2)$：

• 列數增加 $1$，位址增加 $r$
• 欄數減少 $1$，位址減少 $c$

因此：

$$76-56=r-c$$ $$r-c=20 \tag{1}$$

由 $a(3,2)$ 移至 $a(4,5)$：

• 列數增加 $1$，位址增加 $r$
• 欄數增加 $3$，位址增加 $3c$

因此：

$$112-76=r+3c$$ $$r+3c=36 \tag{2}$$

聯立 $(1)$、$(2)$：

$$\begin{aligned} r-c&=20\\ r+3c&=36 \end{aligned}$$

兩式相減：

核心觀念

本題考查三種基本資料結構的：

1. 資料儲存方式。
2. 資料新增、刪除與存取的操作特性。
3. 資料進出順序及其限制。

三者比較如下：

資料結構	主要進出原則	常見特性
堆疊 Stack	後進先出 LIFO	僅能在同一端進行新增與刪除
佇列 Queue	先進先出 FIFO	一端新增，另一端刪除
鏈結串列 Linked List	依節點連結順序存取	節點以指標連結，新增與刪除彈性較高

---

解題方法

作答時可從「儲存方式、操作端點、資料進出順序、存取效率」四個面向說明。每一種資料結構均應先定義其組織方式，再說明可採行的基本操作及其特性。

---

一、堆疊 Stack

（一）資料儲存方式

堆疊是一種線性資料結構，資料依序排列，並在同一端進行所有主要操作。進行操作的一端稱為堆疊頂端（Top），另一端通常稱為堆疊底端（Bottom）。

堆疊可以使用陣列或鏈結串列實作：

• 使用陣列實作時，以變數 top 記錄目前堆疊頂端的位置。
• 使用鏈結串列實作時，通常以指標指向最上方的節點，該節點即為堆疊頂端。

堆疊遵守「後進先出」（Last In, First Out, LIFO）原則，即最後放入的資料最先取出。

例如依序放入 $A、B、C$：

$$A \rightarrow B \rightarrow C$$

取出順序為：

$$C \rightarrow B \rightarrow A$$

（二）基本操作

1. Push：推入

將新資料加入堆疊頂端。

若使用陣列表示，通常先將 top 往上移動，再將資料存入該位置。

2. Pop：彈出

移除並取得堆疊頂端的資料。若堆疊內容為 $A、B、C$，第一次 Pop 會取得 $C$。

3. Peek 或 Top：查看頂端

只查看堆疊頂端資料，不將資料移除。

4. 判斷是否為空

若堆疊沒有任何元素，即為空堆疊（Stack Underflow 的前置判斷）。

5. 判斷是否已滿

使用固定大小陣列實作時，若堆疊容量已用盡，再執行 Push 會發生溢位（Stack Overflow）。

（三）操作特性

• 新增與刪除均在堆疊頂端進行。
• 不能直接取出中間資料而不影響堆疊順序。
• Push、Pop、Peek 通常可在 $O(1)$ 時間內完成。
• 適合處理函式呼叫、遞迴、括號配對、運算式轉換、深度優先搜尋及復原操作等問題。

---

二、佇列 Queue

（一）資料儲存方式

佇列也是線性資料結構，但資料在一端加入、另一端移除。加入資料的一端稱為佇列尾端（Rear 或 Tail），移除資料的一端稱為佇列前端（Front 或 Head）。

佇列可使用陣列或鏈結串列實作：

• 使用陣列實作時，通常以 front 記錄佇列前端，以 rear 記錄佇列尾端。
• 使用鏈結串列實作時，通常維護 front 與 rear 兩個指標，分別指向第一個節點與最後一個節點。

佇列遵守「先進先出」（First In, First Out, FIFO）原則，即最早加入的資料最先被移除。

例如依序加入 $A、B、C$：

$$A \rightarrow B \rightarrow C$$

取出順序為：

$$A \rightarrow B \rightarrow C$$

（二）基本操作

1. Enqueue：加入

將新資料加入佇列尾端。

2. Dequeue：移除

移除並取得佇列前端的資料。

3. Front 或 Peek：查看前端

查看最早加入、即將被移除的資料，但不刪除該資料。

4. 判斷是否為空

佇列中沒有任何元素時，不能執行有效的 Dequeue。

5. 判斷是否已滿

使用固定大小陣列實作時，容量用盡即無法再 Enqueue。

（三）循環佇列

若使用一般陣列實作佇列，資料移除後，前端位置可能留下空間。若每次都將其餘資料往前搬移，會增加處理時間。因此常採用循環佇列（Circular Queue），使陣列尾端連接回陣列開端。

循環佇列常以模運算更新位置：

$$\text{下一個位置}=(\text{目前位置}+1)\bmod n$$

其中 $n$ 為陣列容量，可避免因索引到達陣列末端而無法使用前端空間。

（四）操作特性

• Enqueue 在佇列尾端進行。
• Dequeue 在佇列前端進行。
• 若以適當的 front、rear 指標或循環佇列實作，Enqueue 與 Dequeue 通常均為 $O(1)$。
• 不宜直接從中間插入或刪除資料。
• 適合處理排隊服務、工作排程、列印工作、廣度優先搜尋及訊息緩衝等問題。

---

三、鏈結串列 Linked List

（一）資料儲存方式

鏈結串列由許多節點（Node）組成。每個節點通常包含兩部分：

1. 資料欄位（Data）：儲存實際資料。
2. 連結欄位（Link 或 Pointer）：儲存下一個節點的位址。

單向鏈結串列的節點可表示為：

核心觀念

本題考查哈夫曼編碼（Huffman coding）。其基本原則如下：

1. 將所有指令依出現機率由小到大排列。
2. 每次取出機率最小的兩個節點合併。
3. 合併後的節點，其機率為兩者機率之和，並重新放回排序序列。
4. 重複上述步驟，直到形成一棵完整二元樹。
5. 題目指定左子樹編碼為 $0$，右子樹編碼為 $1$，由根節點往下讀取即可得到各指令編碼。

哈夫曼編碼的特性是：出現機率越高的指令，通常具有越短的編碼；且任何一個指令的編碼都不是另一個指令編碼的前綴，因此可以唯一解碼。

本題機率中有相同數值，故採用標準約定：相同機率時依合併順序排列，並令較小機率的節點置於左子樹。

解題方法

原始機率如下：

指令	A	B	C	D	E	F	G
機率	0.25	0.20	0.15	0.13	0.12	0.10	0.05

先依機率由小到大排列：

$$G(0.05),\ F(0.10),\ E(0.12),\ D(0.13),\ C(0.15),\ B(0.20),\ A(0.25)$$

第 1 次合併

取最小的 $G$ 與 $F$：

$$G(0.05)+F(0.10)=0.15$$

形成節點 $GF(0.15)$。

第 2 次合併

取 $E$ 與 $D$：

$$E(0.12)+D(0.13)=0.25$$

形成節點 $ED(0.25)$。

第 3 次合併

目前最小的兩個節點為 $C(0.15)$ 與 $GF(0.15)$：

$$C(0.15)+GF(0.15)=0.30$$

形成節點 $C\!-\!GF(0.30)$。

第 4 次合併

取 $B(0.20)$ 與 $ED(0.25)$：

$$B(0.20)+ED(0.25)=0.45$$

形成節點 $B\!-\!ED(0.45)$。

第 5 次合併

取 $A(0.25)$ 與 $C\!-\!GF(0.30)$：

核心觀念

本題考查關聯式資料庫的 SQL 基本操作：

• SELECT：指定要顯示的欄位。
• FROM：指定資料來源表格。
• WHERE：設定篩選條件。
• JOIN：依共同欄位連結不同表格。
• GROUP BY：依某些欄位分組。
• AVG：計算平均值。
• SUM：計算合計值。

三個表格的關聯如下：

• 客戶.客戶編號 = 訂單.客戶編號
• 產品.產品編號 = 訂單.產品編號

本題為申論及填寫 SQL 題，沒有選擇題選項，因此無選項分析。

---

（一）列出地址在臺北市的客戶姓名與電話

解題方法

資料只需使用「客戶」表格。以 WHERE 篩選地址包含「臺北市」的紀錄，再以 SELECT 顯示姓名與電話。

SELECT 姓名, 電話
FROM 客戶
WHERE 地址 LIKE '%臺北市%';

LIKE '%臺北市%' 表示地址文字中只要包含「臺北市」即可，例如「臺北市中正區」或「臺北市信義區」。

若資料庫地址欄位的內容固定為「臺北市」而非完整地址，也可寫成：

SELECT 姓名, 電話
FROM 客戶
WHERE 地址 = '臺北市';

解題技巧與陷阱

• 欄位名稱放在 SELECT，篩選條件放在 WHERE。
• 地址通常是完整文字，因此使用 LIKE 搭配萬用字元較符合實際資料。
• % 代表任意長度的文字。

---

（二）列出各個產品名稱及其平均購買數量

核心觀念

平均購買數量的計算公式為：

$$\text{平均購買數量} = \frac{\text{購買數量總和}}{\text{購買紀錄筆數}}$$

產品名稱在「產品」表格，購買數量在「訂單」表格，因此必須透過產品編號進行連結，並依產品分組後使用 AVG。

標準解法

SELECT P.產品名稱, AVG(O.購買數量) AS 平均購買數量
FROM 產品 AS P
JOIN 訂單 AS O
 ON P.產品編號 = O.產品編號
GROUP BY P.產品編號, P.產品名稱;

解題推導

1. 從「產品」表格取得產品名稱。
2. 從「訂單」表格取得購買數量。
3. 以產品編號連結兩表。
4. 依產品分組。
5. 對每一組的購買數量套用 AVG。

例如某產品有三筆訂單，購買數量分別為 $2、5、8$，則：

$$\text{平均購買數量} = \frac{2+5+8}{3} = 5$$

若要求列出沒有訂單的產品

若題意中的「各個產品」包含尚未被購買的產品，可使用左外部連接：

SELECT P.產品名稱, AVG(O.購買數量) AS 平均購買數量
FROM 產品 AS P
LEFT JOIN 訂單 AS O
 ON P.產品編號 = O.產品編號
GROUP BY P.產品編號, P.產品名稱;