108 年 國立政治大學資訊管理學系碩士班科技組《計算機概論》

本題考查二元樹 (Binary Tree) 的基本定義。

本題考查堆疊 (Stack) 的基本操作。
堆疊是一種後進先出 (Last-In, First-Out, LIFO) 的資料結構。

本題考查時間複雜度的比較。
指數函數 $e^n$ 和階乘函數 $n!$ 都是成長非常快速的函數。
我們需要比較 $e^n$ 和 $n!$ 的成長速度。
考慮當 $n$ 趨近於無限大時：
$e^n$ 的成長速度是指數級的。

本題考查鏈結串列 (Linked List) 的 append 操作時間複雜度。
append 操作是指將一個新的節點加入到鏈結串列的最後方。
對於一個單向鏈結串列 (Singly Linked List)，要找到最後一個節點，需要從頭節點開始逐一遍歷，直到找到尾節點（其 next 指標為 NULL）。這個遍歷過程的時間複雜度是 $O(n)$，其中 $n$ 是鏈結串列的節點數量。
然而，如果鏈結串列的尾節點有一個額外的指標 (Tail Pointer) 指向最後一個節點，那麼 append 操作只需要更新尾節點的 next 指標並更新尾節點指標本身，這個操作的時間複雜度就是 $O(1)$。
題目沒有明確說明鏈結串列是否有尾節點指標。

本題考查 SMTP 的運作方式。
SMTP (Simple Mail Transfer Protocol) 是用於傳送電子郵件的協定。
當寄件方的郵件伺服器 (MTA - Mail Transfer Agent) 傳送郵件給收件方的郵件伺服器時，SMTP 協定在此之間運作。

本題考查 Dijkstra 演算法的時間複雜度。
Dijkstra 演算法用於尋找圖中單源點到所有其他點的最短路徑。
其時間複雜度與圖的表示法 (鄰接矩陣或鄰接串列) 以及所使用的優先佇列 (priority queue) 的實作方式有關。

1. 使用鄰接矩陣 (Adjacency Matrix) 表示圖：
   • 在遍歷每個節點時，需要掃描該節點的一整行（或一整列）的鄰接矩陣來尋找與之相鄰的節點。這需要 $O(|V|)$ 的時間。
   • 由於對每個節點都要執行一次，總共遍歷 $|V|$ 次。

本題考查 CPU 位址線與記憶體定址能力的關係。
CPU 的位址線數量決定了它可以定址的記憶體空間大小。如果一個 CPU 有 $N$ 條位址線，那麼它可以定址 $2^N$ 個不同的記憶體位址。
題目提到 CPU 是 64 位元，這通常是指 CPU 的資料匯流排寬度或暫存器寬度，但決定定址能力的是位址匯流排 (address bus) 的寬度。假設這個 64 位元 CPU 具有 64 條位址線。
那麼，它可以定址 $2^{64}$ 個記憶體位址。
每一個記憶體位址通常指向一個位元組 (byte)，也就是 8 個位元 (bits)。

本題考查 IP 位址的私有位址空間與 Internet 路由規則。
IP 位址空間中有一些特定的範圍被保留為私有位址 (Private IP Addresses)，這些位址僅能在內部網路 (Local Area Network, LAN) 使用，不能在公共網際網路 (Internet) 上路由。
這些私有位址範圍包括：

1. $10.0.0.0$ 到 $10.255.255.255$ (即 $10.0.0.0/8$)
2. $172.16.0.0$ 到 $172.31.255.255$ (即 $172.16.0.0/12$)

核心觀念

• Minimum edit distance（Levenshtein distance）：在兩字串之間，以 插入、刪除、置換 任一操作的成本皆為 1，求使兩字串相等的最小總操作次數。
• DP（動態規劃）公式

其中 $c=0$ 若第 $i$ 個字元與第 $j$ 個字元相同，否則 $c=1$。

解題方法

