109 年 國立成功大學數據科學研究所《計算機概論》

核心觀念

本題涵蓋資料結構、圖論、Python、分類模型、資料庫、JSON、網路協定與資料轉換。判斷是非題時，應先對照正式定義、公式與反例；只要能提出一個反例，即可否定全稱敘述。

(1) Complete binary tree 與 full binary tree

核心觀念

• Complete binary tree（完整二元樹）：除最後一層外，其餘各層皆填滿；最後一層的節點由左至右排列。
• Full binary tree（滿二元樹）：每個節點不是沒有子節點，就是恰好有兩個子節點。

高度為 $h$ 時，二元樹的最大節點數為：

完整二元樹與滿二元樹都可能達到此最大值。

解題方法

題目問的是「能不能有更多節點」，並非「最大節點數是否不同」。

例如高度為 $3$：

• 一棵高度為 $3$ 的 full binary tree 可以只有 $7$ 個節點。
• 一棵高度為 $3$ 的 complete binary tree 可以有 $8$ 個節點。

因此，確實存在 complete binary tree 的節點數多於 full binary tree 的情況。

解題技巧

不要把「full」誤認為「節點數一定最多」。Full binary tree 只限制每個節點的子節點數量，不保證各層填滿。

【答案】

True。

(2) 陣列與 linked list 的開頭插入

核心觀念

若陣列目前為：

在 $A[0]$ 插入新元素時，原有元素必須全部向右移動：

因此時間複雜度為：

Linked list 若已經持有 head pointer，只需：

1. 建立新節點；
2. 將新節點指向原本的 head；
3. 更新 head。

時間複雜度為：

解題技巧

比較插入成本時，要注意插入位置：

• 陣列開頭插入：$O(n)$
• 陣列尾端插入：平均可為 $O(1)$
• Linked list 開頭插入：$O(1)$
• Linked list 中間插入：若已知節點位置，為 $O(1)$；若要先搜尋位置，需 $O(n)$

【答案】

True。

(3) 所有邊權重加上常數是否會改變 MST

核心觀念

假設圖中有 $n$ 個頂點。任何 spanning tree 都恰好包含：

條邊。

若每條邊的權重都加上常數 $c$，則任一 spanning tree $T$ 的新權重為：

整理得：

所有 spanning tree 都增加相同的 $c(n-1)$，因此它們之間的相對大小不變。

解題技巧

MST 只在乎不同 spanning tree 的總權重排序。若所有 spanning tree 增加相同數值，最小者仍然是原本的最小者。

「Assume unique weights」更表示原本的 MST 唯一，加常數後仍不會改變。

【答案】

False。

將所有邊權重加上同一常數，不會改變 minimum spanning tree 的邊集合。

(4) Python map 與 range

核心觀念

程式碼為：

print(list(map(lambda x: x+1, range(0,10,2))))

range(0,10,2) 產生：

0, 2, 4, 6, 8

函式：

lambda x: x+1

會將每個元素加 $1$：

因此輸出為：

[1, 3, 5, 7, 9]

時間複雜度為：

額外空間複雜度為：

因為 list() 會建立包含 $n$ 個元素的新串列。

解題技巧

range(start, stop, step) 不包含 stop，因此 range(0,10,2) 不會包含 $10$。

【答案】

False。

正確輸出為：

[1, 3, 5, 7, 9]

(5) Confusion matrix 的 precision

核心觀念

題目矩陣如下：

因此：

• True Positive（TP）$=8$
• False Positive（FP）$=3$
• False Negative（FN）$=12$
• True Negative（TN）$=11$

Precision 定義為：

代入數值：

$\frac{8}{20}$ 是將 TP 除以某個不正確的總數，並非 precision。

解題技巧

Precision 關心的是「被模型預測為 True 的資料中，有多少真的為 True」，所以分母只看預測為 True 的兩格：

不要把 FN、TN 放入 precision 的分母。

【答案】

False。

正確 precision 為：

(6) Database 中的 identifier

核心觀念

Identifier 是用來唯一識別資料列的欄位或欄位組合。資料庫中常見的 identifier 包括：

• Primary key
• Candidate key
• Unique key
• 由多個欄位組成的複合鍵

其中 primary key 的主要條件是：

1. 每一列的值必須唯一；
2. 不可為 NULL。

解題技巧

「唯一辨識每一列」正是 key 或 identifier 的核心用途。題目沒有要求 identifier 必須是單一欄位，因此複合鍵也符合。

