109 年 國立政治大學圖書資訊與檔案學研究所圖書資訊學組《計算機概論》

本題為名詞解釋題，主要測試考生對計算機科學領域基本概念的理解。

(1) 卷積神經網路 (Convolutional Neural Network, CNN)：
CNN 是一種深度學習模型，特別擅長處理具有網格狀拓撲結構的資料，例如圖像。其核心特徵是使用卷積層 (convolutional layer) 來自動且自適應地學習空間層次的特徵。卷積層通過應用濾波器 (filter) 或卷積核 (kernel) 到輸入資料上，提取局部特徵。CNN 通常還包含池化層 (pooling layer) 用來降低維度、以及全連接層 (fully connected layer) 用來進行分類或回歸。
【答案】CNN 是一種深度學習模型，主要用於圖像識別、物件偵測等任務，其特點是通過卷積層、池化層等結構自動提取空間層次的特徵。

(2) 後門程式 (Back Door)：
後門程式是一種惡意軟體或程式碼，它繞過了正常的安全認證機制，允許未經授權的使用者遠端存取、控制或傳輸資料。後門可以是在軟體開發過程中故意植入的，也可以是透過其他惡意軟體（如病毒、木馬）植入的。其目的是提供一種隱藏的、可隨時訪問的通道。
【答案】後門程式是一種繞過正常安全驗證機制的程式，允許未經授權者進行遠端存取、控制或傳輸資料。

(3) 數位人文研究平台 (Digital Humanities Research Platform)：

本題主要考察資料庫正規化的基本概念與應用。

(1) 資料庫正規化 (Database Normalization) 的目的：
正規化是資料庫設計中的一個重要過程，旨在減少資料冗餘 (data redundancy) 和提高資料的獨立性 (data independence)。透過正規化，可以避免資料的插入、更新和刪除異常 (anomalies)。具體來說，正規化有助於：

• 消除資料冗餘： 避免重複儲存相同資訊，節省儲存空間。
• 避免資料異常：
  • 插入異常 (Insertion Anomaly)： 當我們想新增一筆資料時，卻因為某些欄位尚未產生值而無法新增。例如，若課程資訊與學生成績綁在一起，想新增一門新課程但還沒有學生選修時，就無法將課程資訊加入。
  • 更新異常 (Update Anomaly)： 當需要更新某筆資料時，必須在多個地方進行更新，如果遺漏了其中一個，就會導致資料不一致。例如，若同一門課的學分數在多個學生的紀錄中出現，更新學分數時必須修改所有相關紀錄。
  • 刪除異常 (Deletion Anomaly)： 當刪除一筆資料時，可能意外地刪除了其他有用的資訊。例如，若一個學生的所有課程紀錄都被刪除，而課程資訊只儲存在與學生成績相關的欄位中，那麼這門課程的資訊也可能隨之消失。
• 使資料結構更清晰、易於維護。
• 提高資料的一致性 (Consistency)。

【答案】資料庫正規化是為了減少資料冗餘、避免資料異常（插入、更新、刪除異常），並提高資料的一致性與結構清晰度。

(2) 功能相依性 (Functional Dependency, FD) 的種類：
正規化的核心是分析欄位之間的函數依賴關係。

• 直接相依 (Direct Dependency / Full Functional Dependency)： 設有一個關係模式 R，其屬性集合為 U。若 X ⊆ U, Y ⊆ U 且 X ∩ Y = ∅，則稱 Y 對 X 直接相依 (或稱 完全函數相依 Full Functional Dependency)，記為 $X \rightarrow Y$，表示 X 的每一個值唯一確定 Y 的一個值，且 X 是 Y 的一個超鍵 (Super Key) 的最小鍵。在正規化中，我們特別關注非主屬性 (non-prime attributes) 對候選鍵 (candidate key) 的完全函數相依。
• 傳遞相依 (Transitive Dependency)： 設有一個關係模式 R，其屬性集合為 U。若有三個屬性集合 X, Y, Z ⊆ U，且 X, Y, Z 兩兩不相交，則稱 Z 對 X 存在傳遞相依，如果滿足以下兩個條件：
  1. $X \rightarrow Y$ (Y 函數相依於 X)
  2. $Y \rightarrow Z$ (Z 函數相依於 Y)
  3. Y 不是 X 的超鍵 (Y is not a superkey of X)，且 Y 不是 Z 的超集 (Y is not a superset of Z)。
     簡單來說，如果一個非主屬性 Z 不僅依賴於主鍵 X，還依賴於另一個非主屬性 Y，而 Y 又依賴於主鍵 X，那麼 Z 就傳遞相依於 X。傳遞相依是造成 3NF 違反的關鍵。

【答案】直接相依是指一個屬性集合 Y 完全依賴於另一個屬性集合 X，且 X 是 Y 的最小超鍵。傳遞相依是指一個非主屬性 Z 依賴於主鍵 X，但 Z 也依賴於另一個非主屬性 Y，而 Y 又依賴於 X。

(3) 不符合 2NF 的欄位：
給定的資料表結構如下，主鍵為 {學號, 課程名稱}。