1. 建立 DP 表：字串 $S=\text{“GGTTGACTA”}$（長度 9）與 $T=\text{“TGTTACGG”}$（長度 8）。
2. 初始化第一列與第一欄：$D(i,0)=i$，$D(0,j)=j$。
3. 按上式逐格填入表格，僅列出關鍵格子以示計算過程（表格略）。

本題考查關聯式資料庫 (Relational Database) 中，外鍵 (Foreign Key) 的定義。
外鍵 (Foreign Key) 是指一個表格中的一個或多個欄位，其值參照到另一個表格的主鍵 (Primary Key) 或候選鍵 (Candidate Key)。
外鍵的主要目的是建立表格之間的關聯，並確保參照的完整性 (Referential Integrity)。
雖然外鍵「通常」參照到另一個表格的主鍵，但它也可以參照到另一個表格的「唯一鍵 (Unique Key)」或「候選鍵 (Candidate Key)」。
主鍵是候選鍵中被選定用來唯一識別表格中每一行的鍵。

本題考查雜湊函數 (Hash Function) 的特性。
一個設計良好的雜湊函數，其目標是將輸入資料均勻地映射到一個預設的雜湊表中。
如果雜湊函數的輸出範圍是 $0$ 到 $N-1$，那麼一個理想的雜湊函數應該讓每個輸出值 (雜湊桶, hash bucket) 被命中的機率大致相等。

核心觀念

圖示的 8 位元浮點數格式為：

• 1 位元：符號位元（Sign bit）
• 3 位元：指數（Exponent）
• 4 位元：尾數（Mantissa）

浮點數可表示為：

其中尾數 $M$ 的精確度受 4 個位元限制，因此正規化後最多只能保留 4 位有效二進位數字。

解題方法

將各選項轉換為二進位，並判斷正規化後是否能以 4 位尾數精確表示。

(A) $-\dfrac{15}{2}$

可寫成：

尾數為 $1111$，共 4 位，可表示。

(B) $\dfrac{31}{32}$

此數正規化後仍需要 5 位尾數：

但題目只有 4 位尾數，無法精確表示。

(C) $-\dfrac{15}{4}$

可寫成：

核心觀念
本題考查位元運算與位移運算的基本概念。

• AND（∧）：對應位皆為 1 時結果才為 1。
• OR（∨）：只要對應位有一個 1 結果即為 1。
• XOR（⊕）：對應位不同時結果為 1，相同時為 0。
• NOT：一元反相，0 → 1，1 → 0。
• 右移 (>>)：將二進位字串向右平移指定位數，高位補 0（對於本題的正整數）。

解題方法
逐一對每個選項的位元運算或位移結果計算，檢查最終是否全為 0（即 00000000）。

• 多層運算採由內向外、由左至右的順序（與括號所示）。
• 位元長度皆以 8 位元為基礎，若運算結果不足 8 位元，左側以 0 補齊。

選項分析

核心觀念

• 頁面大小 (page size)：記憶體被分割成固定大小的頁面，常見單位為 4 KB、8 KB 等。
• 頁面錯誤 (page fault)：當 CPU 需要的頁面不在實體記憶體中，硬體產生例外，作業系統將該頁面從磁碟調入。
• 頁面錯誤率 (page‑fault ratio)：單位時間內產生的 page fault 數量除以總記憶體存取次數。
• I/O 時間：一次 page fault 需要的磁碟傳輸時間，與調入的頁面大小成正比。
• 記憶體碎裂 (fragmentation)：
  • 內部碎裂：單一頁面未被完整使用而浪費的空間，頁面越大內部碎裂越嚴重。
  • 外部碎裂：在變長分配時，已分配的塊之間留下的無法利用的空隙，與頁面大小關係不大。

解題方法

1. 釐清「頁面大小變小」對下列三個量的影響：
   • 頁面錯誤率
   • 每次 I/O 所需時間
   • 記憶體碎裂程度