【答案】

True。

(7) 五個 attributes 的可能 primary keys 數量

核心觀念

五個 attributes 為：

若只從「欄位組合數」計算非空子集合，可能的組合數為：

也可以逐項計算：

例如：

• 單欄位鍵：$A,B,C,D,E$，共 $5$ 個；
• 雙欄位鍵：共 $\binom52=10$ 個；
• 三欄位鍵：共 $\binom53=10$ 個；
• 四欄位鍵：共 $5$ 個；
• 五欄位鍵：共 $1$ 個。

重要限制

嚴格而言，某個欄位組合是否真的能成為 primary key，仍取決於資料內容是否滿足唯一性與最小性。題目若問「可能的欄位組合數」，採用上述 $2^5-1$ 計算。

解題技巧

$10$ 只是：

代表恰好選兩個 attributes 的組合數，不是所有可能的 primary key 組合數。

【答案】

False。

若計算所有非空欄位組合，數量為：

(8) JSON 格式

核心觀念

JSON 的物件格式為：

{
  "key": "value"
}

JSON 的陣列格式為：

[
  "value1",
  "value2"
]

題目給出的格式為：

[id:'1', name:'dol']

有兩個問題：

1. [] 表示陣列，但內容卻使用 id、name 這種鍵值結構；
2. JSON 的字串必須使用雙引號 " "，不能使用單引號 ' '。

正確的 JSON 物件應為：

{"id": "1", "name": "dol"}

若要表示「包含一個物件的陣列」，應寫成：

[
  {
    "id": "1",
    "name": "dol"
  }
]

解題技巧

JSON 快速檢查規則：

• 物件使用 {};
• 陣列使用 [];
• 鍵與字串值使用雙引號；
• 鍵值之間使用冒號 :;
• 多個項目之間使用逗號。

【答案】

False。

(9) 網路服務是否都使用 TCP

核心觀念

本題主要考察對作業系統中「死鎖 (Deadlock)」概念的理解，包括死鎖的產生條件、解除方法、預防方法以及在實際生活中的體現。

核心觀念： 死鎖的定義、四個必要條件（互斥、佔有並等待、不可剝奪、循環等待）、解除死鎖的方法（資源剝奪、進程回退、進程終止）、預防死鎖的方法（破壞四個必要條件之一）以及實際應用場景。

子題詳解：

(a) 解除現有死鎖的方法與預防死鎖的方法

• 解除現有死鎖 (Breaking an Existing Deadlock):
  當系統已經發生死鎖時，需要採取措施來打破這種僵局。常見的方法包括：

  1. 資源剝奪 (Resource Preemption): 從一個或多個進程中強行剝奪其佔有的資源，並將這些資源分配給其他被阻塞的進程。這可能會導致進程的部分工作丟失，需要進行檢查點或回退。
  2. 進程回退 (Process Rollback): 將一個或多個進程回退到一個較早的檢查點（checkpoint），釋放該進程在回退點之後佔有的所有資源。然後，系統可以將這些資源分配給其他進程。回退的選擇需要仔細考慮，以避免重複發生死鎖。
  3. 進程終止 (Process Termination):
     • 終止一個或多個死鎖進程： 這是最簡單但代價最高的方法。選擇終止哪個進程需要考慮多種因素，如進程的優先級、已執行的進度、已佔用資源的數量、釋放資源後對其他進程的影響等。
     • 終止所有死鎖進程： 這是最極端的做法，通常不推薦。

• 預防死鎖 (Preventing Deadlock):
  預防死鎖的策略是在系統設計階段就採取措施，確保死鎖不會發生。這通常通過破壞死鎖的四個必要條件之一來實現：

  1. 互斥 (Mutual Exclusion) 的破壞： 允許某些資源可以被同時共享，而不是嚴格互斥。但這只適用於少數可共享的資源。
  2. 佔有並等待 (Hold and Wait) 的破壞：
     • 方法一： 要求所有進程在執行前一次性申請所有需要的資源。這樣，進程要么獲得所有資源並執行，要么不獲得任何資源。缺點是可能導致資源利用率低，並且需要知道進程的完整資源需求，這在動態系統中很難實現。
     • 方法二： 允許進程在沒有佔有任何資源的情況下才申請資源。
  3. 不可剝奪 (No Preemption) 的破壞： 如果一個進程請求的資源已經被其他進程佔有，則該進程必須等待。

