111 年 國立中央大學資訊管理學系碩士班乙組《計算機概論》

核心觀念

二元搜尋樹（BST）符合以下規則：每個節點的左子樹所有鍵值都小於該節點，右子樹所有鍵值都大於該節點。插入時從根節點開始比較，較小就往左、較大就往右，直到找到空位置。

刪除有兩個子節點的節點時，常見作法是以其中序後繼或中序前驅取代。本題未指定採用哪一種，因此以下採用中序後繼作答。

解題方法

(a) 依序插入整數

依照序列逐一比較並插入：

• $9$ 為根；$3$ 插入 $9$ 左側，$13$ 插入 $9$ 右側。
• $4$ 插入 $3$ 右側；$16$ 插入 $13$ 右側；$19$ 插入 $16$ 右側。
• $1$ 插入 $3$ 左側；$2$ 插入 $1$ 右側；$7$ 插入 $4$ 右側。
• $21$ 插入 $19$ 右側；$23$ 插入 $21$ 右側。
• $14$ 插入 $16$ 左側；$11$ 插入 $13$ 左側；$22$ 插入 $23$ 左側。

因此，插入完成後的二元搜尋樹 $T$ 為：

本題考驗對 Linux 檔案權限、檔案類型以及 chmod 指令的理解。

核心觀念：

• Linux 檔案權限表示法： 通常以 10 個字元表示。
  • 第一個字元：檔案類型 (d:目錄, -:普通檔案, l:符號連結, etc.)。
  • 接下來九個字元：分為三組，每組三個字元，分別代表檔案擁有者 (owner)、所屬群組 (group)、其他使用者 (others) 的讀取 (r)、寫入 (w)、執行 (x) 權限。
• chmod 指令： 用於改變檔案或目錄的權限。
  • 符號模式： u (owner), g (group), o (others), a (all)；+ (add), - (remove), = (set)；r (read), w (write), x (execute)。
  • 數字模式： 使用八進位數字表示權限，其中 r=4, w=2, x=1。將三組權限 (owner, group, others) 的數字相加。例如 755 代表：
    • Owner: 7 (4+2+1) = rwx
    • Group: 5 (4+0+1) = r-x
    • Others: 5 (4+0+1) = r-x

(a) 此檔案所屬群組為？