2. 比較「大」與「小」兩極情況，判斷每個敘述的正確性。
3. 針對「process 數量過多」與「page fault 與 system call 同時發生」兩個較易混淆的選項，檢視概念差異即可作出判斷。

選項分析

• (A) 作業系統的分頁大小(page size)越小, page fault ratio 越大。

  • 正確。頁面變小，欲存取同樣大小的資料需要更多頁面。若工作集大小不變，記憶體能容納的頁數會增加，導致每次換頁只能載入較少的資料，結果是同樣的記憶體參照在較多的頁面之間跳動，產生較高的 page fault 次數，故比例上升。

• (B) 作業系統的分頁大小(page size)越小, I/O 時間越長。

  • 錯誤。

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• 頁面大小 (page size)：記憶體被分割成固定大小的頁面，常見單位為 4 KB、8 KB 等。
• 頁面錯誤 (page fault)：當 CPU 需要的頁面不在實體記憶體中，硬體產生例外，作業系統將該頁面從磁碟調入。
• 頁面錯誤率 (page‑fault ratio)：單位時間內產生的 page fault 數量除以總記憶體存取次數。
• I/O 時間：一次 page fault 需要的磁碟傳輸時間，與調入的頁面大小成正比。
• 記憶體碎裂 (fragmentation)：
  • 內部碎裂：單一頁面未被完整使用而浪費的空間，頁面越大內部碎裂越嚴重。
  • 外部碎裂：在變長分配時，已分配的塊之間留下的無法利用的空隙，與頁面大小關係不大。

解題方法

1. 釐清「頁面大小變小」對下列三個量的影響：
   • 頁面錯誤率
   • 每次 I/O 所需時間
   • 記憶體碎裂程度
2. 比較「大」與「小」兩極情況，判斷每個敘述的正確性。
3. 針對「process 數量過多」與「page fault 與 system call 同時發生」兩個較易混淆的選項，檢視概念差異即可作出判斷。

選項分析

• (A) 作業系統的分頁大小(page size)越小, page fault ratio 越大。

  • 正確。頁面變小，欲存取同樣大小的資料需要更多頁面。若工作集大小不變，記憶體能容納的頁數會增加，導致每次換頁只能載入較少的資料，結果是同樣的記憶體參照在較多的頁面之間跳動，產生較高的 page fault 次數，故比例上升。

• (B) 作業系統的分頁大小(page size)越小, I/O 時間越長。

  • 錯誤。

核心觀念

• Deadlock（死結）：系統同時滿足四個必要條件（互斥、保持、等待、循環等待）時，參與的程序皆無法繼續執行。
• Starvation（飢餓）：某些程序因資源分配策略（如優先權排程）長時間得不到所需資源，雖然系統仍有可執行的程序，但這些程序被「餓死」了。
• Preemptive（可搶奪）機制：作業系統可以在程序持有資源期間強制收回資源，常用於避免 deadlock，但 starvation 仍可能發生。

解題方法

1. 先釐清每個選項所描述的概念是否與上述定義相符。
2. 判斷敘述是否為 必然（always）或僅是 可能（may）。題目使用「一定」或「必定」等絕對詞彙，若該敘述在任何情境下都有例外，則為錯。
3. 針對每個選項逐一驗證：
   • 是否符合 資源互斥、持有‑等待、循環等待 等 deadlock 必要條件。
   • 是否與 preemptive 機制對 starvation 的影響相衝突。

選項分析

核心觀念

• Retransmission 機制：TCP 只在 sender 端因 timeout 或 重複 ACK（fast‑retransmit）而重新傳送資料，receiver 端不會觸發 timeout。
• Congestion Window (cwnd)：控制 sender 同時未被確認的資料量。cwnd 只在 sender 收到 ACK 後依照擁塞控制演算法（slow‑start、congestion‑avoidance）調整，且在 slow‑start 階段呈 指數 成長。
• Receiving Window (rwnd)：由 receiver 宣告的可接收緩衝區大小，僅在 receiver 端根據本地緩衝區剩餘空間變化而改變，與每收到一個訊息的次數無直接關係。
• Slow‑Start 階段：cwnd 以 指數 增加，初始值通常為 1 或 2 個 MSS，每收到一次 ACK，就將 cwnd 增加 1 MSS（即 cwnd = cwnd + MSS），等同於 $cwnd = 2^{k}\,{\rm MSS}$，因此成長速度相當快速。