學號	姓名	地址	課程名稱	學分數	成績	必選修
40011223	張有明	高雄市###	資料庫管理系統	3	80	必
40011224	劉志明	彰化市###	資料庫管理系統	3	90	必

核心觀念

本題考「單點交配」（one-point crossover）的字串操作：先隨機選出切點，再交換兩個字串切點之後的部分。

題目中的亂數 $k$ 介於 $1$ 到 $5$。以五個字元字串為例，交換位置 $k+1$ 至第 $5$ 個字元；位置 $1$ 至 $k$ 則保留原樣。當 $k=5$ 時，切點之後沒有字元，因此兩個子代與原親代相同。

解題方法

設親代字串為 $P_1$、$P_2$，子代為 $C_1$、$C_2$。切點為 $k$ 時，子代前 $k$ 個字元分別取自原親代，剩餘字元則互相交換：

$$C_1=P_1[1:k]+P_2[k+1:5]$$ $$C_2=P_2[1:k]+P_1[k+1:5]$$

以下用 Python 的切片實作。Python 索引從 $0$ 開始，[:k] 取前 $k$ 個字元，[k:] 取從第 $k+1$ 個字元起的部分。

核心觀念

本題考查二元搜尋樹（binary search tree, BST）的定義、建立方式、陣列表示法，以及三種樹走訪順序。

二元搜尋樹的基本特性如下：

1. 每個節點最多有兩個子節點，分別稱為左子樹與右子樹。
2. 對任一節點而言，左子樹中所有節點的鍵值均小於該節點鍵值。
3. 右子樹中所有節點的鍵值均大於該節點鍵值。
4. 左、右子樹本身也必須分別是二元搜尋樹。
5. 若鍵值不重複，則對任一節點 $x$：

$$\text{左子樹所有鍵值}<x<\text{右子樹所有鍵值}$$

二元搜尋樹的搜尋、插入與刪除，在樹高為 $h$ 時，其時間複雜度通常為 $O(h)$。若樹接近平衡，$h\approx \log_2 n$；若樹退化成鏈狀，則 $h=n$。

---

解題方法

建立二元搜尋樹時，依照題目給出的資料序列逐一插入：

$$\{5,4,6,2,1,3,8,7,9\}$$

插入規則如下：

• 新值小於目前節點：往左子樹尋找。
• 新值大於目前節點：往右子樹尋找。
• 找到空位置時，將新值放入該位置。

逐一插入

1. 插入 $5$：$5$ 成為根節點。
2. 插入 $4$：$4<5$，放在 $5$ 的左子節點。
3. 插入 $6$：$6>5$，放在 $5$ 的右子節點。
4. 插入 $2$：$2<5$，再比較 $2<4$，放在 $4$ 的左子節點。
5. 插入 $1$：$1<5$、$1<4$、$1<2$，放在 $2$ 的左子節點。
6. 插入 $3$：$3<5$、$3<4$，但 $3>2$，放在 $2$ 的右子節點。
7. 插入 $8$：$8>5$、$8>6$，放在 $6$ 的右子節點。
8. 插入 $7$：$7>5$、$7>6$，但 $7<8$，放在 $8$ 的左子節點。
9. 插入 $9$：$9>5$、$9>6$、$9>8$，放在 $8$ 的右子節點。

因此所建立的二元搜尋樹為：

          5
        /   \
       4     6
      /       \
     2         8
    / \       / \
   1   3     7   9

---

一維陣列儲存方式

可使用「完全二元樹索引法」將二元樹儲存在一維陣列中。採用陣列索引從 $1$ 開始時：

• 根節點儲存於 $A[1]$
• 若節點位於 $A[i]$：
  • 左子節點位於 $A[2i]$
  • 右子節點位於 $A[2i+1]$
• 父節點位於：

$$A\left[\left\lfloor \frac{i}{2}\right\rfloor\right]$$

依照上述規則配置：

陣列位置	儲存內容
$A[1]$	$5$
$A[2]$	$4$
$A[3]$	$6$
$A[4]$	$2$
$A[5]$	空
$A[6]$	空
$A[7]$	$8$
$A[8]$	$1$
$A[9]$	空
$A[14]$	$7$
$A[15]$	$9$

因此可表示為：

$$A[1..15] = [5,4,6,2,\varnothing,\varnothing,8,1,\varnothing,\varnothing,\varnothing,\varnothing,\varnothing,7,9]$$

其中 $\varnothing$ 表示該位置沒有節點。

位置推導如下：

• $5$ 在 $A[1]$
• $4$ 是 $5$ 的左子節點，在 $A[2]$
• $6$ 是 $5$ 的右子節點，在 $A[3]$
• $2$ 是 $4$ 的左子節點，在 $A[4]$
• $8$ 是 $6$ 的右子節點，在 $A[7]$
• $1$ 是 $2$ 的左子節點，在 $A[8]$
• $7$ 是 $8$ 的左子節點，在 $A[14]$
• $9$ 是 $8$ 的右子節點，在 $A[15]$

儲存方式的特性