本題考察對作業系統中幾個核心概念的辨析能力，包括進程與處理器的區別、調度策略、進程行為類型以及進程創建與替換的系統調用。

核心觀念： 作業系統的進程管理、調度機制、資源分配與進程行為分析、系統調用。

子題詳解：

(a) Process vs. Processor

• Process (進程):

  • 定義： 進程是作業系統中執行中的程式的實例。它是一個獨立的執行單元，擁有自己的記憶體空間（程式代碼、數據、堆疊）、系統資源（文件句柄、網路連接等）以及執行狀態（運行、就緒、等待等）。
  • 抽象概念： 進程是作業系統對正在進行的計算活動的一種抽象。
  • 可被調度： 進程是作業系統調度器調度的對象。
  • 數量： 系統中可以同時存在很多進程。

• Processor (處理器/CPU):

  • 定義： 處理器（通常指中央處理器 CPU）是計算機的硬件組件，負責執行指令、進行計算和控制其他硬件。
  • 硬件實體： 處理器是實際執行指令的物理設備。
  • 執行單元： 處理器是執行進程（或線程）指令的實際執行單元。
  • 數量： 一台計算機通常有 1 個或多個 CPU 核心。

• 主要區別：

  • 性質： 進程是軟體的抽象概念，是執行中的程式；處理器是硬體的物理設備，是執行指令的引擎。
  • 關係： 進程運行在處理器上。一個處理器可以在不同時間執行不同的進程，而一個進程也需要在處理器上才能執行。
  • 數量： 系統可以有很多進程，但 CPU 核心的數量是有限的。當進程數量遠大於 CPU 核心數量時，就需要通過時間分片（時分復用）來讓多個進程輪流在 CPU 上運行。

(b) Preemptive vs. Non-preemptive

• Preemptive (搶佔式):

  • 定義： 在搶佔式調度策略中，作業系統可以暫停（剝奪）一個正在 CPU 上運行的進程，將 CPU 分配給另一個具有更高優先級的進程，或者當前進程的時間片用完時。
  • 機制： 通常由定時器中斷觸發，當進程的時間片耗盡或有更高優先級的進程進入就緒狀態時，CPU 會被強制從當前進程轉移到另一個進程。
  • 優點： 能夠更公平地分配 CPU 時間，避免低優先級進程被長期餓死，響應性較好。
  • 缺點： 系統開銷較大（上下文切換頻繁），需要額外的機制來處理共享資源的同步問題（如互斥鎖），否則可能導致數據不一致。
  • 例子： Round Robin (RR), Priority Scheduling (with preemption), Shortest Remaining Time First (SRTF)。

• Non-preemptive (非搶佔式/協定式):

  • 定義： 在非搶佔式調度策略中，一旦一個進程獲得了 CPU，它將一直運行，直到它自己主動釋放 CPU（例如，完成執行、進入等待狀態、或主動讓出 CPU）。
  • 機制： CPU 的所有權不會被作業系統強制剝奪。
  • 優點： 系統開銷較小，上下文切換較少，對共享資源的同步問題相對容易處理。
  • 缺點： 可能導致短小進程被長進程阻塞（ the convoy effect），響應性較差，低優先級進程可能長時間得不到 CPU。
  • 例子： First-Come, First-Served (FCFS), Shortest Job First (SJF, non-preemptive version), Priority Scheduling (non-preemptive version)。

本題考察對兩種基本搜尋演算法——順序搜尋 (Sequential Search) 和二分搜尋 (Binary Search) 的時間複雜度及最壞情況的理解。

核心觀念： 順序搜尋的時間複雜度，二分搜尋的時間複雜度，以及它們在不同搜尋元素下的性能表現。

子題詳解：

給定的列表為：[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O]
這個列表是已排序的（按字母順序）。列表長度 $n=15$。

(a) 順序搜尋 (Sequential Search) 的最壞情況

• 順序搜尋原理： 從列表的第一個元素開始，逐個與目標元素進行比較，直到找到目標元素或遍歷完整個列表。
• 時間複雜度：
  • 最好情況：目標元素是列表的第一個元素。需要 1 次比較。時間複雜度 $O(1)$。
  • 最壞情況：目標元素是列表的最後一個元素，或者目標元素不在列表中。需要 $n$ 次比較。時間複雜度 $O(n)$。
  • 平均情況：假設目標元素在列表中，平均需要 $(1+n)/2$ 次比較。時間複雜度 $O(n)$。