解題方法
逐一驗證選項敘述是否符合上述 TCP 基本規則。若敘述與標準 RFC 793/1122 或常見課本描述相違，即判為錯誤。

選項分析

• (A) TCP sender 的 retransmission 機制可由 sender 端 timeout 觸發或由 receiver 端 timeout 觸發。
  • 錯誤。TCP 的重傳只在 sender 端因 timeout（未在 RTO 時間內收到 ACK）或 duplicate ACK（快速重傳）而發生。receiver 端沒有 timeout 機制會直接觸發 sender 重傳。

核心觀念

• Retransmission 機制：TCP 只在 sender 端因 timeout 或 重複 ACK（fast‑retransmit）而重新傳送資料，receiver 端不會觸發 timeout。
• Congestion Window (cwnd)：控制 sender 同時未被確認的資料量。cwnd 只在 sender 收到 ACK 後依照擁塞控制演算法（slow‑start、congestion‑avoidance）調整，且在 slow‑start 階段呈 指數 成長。
• Receiving Window (rwnd)：由 receiver 宣告的可接收緩衝區大小，僅在 receiver 端根據本地緩衝區剩餘空間變化而改變，與每收到一個訊息的次數無直接關係。
• Slow‑Start 階段：cwnd 以 指數 增加，初始值通常為 1 或 2 個 MSS，每收到一次 ACK，就將 cwnd 增加 1 MSS（即 cwnd = cwnd + MSS），等同於 $cwnd = 2^{k}\,{\rm MSS}$，因此成長速度相當快速。

解題方法
逐一驗證選項敘述是否符合上述 TCP 基本規則。若敘述與標準 RFC 793/1122 或常見課本描述相違，即判為錯誤。

選項分析

• (A) TCP sender 的 retransmission 機制可由 sender 端 timeout 觸發或由 receiver 端 timeout 觸發。
  • 錯誤。TCP 的重傳只在 sender 端因 timeout（未在 RTO 時間內收到 ACK）或 duplicate ACK（快速重傳）而發生。receiver 端沒有 timeout 機制會直接觸發 sender 重傳。

本題考查 IP 位址的子網路切割 (Subnetting) 概念，以及 CIDR 的表示法。

原始網路位址為 $192.168.100.0/24$。
這表示：

• 網路位址 (Network Address): $192.168.100.0$
• 主機位址 (Host Address) 的長度: $32 - 24 = 8$ 位元。
• Netmask: $255.255.255.0$ (二進位為 24 個 1 後接 8 個 0)。

目標是將這個 /24 的網路切割成四個子網路 (subnets)。
要切割成 4 個子網路，我們需要在主機位元部分借用位元來作為子網路位元。
借用的位元數 $n$ 必須滿足 $2^n \ge 4$。
最小的 $n$ 是 2，因為 $2^2 = 4$。
所以，我們需要從原來的 8 個主機位元中借用 2 位元作為子網路位元。

借用 2 位元後，新的子網路位址的 CIDR 表示法將是 /$(24 + 2) = /26$。
新的 Netmask 將會有 $(24 + 2) = 26$ 個 1。
原始 Netmask: 11111111.11111111.11111111.00000000
借用 2 位元後，新的 Netmask: 11111111.11111111.11111111.11000000
轉換成十進位：$255.255.255.(128 + 64) = 255.255.255.192$。

每個子網路將有 $32 - 26 = 6$ 個主機位元。
每個子網路可以使用的 IP 位址數量為 $2^6 = 64$ 個。
其中，第一個位址是 Network ID，最後一個位址是 Broadcast Address，其餘為可用主機 IP。
每個子網路的主機 IP 數量為 $2^6 - 2 = 62$ 個。