本題考驗對作業系統中資源分配、銀行家演算法 (Banker's Algorithm) 的理解，特別是死結的偵測。

核心觀念：

• 資源分配矩陣： Allocation 表示每個行程目前佔用的資源數量，Request 表示每個行程目前請求的資源數量，Available 表示系統中尚餘的資源數量。
• 死結 (Deadlock)： 在多個行程競爭資源的系統中，如果每個行程都佔有某個資源，並請求其他行程所佔有的資源，導致沒有行程能繼續執行，就發生了死結。
• 銀行家演算法 (Banker's Algorithm)： 用於避免或偵測死結。其核心思想是檢查系統是否存在一個「安全序列」(safe sequence)，即是否存在一種行程執行順序，使得所有行程都能在有限的時間內完成。如果不存在安全序列，則系統可能處於死結狀態，或者存在死結的風險。

(a) 每種硬體資源分別有多少實體 (instance)?

系統中總的資源數量等於已分配的資源數量加上目前可用的資源數量。
對於每一種資源（A, B, C, D），總實體數 = 該資源的已分配總數 + 該資源的可用總數。

• 資源 A：

  • 已分配總數 = P1(1) + P2(1) + P3(1) + P4(1) + P5(1) = 5
  • 可用總數 = 1 (來自 Available 列)
  • 總實體數 A = 5 + 1 = 6

• 資源 B：

  • 已分配總數 = P1(0) + P2(1) + P3(1) + P4(1) + P5(1) = 4
  • 可用總數 = 1 (來自 Available 列)
  • 總實體數 B = 4 + 1 = 5

• 資源 C：

  • 已分配總數 = P1(0) + P2(1) + P3(0) + P4(0) + P5(1) = 2
  • 可用總數 = 0 (來自 Available 列)
  • 總實體數 C = 2 + 0 = 2

• 資源 D：

  • 已分配總數 = P1(1) + P2(1) + P3(1) + P4(0) + P5(1) = 4
  • 可用總數 = 1 (來自 Available 列)
  • 總實體數 D = 4 + 1 = 5

【答案】資源 A: 6, 資源 B: 5, 資源 C: 2, 資源 D: 5

(b) 請問此系統目前是否存在死結 (deadlock)? 如有死結，是哪幾個行程所造成？

我們使用銀行家演算法來判斷是否存在死結。
首先，我們需要知道每個行程的最大需求量 (Max)。題目中只給了 Allocation 和 Request。在死結偵測中，我們通常假設 Request 是行程當前還需要的資源，而不是最大需求。如果系統能夠滿足所有行程的 Request，則不會發生死結。如果無法滿足，則需要進一步分析。

死結偵測的步驟：

1. 初始化 Work 向量等於 Available 向量。
2. 找一個尚未完成的行程 Pi，使得 Request_i <= Work。
3. 如果找到這樣的行程，則假設 Pi 完成，並將 Pi 所佔有的資源加到 Work 中：Work = Work + Allocation_i。標記 Pi 為已完成。
4. 重複步驟 2 和 3，直到所有行程都標記為已完成。
5. 如果在某一步驟中，找不到任何滿足 Request_i <= Work 的行程，且還有未完成的行程，則系統處於死結狀態。處於死結狀態的行程就是那些無法被找到並完成的行程。

初始狀態：

• Available (Work) = [1, 1, 0, 1]
• Allocation (已分配)：
  • P1: [1, 0, 0, 1]
  • P2: [1, 1, 1, 1]
  • P3: [1, 1, 0, 1]
  • P4: [1, 1, 0, 0]
  • P5: [1, 1, 1, 1]
• Request (請求)：
  • P1: [1, 0, 0, 1]
  • P2: [0, 1, 1, 1]
  • P3: [1, 0, 1, 0]
  • P4: [1, 1, 0, 1]
  • P5: [0, 1, 1, 0]

本題考驗對二進位小數轉換為十進位表示法的理解。

核心觀念：
二進位小數的每一位代表的權重是 $2$ 的負次方。從小数点右邊第一位開始，權重依序為 $2^{-1}, 2^{-2}, 2^{-3}, \dots$。

將二進位小數 $0.10101_2$ 轉換為十進位：
$0.10101_2 = 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} + 0 \times 2^{-4} + 1 \times 2^{-5}$

核心觀念
本題測驗學生對關聯式資料庫中 連接（join） 的三種常見類型——等值連接 (equi‑join)、自然連接 (natural join)、外部連接 (outer join)——的概念與差異的掌握程度。須能說明它們在 連接條件、結果欄位、以及是否保留未匹配的資料 上的不同。

(a) 等值連接 (Equi‑join)

等值連接是最基本的二元關係運算，其 連接條件僅使用等號 (=) 比較兩個關係的屬性。例如：

$R \bowtie_{R.A = S.B} S$

• 連接條件：只允許 等號，可針對任意屬性配對。
• 結果欄位：保留兩側所有欄位，若連接屬性名稱不同，結果中會同時出現兩個欄位 (如 R.A、S.B)。
• 保留未匹配資料：不保留。若某筆 R 或 S 沒有符合條件的配對，該筆資料將不會出現在結果中（等同於內部連接的子集）。

為什麼：等值連接是內部連接（inner join）的一種實作方式，透過等號篩選出兩表中「相等」的元組，僅保留配對成功的元組。

(b) 自然連接 (Natural join)

自然連接是等值連接的 語法糖，自動以 所有同名屬性 作為連接條件，且 去除重複的屬性。形式上：

$R \ \text{⋈} \ S$

若 R 與 S 同時擁有屬性 A、B，自然連接等價於：

$R \bowtie_{R.A = S.A \ \land\ R.B = S.B} S$

• 連接條件：自動使用 所有同名屬性 的等號比較。
• 結果欄位：對於同名屬性，只保留 一個（通常是左表的版本），其餘欄位全部保留下來。
• 保留未匹配資料：同等值連接，不保留 未匹配的元組。

為什麼：自然連接減少了手動指定相等條件的繁瑣，同時避免在結果中出現重複欄位，提升可讀性。但若兩表同名屬性過多或名稱相同卻語意不同，使用自然連接容易產生誤解。

(c) 外部連接 (Outer join)

外部連接在 內部連接的基礎上， 保留 未匹配的資料。依保留方向不同，可分為三種：

核心概念
本題測驗的是關於關聯模型 (relational model) 中「資料異常 (anomaly)」的概念。資料異常是因資料冗餘與未正規化的關係模式所導致的三種基本問題：插入異常 (Insertion anomaly)、刪除異常 (Deletion anomaly) 與更新異常 (Update anomaly)。掌握這三種異常以及它們產生的根本原因，是判斷資料庫設計是否符合正規化原則的關鍵。

解題步驟

1. 定義「異常」

   • 在關聯模型中，異常指的是在對資料表執行 插入 (INSERT)、刪除 (DELETE)、或 更新 (UPDATE) 時，因表中出現不必要的資料冗餘而產生的問題。
   • 異常的出現通常是因為關係未達到足夠的正規化程度，使得同一資訊被儲存在多筆記錄中。

2. 說明三種異常的類型與形成原因

   類型	何時發生	為什麼會發生	可能的影響
   插入異常 (Insertion anomaly)	嘗試插入一筆新資料時	若某些屬性必須同時出現在同一筆記錄中，而目前缺少其他屬性值（可能因為尚未產生相關實體），則無法完整插入。	無法新增資料，或必須插入「偽」資料（null、dummy 值），造成資料品質下降。
   刪除異常 (Deletion anomaly)	刪除一筆記錄時	當該筆記錄同時儲存了多個實體的資訊（例如同時存放員工與部門資料），刪除該筆記錄可能導致其他實體資訊也被意外刪除。	重要資訊遺失，需額外備份或重新輸入。

核心概念
本題測試學生對 資料庫分割（partitioning） 的概念與其在系統效能、可維護性、資源管理等層面的正反影響，重點在於能否說明各項優缺點的原因與適用情境。

(a) 資料庫分割的優點

1. 提升查詢效能

   • 分割後的資料表只包含部份資料，查詢時只需要在相關分割上搜尋，I/O 讀取量降低。
   • 若以水平分割（row‑partition）為例，查詢條件包含分割鍵 $k$ 時，可直接定位到唯一的分割，搜尋成本由 $O(N)$ 降至 $O(N/M)$（$M$ 為分割數量）。

2. 改善負載平衡

   • 不同分割可以分佈在不同的磁碟、伺服器或資料中心。寫入/讀取請求可同時在多個節點執行，減少單點瓶頸。
   • 對垂直分割（vertical‑partition）而言，將常用欄位與不常用欄位分開存放，可讓熱點查詢只存取少量欄位，提高快取命中率。

3. 易於資料管理與清除

   • 舊資料可整體刪除或歸檔整個分割，而不必逐筆刪除，作業時間從 $O(N)$ 簡化為 $O(1)$（刪除檔案或資料檔案系統層面的操作）。
   • 例如，每月新增的交易紀錄可放在當月分割，過期資料只需刪除該月份的分割。

4. 支援彈性擴充（scalability）

   • 水平分割 可隨需求新增分割（sharding），使資料庫規模與效能呈線性擴展。
   • 若每個分割的容量上限為 $C$，總容量上限可達 $M \times C$，不受單一資料庫實例限制。

5. 提升容錯與可用性

   • 分割可部署於不同機房或雲端區域，單一分割失效不會影響其他分割的服務，系統可快速切換至備援分割。

6. 符合業務需求的資料隔離

   • 不同客戶或部門的資料可以分割存放，降低資料混用風險，亦方便實作權限控制與合規審核。

(b) 資料庫分割的缺點

1. 增加系統複雜度

   • 必須維護分割鍵的選擇與分割策略（水平、垂直、範圍、哈希等），不當的分割鍵會導致 資料倾斜（data skew），部分分割過大，效能甚至變差。
   • 查詢跨多個分割時，需要 合併（union） 或 分散式 JOIN，在大量分割下會產生高額的網路傳輸與協調開銷。

2. 管理成本升高

   • 每個分割往往需要獨立的備份、還原、監控與維護腳本，運維負擔成比例上升。
   • 若分割跨不同資料庫系統或雲端服務，還會產生 跨平台相容性 與 版本同步 的問題。

3. 事務一致性挑戰

   • 跨分割的事務需使用 分散式交易（distributed transaction） 或 兩階段提交（2PC），會增加鎖定時間與死鎖風險，並影響吞吐量。
   • 為避免 2PC，常必須將相關資料保證落在同一分割，限制了資料模型的彈性。

4. 資料搬移與重新分割成本

   • 隨著業務成長，原有的分割策略可能失效，需要 重新分割（re‑partition）。這通常需要大量資料搬移，會暫時降低系統效能，且操作複雜。
   • 若使用 範圍分割，新增分割時需調整分割鍵範圍，可能引發資料重疊或缺失。

5. 開發與測試難度

   • 開發人員必須在程式碼層面考慮分割鍵、路由邏輯與分割映射，測試時需模擬多分割環境，測試覆蓋率相對較低。
   • 若未做好抽象層，未來變更分割策略會導致大量程式碼重構。

6. 成本效益不一定顯著

   • 在資料規模不大或查詢模式不需要大量 I/O 時，分割帶來的效能提升可能並不足以抵消額外的硬體、管理與開發成本。
   • 因此，成本-效益分析（Cost‑Benefit核心概念
     本題測試學生對 資料庫分割（partitioning） 的概念與其在系統效能、可維護性、資源管理等層面的正反影響，重點在於能否說明各項優缺點的原因與適用情境。

(a) 資料庫分割的優點

本題考驗對傳輸層兩個重要協定 TCP (Transmission Control Protocol) 和 UDP (User Datagram Protocol) 的特性差異，以及 TCP 中滑動視窗 (Sliding Window) 機制的理解。

核心觀念：

• 傳輸層 (Transport Layer)： 負責在主機之間提供端對端 (end-to-end) 的資料傳輸服務。
• TCP (Transmission Control Protocol)： 提供可靠、有序、面向位元組流的連線導向 (connection-oriented) 傳輸服務。
• UDP (User Datagram Protocol)： 提供簡單、不可靠、無連線 (connectionless) 的資料傳輸服務，以最少的開銷提供盡可能快的傳輸。
• 滑動視窗 (Sliding Window)： 一種用於提高流量控制和可靠傳輸效率的機制。

(a) 請說明 TCP 和 UDP 特性上的不同。(5%)

TCP 和 UDP 是傳輸層的兩種主要協定，它們在服務品質、開銷和應用場景上有顯著差異：

總結：

• TCP 像是打電話，需要先建立連線，保證通話內容清晰、無遺漏、按順序，但相對耗時。
• UDP 像是寄明信片，直接寄出，不保證送達、順序或內容完整，但快速且簡單。

【答案】TCP 是可靠的、面向連線的、保證順序和流量控制的協定；UDP 是不可靠的、無連線的、盡力傳輸的協定，開銷較小。

(b) 請先說明 TCP 上滑動視窗 (sliding window) 的設計目的，然後詳細說明滑動視窗的工作原理。(10%)

TCP 滑動視窗的設計目的：

滑動視窗機制的主要設計目的是為了實現 流量控制 (Flow Control) 和 提高傳輸效率 (Efficiency)。

1. 流量控制： 確保發送端不會以過快的速度發送數據，以免淹沒接收端的緩衝區，導致數據丟失。接收端透過告知發送端它還有多少可用緩衝區空間來實現流量控制。
2. 提高傳輸效率： 在傳統的停止等待 (Stop-and-Wait) 協議中，發送端每發送一個數據包後，必須等待接收端的確認應答 (ACK) 後才能發送下一個數據包。這會導致網路鏈路利用率低下，尤其是在高延遲的鏈路上。滑動視窗允許發送端在收到 ACK 之前發送多個數據包，從而充分利用鏈路帶寬，提高傳輸速度。

滑動視窗的工作原理：

滑動視窗機制涉及發送端和接收端各自維護一個「視窗」。這個視窗代表了在給定時間內，可以發送或接收的數據序列號 (sequence number) 的範圍。

1. 發送端 (Sender) 的滑動視窗：

本題考驗對 SQL Injection 攻擊原理的理解。

核心觀念：

• SQL Injection (SQL 注入)： 一種常見的網頁安全漏洞，攻擊者透過在網頁輸入欄位、URL 參數或其他使用者輸入點，插入惡意的 SQL 查詢語句，來欺騙後端資料庫執行非預期的命令。
• 資料庫查詢原理： 應用程式通常會動態建構 SQL 查詢語句，將使用者輸入的值拼接到 SQL 字串中，然後執行。

SQL Injection 的攻擊原理：

SQL Injection 的核心原理是利用了應用程式在構建 SQL 查詢語句時，未能正確地驗證和過濾使用者輸入的數據，導致惡意輸入的 SQL 代碼被直接拼接到合法的 SQL 語句中，進而改變了原有的查詢邏輯。

攻擊者可以通過以下方式利用此漏洞：

1. 注入惡意 SQL 語句以繞過驗證 (Bypass Authentication)：

   • 情境： 假設一個登入頁面，輸入使用者名稱和密碼。後端的 SQL 查詢可能類似：
     SELECT * FROM users WHERE username = '輸入的使用者名稱' AND password = '輸入的密碼';
   • 攻擊者輸入：
     • 使用者名稱： ' OR '1'='1
     • 密碼： 任意值 (例如 ' OR '1'='1)
   • 構建的 SQL 語句 (若未過濾)：
     SELECT * FROM users WHERE username = '' OR '1'='1' AND password = '...';
   • 原理： 由於 '1'='1' 永遠為真，整個 WHERE 條件變成 username = '' OR TRUE。如果應用程式邏輯是只要找到一筆記錄就成功登入，那麼這個查詢會返回第一個使用者（通常是管理員）的記錄，從而繞過了密碼驗證。
   • 另一種常見注入： ' OR '1'='1' -- (其中 -- 是 SQL 的註解符號，用於忽略後續的語句)。

2. 注入惡意 SQL 語句以讀取敏感數據 (Data Extraction)：

   • 情境： 假設一個網頁顯示某產品的詳細資訊，URL 可能是 http://example.com/product?id=123。後端查詢可能是：
     SELECT * FROM products WHERE product_id = 123;
   • 攻擊者輸入 (修改 URL)： http://example.com/product?id=123 UNION SELECT username, password FROM users --

核心觀念

• 介面 (interface) 與 抽象類別 (abstract class) 均屬於 型別，但 無法直接實例化，必須由 具體子類別 繼承或實作後才能建立物件。
• 抽象類別 可包含 抽象方法（沒有實作）與 具體方法（有實作），亦可宣告 常數、欄位、建構子。
• 介面 於 Java 8 之前僅能宣告 抽象方法 與 常數（public static final），不可包含實作；Java 8 起加入 default 方法（具體實作）與 static 方法。
• Java 不支援多重類別繼承（即一個類別同時 extend 多個類別），多重型別繼承只能透過 多重介面實作 來實現。

解題方法
針對每個選項，對照上述概念檢視其敘述的正確性：

1. 判斷「是否相同」→比較語法與功能差異。
2. 檢查「介面能否有實作」→依 Java 版本判斷 default 方法之存在。
3. 檢查「抽象類別與介面能否有常數」→兩者皆可宣告 public static final 常數。
4. 判斷「是否需要其他類別才能產生實例」→抽象類別與介面皆不可直接 new。
5. 判斷「抽象類別是否用於多重繼承」→檢視 Java 繼承機制。

選項分析

(a) 文字說明程式核心概念

本題測試以下物件導向與程式設計概念：

1. 抽象與封裝 – 以 Time 類別封裝「時」與「分」的資料與檢查格式的行為；以 ClockAngleCalculator 負責角度計算的演算法，兩者相互獨立、界面清晰。
2. 單一職責原則 (SRP) – Time 僅負責時間的表示與驗證；ClockAngleCalculator 僅負責根據給定時間算出最小夾角。
3. 資訊隱蔽 – 兩個類別的成員變數皆設為 private，外部只能透過公開方法取得所需資訊。
4. 多型/介面 – 若未來欲支援其他時計算方式，只要實作同樣的 calculateAngle() 方法即可擴充。

角度計算公式

• 分針每分鐘轉動 $6^\circ$：$\displaystyle \theta_m = 6 \times \text{minute}$
• 時針每小時轉動 $30^\circ$，每分鐘再額外轉動 $0.5^\circ$：
  $\displaystyle \theta_h = 30 \times (\text{hour}\bmod 12) + 0.5 \times \text{minute}$
• 兩針之差的絕對值 $|\theta_h-\theta_m|$ 可能大於 $180^\circ$，最小夾角為
  $\displaystyle \alpha = \min\big(|\theta_h-\theta_m|,\;360-|\theta_h-\theta_m|\big)$
• 輸出保留三位小數（千分之一度）。

(b) Class Diagram 及簡易說明

+-------------------+          +---------------------------+
|      Time         |<>------->|  ClockAngleCalculator     |
+-------------------+          +---------------------------+
| - hour : int      |          | + calculateAngle(t:Time) |
| - minute : int    |          |   : double                |
+-------------------+          +---------------------------+
| + Time(str)       |          | + formatAngle(a:double)   |
| + getHour() : int |          +---------------------------+
| + getMinute() :int|
| + isValid() :bool |
+-------------------+

• Time

  • 屬性：hour、minute（皆為 private）
  • 建構子：接受字串 "H:MM"，解析後存入屬性；若格式不符拋出例外。
  • 方法：getHour()、getMinute() 取得分別的值；isValid() 用於驗證時/分是否在合法範圍（0 ≤ hour ≤ 12、0 ≤ minute ≤ 59）。

• ClockAngleCalculator

  • 方法 calculateAngle(Time t)：依上述公式回傳最小夾角的 double（單位度）。
  • 方法 formatAngle(double a)：將角度以 String.format("%.3f", a) 轉成保留三位小數的字串，確保輸出符合題目要求。

兩個類別之間的關係為 「使用 (uses)」 ；ClockAngleCalculator 只需要 Time 物件的公開介面即可完成計算。

(c) 程式本身（含合理註解）