• 最壞情況的元素：
  在順序搜尋中，最壞情況發生在需要進行最多比較的時候。這通常是當目標元素位於列表的末尾時。
  對於列表 [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O]，長度為 15。
  • 如果搜尋元素是 'O' (列表的第 15 個元素)，則需要進行 15 次比較。
  • 如果搜尋的元素不在列表中（例如 'P'），則也需要進行 15 次比較（遍歷整個列表後確定不存在）。
• 答案： 搜尋列表中的最後一個元素，即 'O'。或者搜尋一個不在列表中的元素（例如 'P'）。

(b) 二分搜尋 (Binary Search) 的最壞情況

• 二分搜尋原理： 二分搜尋要求列表必須是已排序的。它通過不斷將搜尋範圍縮小一半來查找目標元素。首先比較中間元素，如果目標元素與中間元素相等，則找到；如果目標元素小於中間元素，則在前半部分繼續搜尋；如果目標元素大於中間元素，則在後半部分繼續搜尋。
• 時間複雜度：
  • 最好情況：目標元素是中間元素。需要 1 次比較。時間複雜度 $O(1)$。
  • 最壞情況：目標元素位於搜尋範圍的最邊緣，或者目標元素不在列表中，需要執行 log$_2(n)$ 次比較。時間複雜度 $O(\log n)$。
  • 平均情況：時間複雜度 $O(\log n)$。
• 最壞情況的元素：
  在二分搜尋中，最壞情況發生在搜尋過程中，每次都將搜尋範圍縮小到最小，直到搜尋範圍只剩一個元素或為空。這通常發生在：

核心觀念

本題考查圖形搜尋中的廣度優先搜尋（BFS）與深度優先搜尋（DFS），以及如何在圖中找到一條由起點 start 通往終點 goal 的路徑。

以鄰接串列表示圖：graph[u] 存放從節點 u 可沿邊到達的鄰居。圖中可能有多條路徑、環路，甚至很長的路徑，因此搜尋時要記錄已造訪節點，避免重複搜尋或陷入環路。

題目沒有提供完整圖形與節點資料，以下假設輸入是有限圖，且程式能取得每個節點的鄰居；若邊有方向，鄰接串列須依照箭頭方向建立。

解題方法

為了回傳完整路徑，而不只是判斷能否抵達，搜尋時為每個新造訪的節點記錄其前驅 parent。抵達 goal 後，從終點沿前驅回溯至起點，再反轉路徑，即可得到答案。

BFS：逐層搜尋

BFS 使用先進先出佇列。先搜尋距離起點一條邊的節點，再搜尋距離兩條邊的節點，依此類推。以下程式在無權重圖中回傳邊數最少的路徑；符合題目需求的任意可行路徑。

from collections import deque

def build_path(parent, start, goal):
    path = []
    node = goal

    while node is not None:
        path.append(node)
        if node == start:
            break
        node = parent[node]

    if path[-1] != start:
        return None

    return list(reversed(path))


def bfs_path(graph, start, goal):
    if start == goal:
        return [start]

    queue = deque([start])
    parent = {start: None}

    while queue:
        node = queue.popleft()

        for neighbor in graph.get(node, []):
            if neighbor in parent:
                continue

            parent[neighbor] = node

            if neighbor == goal:
                return build_path(parent, start, goal)

            queue.append(neighbor)

    return None

DFS：沿路深入搜尋

DFS 使用堆疊，優先沿一條路徑深入；無路可走時再回退，改走尚未搜尋的分支。下列寫法採用迭代堆疊，避免遞迴深度過大。

本題涵蓋了數據科學中的幾個重要概念，包括監督學習中的兩種經典模型（線性迴歸與邏輯迴歸）、機器學習與深度學習的關係、模型正則化以及決策樹的過擬合問題與對策。

核心觀念： 迴歸模型、分類模型、機器學習與深度學習的區別、模型正則化、過擬合的成因與防治。

子題詳解：

(a) 線性迴歸 (Linear Regression) 與邏輯迴歸 (Logistic Regression) 的異同

• 相似點 (One Similarity):

  1. 模型結構： 兩者都基於輸入特徵的線性組合來進行預測。它們都計算一個加權和（特徵乘以對應的係數）加上一個偏差項。
  2. 目標函數： 兩者在優化過程中都試圖最小化某種誤差或損失函數。
  3. 廣義線性模型 (Generalized Linear Models, GLM): 兩者都可以被看作是廣義線性模型的一種。線性迴歸是 GLM 的一個特例，而邏輯迴歸則是另一種常見的 GLM。
  • 選擇一個相似點： 兩者都基於輸入特徵的線性組合。