現在我們來計算四個子網路的 Network ID：
原始網路 ID 是 $192.168.100.0$。
借用的 2 個子網路位元在原始 IP 位址的最後一個位元組 (octet) 中。
原始 IP 位址的最後一個位元組是 00000000 (主機位元)。
新的 Netmask 是 11000000 (子網路位元在前 2 位)。

四個子網路的 Network ID 是由這 2 個子網路位元組合決定的。
這 2 個位元的值可以是：00, 01, 10, 11。
它們對應的最後一個位元組的值是：

• 00xxxxxx (主機位元) -> 0
• 01xxxxxx (主機位元) -> 64
• 10xxxxxx (主機位元) -> 128
• 11xxxxxx (主機位元) -> 192

所以，四個子網路的 Network ID 分別是：

1. 子網路 1:

   • Network ID: $192.168.100.0$
   • CIDR: $192.168.100.0/26$
   • Netmask: $255.255.255.192$
   • IP Range: $192.168.100.0$ (Network ID) 到 $192.168.100.63$ (Broadcast Address)。
     可用主機 IP: $192.168.100.1$ 到 $192.168.100.62$。

2. 子網路 2:

   • Network ID: $192.168.100.64$
   • CIDR: $192.168.100.64/26$
   • Netmask: $255.255.255.192$
   • IP Range: $192.168.100.64$ (Network ID) 到 $192.168.100.127$ (Broadcast Address)。
     可用主機 IP: $192.168.100.65$ 到 $192.168.100.126$。

3. 子網路 3:

   • Network ID: $192.168.100.128$
   • CIDR: $192.168.100.128/26$
   • Netmask: $255.255.255.192$

核心觀念

圖示的 8 位元浮點數格式為：

• 1 位元：符號位元（Sign bit）
• 3 位元：指數（Exponent）
• 4 位元：尾數（Mantissa）

浮點數可表示為：

其中尾數 $M$ 的精確度受 4 個位元限制，因此正規化後最多只能保留 4 位有效二進位數字。

解題方法

將各選項轉換為二進位，並判斷正規化後是否能以 4 位尾數精確表示。

(A) $-\dfrac{15}{2}$

可寫成：

尾數為 $1111$，共 4 位，可表示。

(B) $\dfrac{31}{32}$

此數正規化後仍需要 5 位尾數：

但題目只有 4 位尾數，無法精確表示。

(C) $-\dfrac{15}{4}$

可寫成：

核心觀念
本題考查位元運算與位移運算的基本概念。

• AND（∧）：對應位皆為 1 時結果才為 1。
• OR（∨）：只要對應位有一個 1 結果即為 1。
• XOR（⊕）：對應位不同時結果為 1，相同時為 0。
• NOT：一元反相，0 → 1，1 → 0。
• 右移 (>>)：將二進位字串向右平移指定位數，高位補 0（對於本題的正整數）。

解題方法
逐一對每個選項的位元運算或位移結果計算，檢查最終是否全為 0（即 00000000）。

• 多層運算採由內向外、由左至右的順序（與括號所示）。
• 位元長度皆以 8 位元為基礎，若運算結果不足 8 位元，左側以 0 補齊。

選項分析

本題考查關聯式資料庫中的兩種 JOIN 操作：INNER JOIN 和 CROSS JOIN。

(a) INNER JOIN
概念說明：
INNER JOIN (內連接) 是 SQL 中最常用的 JOIN 操作之一，用於合併兩個或多個表格的記錄。它會根據指定的連接條件 (JOIN condition)，從被連接的表格中選取記錄。只有當連接條件在兩個表格中都得到滿足時，才會生成一條合併後的記錄。換句話說，INNER JOIN 只會返回兩個表格中匹配的行。

運作方式：
假設我們有兩個表格 T1 和 T2，並且我們執行 T1 INNER JOIN T2 ON T1.column = T2.column。

• 系統會遍歷 T1 中的每一行。
• 對於 T1 中的每一行，系統會遍歷 T2 中的每一行。
• 如果 T1 中的某一行與 T2 中的某一行在指定的連接條件 T1.column = T2.column 上匹配，則將這兩行合併成一條新的記錄。
• 所有不滿足連接條件的行對將被丟棄。

範例：
假設有兩個表格：
雇員表 (Employee)

部門表 (Department)

執行 Employee INNER JOIN Department ON Employee.DepartmentID = Department.DepartmentID：

• Rafferty (Dept 31) 匹配 Department 31 (銷售部)。
• Jones (Dept 33) 匹配 Department 33 (工程部)。
• Steinberg (Dept 33) 匹配 Department 33 (工程部)。
• Robinson (Dept 34) 匹配 Department 34 (市場部)。

結果：

用途：
INNER JOIN 通常用於根據共同的鍵值關聯相關數據，例如查找所有員工及其所屬部門的名稱。

(b) CROSS JOIN
概念說明：
CROSS JOIN (笛卡兒積連接) 是另一種 JOIN 操作，它會將第一個表格的每一行與第二個表格的每一行進行組合，產生一個包含所有可能組合的結果集。它不會使用 ON 子句來指定連接條件，而是生成兩個表格的笛卡兒積 (Cartesian Product)。

運作方式：
假設我們有表格 T1 (有 $m$ 行) 和表格 T2 (有 $n$ 行)。
執行 T1 CROSS JOIN T2 (或在某些 SQL 方言中使用 T1, T2) 會產生 $m \times n$ 行的結果集。

本題考查雜湊函數 (Hash Function) 的定義及其特性。

雜湊函數 (Hash Function) 的定義：
雜湊函數是一種將任意大小的輸入（例如字串、檔案、物件等）映射到固定大小輸出（稱為雜湊值、雜湊碼、或簡稱雜湊）的函數。這個過程通常稱為雜湊 (Hashing)。雜湊值可以被視為輸入數據的「指紋」或「摘要」。

雜湊函數的常見應用包括：

1. 雜湊表 (Hash Table)：用於快速查找、插入和刪除數據。雜湊函數將鍵映射到雜湊表中某個桶 (bucket) 的索引。
2. 密碼學：用於生成訊息摘要 (Message Digest)，確保數據的完整性和真實性。
3. 數據校驗：用於檢測數據在傳輸或儲存過程中是否發生錯誤。

雜湊函數應有的兩個特點：

1. 高效性 (Efficiency)：

   • 說明： 雜湊函數應該能夠非常快速地計算出雜湊值。對於任意輸入，計算雜湊值所需的時間應該是確定性的，並且在實際應用中足夠快（通常是 $O(1)$ 或 $O(n)$，其中 $n$ 是輸入大小）。
   • 重要性： 在雜湊表中，雜湊函數的計算速度直接影響查找、插入和刪除操作的整體效能。如果雜湊函數計算緩慢，那麼雜湊表將失去其快速查找的優勢。

2. 均勻分佈 (Uniform Distribution)：

   • 說明： 一個好的雜湊函數應該將不同的輸入均勻地映射到其輸出空間中。這意味著，對於大量的不同輸入，輸出的雜湊值應該在整個輸出範圍內均勻分佈，而不會集中在某個區域。

本題考查使用 Pseudocode 篩選特定範圍內滿足多個條件的數字。

問題分析：
我們需要找出 1 到 100 之間的整數，這些數字必須同時滿足以下三個條件：

1. 是偶數 (even)。
2. 不能被 3 整除 (not divisible by 3)。
3. 可以被 5 整除 (divisible by 5)。

解題思路：
最直接的方法是遍歷 1 到 100 的每一個整數，並檢查它是否同時滿足上述三個條件。如果滿足，則將該數字輸出。

條件判斷：