• 差異點 (Two Differences):

  1. 輸出範圍與應用場景：
     • 線性迴歸： 輸出是一個連續的數值。用於預測連續的目標變數，如房價、溫度、銷售額等。
     • 邏輯迴歸： 輸出是一個介於 0 和 1 之間的概率值，通常用於二元分類問題（預測樣本屬於某類別的概率），也可以擴展到多元分類。
  2. 響應函數 (Link Function) 與預測目標：
     • 線性迴歸： 直接預測目標變數 $Y$ 的期望值 $E[Y]$。響應函數是恆等函數 (identity function)，即 $\eta = X\beta$。
     • 邏輯迴歸： 預測目標變數屬於某類別的概率 $P(Y=1|X)$。它使用一個logit 函數（log-odds）作為響應函數，將線性組合 $\eta = X\beta$ 映射到概率空間：$\log\left(\frac{P(Y=1|X)}{1 - P(Y=1|X)}\right) = X\beta$。這意味著線性組合 $\eta$ 是目標變數的 log-odds。
  3. 損失函數 (Loss Function) / 優化目標：
     • 線性迴歸： 通常最小化均方誤差 (Mean Squared Error, MSE)。
     • 邏輯迴歸： 通常最大化似然函數 (Likelihood Function)，或最小化交叉熵損失 (Cross-Entropy Loss)。

(b) 機器學習 (Machine Learning) 與深度學習 (Deep Learning) 的三點差異

• 特徵提取 (Feature Extraction):
  • 機器學習： 通常需要人工進行特徵工程。數據科學家需要根據對問題的理解，手動設計和提取對模型有效的特徵。這是一個耗時且依賴領域知識的過程。
  • 深度學習： 模型本身能夠自動學習特徵。通過多層神經網絡，每一層能夠學習到不同抽象層次的特徵，從原始數據中自動提取出有用的表示。
• 數據量需求 (Data Requirement):
  • 機器學習： 對於傳統的機器學習演算法，在數據量不是非常巨大時，也能取得不錯的效果。
  • 深度學習： 通常需要大量的數據來訓練模型，尤其是在特徵學習階段。數據量越大，深度學習模型的性能往往越好。
• 模型複雜度與計算資源 (Model Complexity & Computational Resources):
  • 機器學習： 模型相對簡單，訓練和推理所需計算資源較少，可以在普通 CPU 上進行。
  • 深度學習： 模型（神經網絡）結構複雜，層數多，參數量大，訓練過程計算量巨大，通常需要高性能的 GPU 或 TPU 來加速計算。

本題要求根據給定的散點圖，找出兩種能夠完美區分 X 和 O 類別的機器學習模型，並說明理由。

核心觀念： 模型的分類能力，特別是能夠學習複雜決策邊界模型的識別能力。

分析散點圖：

觀察散點圖，其中 X 和 O 兩類數據點的分布呈現出明顯的非線性、非球狀的複雜模式。O 類數據點在圖的右側和中部形成了一些聚集，而 X 類數據點則分布在圖的左側、中部以及一些零散的位置。兩類數據之間存在複雜的交叉和交織，簡單的線性模型（如線性 SVM 或線性迴歸）無法在這裡找到一個直線來區分兩類。

能夠完美建模的模型：

要完美地區分 X 和 O，模型需要能夠學習到這種複雜的、非線性的決策邊界。以下是兩種常見的模型：

模型一：支持向量機 (Support Vector Machine, SVM) 搭配核函數 (Kernel Trick)

• 模型名稱： 支持向量機 (SVM)，特別是使用徑向基函數 (RBF Kernel) 或多項式核函數 (Polynomial Kernel)。
• 理由：
  • SVM 的核心思想是找到一個最大邊界分類器，在特徵空間中尋找一個超平面來分隔不同類別的數據點。
  • 當數據點的分布是非線性可分的時，SVM 可以通過核函數將數據映射到一個更高維度的空間，在這個高維空間中，數據點可能變得線性可分。
  • RBF Kernel ($K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)$) 是一種非常強大的核函數，它可以學習任意複雜的決策邊界，非常適合處理像圖中這樣非線性、非球狀的數據分布。
  • 多項式核函數 (Polynomial Kernel) 也可以學習非線性邊界，但 RBF 通常更靈活。