• 一個數字 $n$ 是偶數，若 $n \pmod 2 = 0$。
• 一個數字 $n$ 不能被 3 整除，若 $n \pmod 3 \neq 0$。
• 一個數字 $n$ 可以被 5 整除，若 $n \pmod 5 = 0$。

Pseudocode 結構：
我們可以使用一個循環 (例如 FOR loop) 來迭代 1 到 100 的數字。在循環內部，使用 IF 語句來檢查所有條件是否同時成立。

Pseudocode 撰寫：

PROCEDURE FindNumbers
  // 宣告一個變數來迭代數字
  DECLARE num INTEGER

  // 輸出提示訊息
  PRINT "符合條件的數字如下："

  // 循環遍歷 1 到 100 的所有整數
  FOR num FROM 1 TO 100 DO
    // 檢查條件：
    // 1. 是偶數 (num MOD 2 == 0)
    // 2. 不能被 3 整除 (num MOD 3 != 0)
    // 3. 可以被 5 整除 (num MOD 5 == 0)
    IF (num MOD 2 == 0) AND (num MOD 3 != 0) AND (num MOD 5 == 0) THEN
      // 如果所有條件都滿足，則輸出該數字
      PRINT num
    END IF
  END FOR
END PROCEDURE

// 呼叫程序開始執行
CALL FindNumbers

優化思考 (可選)：
我們可以進行一些觀察來優化。

• 如果一個數字可以被 5 整除，且是偶數，那麼它必須是 10 的倍數。
  • 例如：10, 20, 30, 40, 50, 60, 70, 80, 90, 100。
• 然後我們只需要檢查這些 10 的倍數是否不能被 3 整除。
  • 10: $10 \pmod 3 = 1 \neq 0$ (符合)
  • 20: $20 \pmod 3 = 2 \neq 0$ (符合)
  • 30: $30 \pmod 3 = 0$ (不符合)
  • 40: $40 \pmod 3 = 1 \neq 0$ (符合)
  • 50: $50 \pmod 3 = 2 \neq 0$ (符合)
  • 60: $60 \pmod 3 = 0$ (不符合)

本題考查將十進位整數轉換為十六進位字串的 Pseudocode 實作。

函式要求：

• 輸入：一個十進位整數 n。
• 輸出：一個字串，以 "0x" 開頭，後面跟著 n 的十六進位表示。
• 十六進位數字使用：0123456789ABCDEF。

核心轉換邏輯：
將一個十進位數轉換為十六進位數，通常是透過不斷地除以 16 並記錄餘數來實現。餘數就是十六進位的數字，從最低位元開始產生。

步驟：

1. 處理特殊情況： 如果輸入的十進位數 n 是 0，則直接返回 "0x0"。
2. 建立十六進位對應表： 為了方便將餘數 (0-15) 轉換為對應的十六進位字元 ('0'-'9', 'A'-'F')，可以創建一個字串或陣列。
3. 循環轉換：
   • 當 n 大於 0 時，執行以下操作：
     • 計算 n 除以 16 的餘數：remainder = n MOD 16。
     • 將餘數轉換為對應的十六進位字元，例如使用 hex_digits[remainder]。
     • 將這個十六進位字元加到結果字串的開頭（因為餘數是從最低位產生的，需要反向組合）。
     • 更新 n：n = n / 16 (整數除法)。
4. 組合結果： 在循環結束後，將 "0x" 前綴加到構建好的十六進位字串前面。

Pseudocode 實作：

FUNCTION Dec_to_Hex(n : INTEGER) : STRING
  // 宣告十六進位對應字元陣列
  DECLARE hex_digits : ARRAY OF CHAR = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'}
  
  // 宣告儲存結果的字串變數
  DECLARE hex_string : STRING = ""
  
  // 處理輸入為 0 的特殊情況
  IF n == 0 THEN
    RETURN "0x0"
  END IF
  
  // 處理負數（題目未明確說明，但通常需要考慮。這裡假設 n 為非負數，若有負數，需額外處理，例如補碼）
  // 這裡假設 n >= 0
  
  // 迴圈進行轉換
  DECLARE temp_n : INTEGER = n // 使用臨時變數，避免修改原始輸入 n
  WHILE temp_n > 0 DO
    DECLARE remainder : INTEGER = temp_n MOD 16
    // 將餘數對應的十六進位字元加到字串的開頭
    hex_string = hex_digits[remainder] + hex_string 
    // 更新 temp_n 為整數除法結果
    temp_n = temp_n / 16 
  END WHILE
  
  // 在結果前加上 "0x" 前綴
  RETURN "0x" + hex_string
END FUNCTION

// 範例呼叫 (題目中已給出函式簽章，這裡僅為說明用法)
// string result = Dec_to_Hex(100); // result 應該是 "0x64"
// string result_zero = Dec_to_Hex(0); // result_zero 應該是 "0x0"

填入原函式框架：

核心觀念

每個元素對某一個子集合只有兩種選擇：放入或不放入。對 $n$ 個元素各自做一次選擇，因此 $S$ 的 power set 共有

個子集合，其中包含空集合 $\varnothing$ 與集合本身 $S$。

解題方法

依序處理集合中的元素。處理每個元素時，遞迴分成兩條路徑：一條不將元素放入目前子集合，另一條將元素放入。所有元素都處理完後，輸出目前形成的子集合。

核心觀念

本題考查：

• 雜湊集合（hash set）
• 連續整數序列的判定
• 線性時間演算法設計
• 避免先排序所造成的 $O(n\log n)$ 時間複雜度

若某整數 $x$ 的前一個數 $x-1$ 不存在於陣列中，則 $x$ 必定是某個連續序列的起點。從起點開始依序檢查 $x+1,x+2,\ldots$ 是否存在，即可找出該序列長度。

例如：

建立集合後為：

其中 $1$ 的前項 $0$ 不存在，因此 $1$ 是序列起點；接著檢查 $2,3,4$ 均存在，得到最長序列：

解題方法

將所有陣列元素存入 hash set，使得查詢某個整數是否存在的平均時間為 $O(1)$。

對每個元素 $x$：

1. 若 $x-1$ 存在，表示 $x$ 不是序列起點，略過。
2. 若 $x-1$ 不存在，表示 $x$ 是序列起點。
3. 從 $x$ 開始，持續檢查 $x+1,x+2,\ldots$ 是否存在。
4. 若目前序列長度大於已知最長長度，更新答案。

Pseudocode

function longestConsecutiveSequence(array A):
    S ← empty hash set

    for each value x in A:
        insert x into S

    bestSequence ← empty list

    for each value x in S:
        if (x - 1) not in S:
            currentSequence ← empty list
            current ← x

            while current in S:
                append current to currentSequence
                current ← current + 1

            if length(currentSequence) > length(bestSequence):
                bestSequence ← currentSequence

    return bestSequence

演算法正確性說明

1. 起點判定正確

若 $x-1$ 存在於集合中，則 $x$ 可接在 $x-1$ 後面，因此 $x$ 不可能是連續序列的起點。

若 $x-1$ 不存在於集合中，則沒有更小的整數能與 $x$ 連接，因此 $x$ 必為某個連續序列的起點。

2. 序列擴展正確

從起點 $x$ 開始，依序檢查 $x+1,x+2,\ldots$：

• 若下一個整數存在，就加入序列。
• 若下一個整數不存在，連續序列即在此結束。

因此，所建立的 currentSequence 恰好是一個完整的連續整數序列。

3. 最長序列選擇正確

演算法會檢查所有連續序列的起點，並比較每個序列的長度。最後保留長度最大的序列，因此回傳結果必為陣列中的最長連續項目序列。

範例追蹤

輸入：

A = [100, 4, 2, 1, 3]

集合：

S = {100, 1, 2, 3, 4}

各元素判定：