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

本題主要在測試對網路協定與網頁資料交換格式的理解。

題目中的第一個空格，描述的是「客戶端與伺服器在網際網路交換資料的資料通訊方法」。
網際網路（Internet）上的資料通訊通常仰賴一系列標準協定，其中 HTTP (Hypertext Transfer Protocol) 是最常見的。HTTPS 則是 HTTP 的安全版本，在網際網路上的資料傳輸中扮演關鍵角色。URL (Uniform Resource Locator) 則是資源的位址，而非通訊方法。

本題考查資料庫交易管理中的一致性問題與解決方案。

資料庫交易（Database Transaction）是一系列操作的集合，必須保證原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）、持久性（Durability），即 ACID 特性。當一個交易涉及多個數據庫或多個資源時，保證其原子性變得複雜。

• Two-phase commit (2PC)：是一種分散式系統中的原子提交協定，旨在確保參與者（如多個資料庫節點）對交易的最終決定（提交或中止）達成一致。它分為兩個階段：
  1. 準備階段（Prepare Phase）：協調者詢問所有參與者是否準備好提交。參與者執行交易的本地部分，並將結果（準備好或不能提交）報告給協調者。
  2. 提交階段（Commit Phase）：如果所有參與者都準備好了，協調者會發送提交指令。

本題考查作業系統中資源存取控制的機制。

在多工作業系統（multitasking OS）中，多個程序（process）或執行緒（thread）可能同時或依序存取共享資源（如印表機、共享記憶體、檔案等）。為了避免資源競爭導致的資料損壞或不一致，需要有機制來控制對這些資源的存取。

a) Semaphore (訊號燈)：是一種同步原語（synchronization primitive），用於控制多個執行緒或程序對共享資源的存取。它維護一個計數器，並提供兩個主要操作：wait (或 P) 和 signal (或 V)。wait 操作會減少計數器，如果計數器變為負數，則執行緒會被阻塞；signal 操作會增加計數器，並可能喚醒一個被阻塞的執行緒。

本題考查作業系統中行程表（Process Table）的內容。

行程表是作業系統用來管理各個行程（process）的資料結構。其中包含了每個行程的關鍵資訊，以便作業系統能夠有效地調度、管理和切換行程。

一個典型的行程表（或稱為 Process Control Block, PCB）通常包含以下資訊：

• 行程狀態 (Process State)：例如，新建 (new)、就緒 (ready)、執行中 (running)、等待 (waiting)、終止 (terminated)。
• 行程 ID (Process ID)：唯一識別符。
• CPU 暫存器資訊 (CPU Registers)：包括程式計數器 (Program Counter, PC)、堆疊指標 (Stack Pointer, SP) 等，這些資訊在行程切換時需要保存。
• CPU 調度資訊 (CPU Scheduling Information)：如行程的優先級 (priority)、排程佇列指標等。

本題考查 RAID (Redundant Array of Independent Disks) 的基本概念，特別是其最簡單的寫入方式。

RAID 是一種將多個獨立的硬碟組合起來，以提供比單一硬碟更好的效能、容量或可靠性的技術。
常見的 RAID 層級包括：

• RAID 0 (Striping)：將資料分散寫入多個硬碟。當寫入一個檔案時，檔案會被分割成區塊，並同時寫入不同的硬碟。這樣做可以顯著提高讀寫效能，因為可以同時讀寫多個磁碟。這是最簡單的「同時寫入不同硬碟」且能提高效能的設計，但沒有任何冗餘，單一硬碟損壞會導致所有資料遺失。
• RAID 1 (Mirroring)：將相同的資料同時寫入兩個或多個硬碟。這提供了高度的冗餘，因為如果一個硬碟損壞，另一個硬碟仍保有完整的資料。但儲存空間的利用率較低，因為需要備份。
• RAID 5/6：結合了條帶化（striping）和奇偶校驗（parity），提供效能和冗餘的平衡。
• Duplicating (複製)：這個詞比較廣泛，但在 RAID 的語境下，最接近的是 Mirroring。
• Partitioning (分割)：指的是將一個實體硬碟劃分成多個邏輯磁碟區，與 RAID 的概念不同。

題目要求的是「最簡單的 RAID 儲存設計，將資料同時寫入不同的硬碟」。

• Mirroring 是將資料「相同地」寫入不同硬碟，以提供冗餘。
• Striping 是將資料「分割後」同時寫入不同硬碟，以提高效能。

本題延續 RAID 的概念，詢問哪種設計能夠將資料、指令和資訊「分割」並分散到陣列中的多個硬碟。

• Striping (條帶化)：這是 RAID 0 的核心技術。它將資料分割成較小的區塊，然後將這些區塊依序寫入 RAID 陣列中的不同硬碟。這樣做可以讓多個硬碟同時進行讀寫操作，從而顯著提高整體效能。因此，Striping 正是將資料、指令和資訊「分割」並分散到多個硬碟的技術。
• Duplicating (複製)：這個詞較為籠統。

本題考查網路協定、電腦硬體基本概念、字元編碼以及 OSI/TCP/IP 模型。我們逐一分析每個敘述的正確性：

a. Firmware consists of ROM or memory chips that store permanent instructions, such as start-up instructions
Firmware 是一種嵌入式軟體，它儲存在非揮發性記憶體（如 ROM, PROM, EPROM, EEPROM, Flash Memory）中。它通常包含硬體啟動所需的低階指令，例如 BIOS (Basic Input/Output System) 或 UEFI (Unified Extensible Firmware Interface)，這些指令負責初始化硬體並載入作業系統。因此，這個敘述是正確的。

b. Ethernet is in the data link layer, which transfers data between the network nodes
Ethernet 是最常見的區域網路（LAN）技術。根據 OSI 模型（或 TCP/IP 模型），Ethernet 工作在資料連結層（Data Link Layer, Layer 2）。資料連結層負責在相鄰的網路節點（nodes）之間可靠地傳輸資料幀（frames），並處理 MAC 位址、錯誤偵測等。因此，這個敘述是正確的。

c. ASCII can map characters to numeric values that allow a machine to process

核心觀念

• Stack（堆疊）：遵循 Last‑In‑First‑Out (LIFO) 原則，最新加入的元素最先被移除。常見操作有 push()（加入）與 pop()（移除最後加入的元素），peek()（查看最上層元素但不移除）。
• Queue（佇列）：遵循 First‑In‑First‑Out (FIFO) 原則，最早加入的元素最先被移除。常見操作有 offer()（或 add()）加入元素、poll()（或 remove()）取出最前面的元素，peek()（查看最前端元素但不移除）。
• 兩者皆屬於 線性資料結構，在實作上可使用陣列、鏈結串列或內建集合類別（如 Java 的 Stack、Queue 介面）。

---

解題方法
針對每一選項的描述，直接比對其與上述資料結構的定義及常見 API（以 Java 為例）是否相符；若有不符或描述錯誤，即判定為錯誤。此題屬於概念辨識型多選題，無需計算，只要檢查概念與術語的正確性即可。

---

選項分析

選項	內容	正確性說明
a	Stack is based on last-in-first-out principle; whereas Queue is based on first-in-first-out principle.	正確。Stack 的 LIFO 與 Queue 的 FIFO 正是兩者最根本的差別。
b	In a queue: offer() is used to add an item, and remove() is used to retrieve an item.	錯誤。

本題考查排序演算法的性質。我們逐一分析每個敘述：

a. Merge sort always outperform than selection sort.

• Merge Sort (合併排序)：時間複雜度在最好、平均、最壞情況下皆為 $O(n \log n)$。
• Selection Sort (選擇排序)：時間複雜度在最好、平均、最壞情況下皆為 $O(n^2)$。

由於 $O(n \log n)$ 通常比 $O(n^2)$ 更快（尤其對於較大的 n），Merge Sort 在漸進時間複雜度上優於 Selection Sort。然而，「always outperform」這個詞語可能過於絕對。在非常小的資料集上，Selection Sort 的常數因子可能較小，表現可能與 Merge Sort 相當或稍好。但從演算法的理論角度來看，Merge Sort 的效能是優於 Selection Sort 的。
如果題目指的是「漸進時間複雜度」，則此敘述大致正確。但如果嚴格解釋，並考慮常數因子和小資料集，則不一定「總是」優於。

b. Selection sort and heap sort can have similar time complexity in the worst case scenario.

• Selection Sort (選擇排序)：最壞情況時間複雜度為 $O(n^2)$。
• Heap Sort (堆積排序)：最壞情況時間複雜度為 $O(n \log n)$。

$O(n^2)$ 和 $O(n \log n)$ 是不同的。因此，這個敘述是錯誤的。

核心觀念

本題考查數位安全（digital security）的基本概念，包括：

• 通行片語（passphrase）
• 生物辨識裝置（biometrics device）
• 對稱式金鑰加密（symmetric key encryption）
• 使用者帳戶（user account）

判斷此類題目的關鍵，是確認各選項中的定義是否符合資訊安全與電腦概論的標準用語。

解題方法

逐一比對各選項的敘述與正式定義。題目詢問「NOT true」，因此要找出唯一不正確的敘述。

選項分析

a) passphrase

passphrase is a sequence or combination of words, which often contains mixed capitalization and characters

Passphrase 是由一連串單字組成的通行片語，通常比單一密碼更長，例如：

BlueRiverStudy2024!

通行片語可能包含大小寫字母、數字與特殊字元，以提高密碼強度。因此此敘述正確。

補充而言，passphrase 的核心特徵是「由多個單字或字串組成且長度較長」，混合大小寫與特殊字元則是常見的強化方式。

b) biometrics device

biometrics device authenticates a person's identity by translating his/her physiological or behavioral characteristics into an analog code

生物辨識裝置會根據人的生理特徵或行為特徵來確認身分，例如：

• 生理特徵：指紋、臉部、虹膜、掌紋
• 行為特徵：聲音、簽名方式、打字節奏

然而，裝置實際上是將這些特徵轉換成可由電腦處理的數位資料或數位特徵模板（biometric template），再與資料庫中的樣本進行比對。題目敘述使用 analog code（類比碼），不符合數位安全與生物辨識的標準定義。

因此此選項錯誤。

c) symmetric key encryption

本題考查數位儲存裝置的相關知識，要求找出錯誤的敘述。

a) non-volatile NAND flash memory is often used in a solid-state drive
固態硬碟（SSD）的主要儲存介質就是 NAND 快閃記憶體（NAND flash memory）。NAND 快閃記憶體是一種非揮發性記憶體，意味著即使斷電，資料也能被保留。因此，這個敘述是正確的。

b) a computer can have both a solid-state drive and a hard disk
現代電腦通常可以同時安裝和使用多種儲存裝置。許多使用者會選擇將作業系統和常用程式安裝在速度較快的 SSD 上，同時使用容量較大的傳統硬碟（HDD）來儲存文件、媒體檔案等。因此，這個敘述是正確的。

c) defragmentation can optimize the performance in both a solid-state drive and a hard disk

• 硬碟重組（Defragmentation）：對於傳統機械式硬碟（HDD）來說，當檔案被寫入、刪除、修改後，檔案碎片（fragments）會分散儲存在磁碟的不同位置。

本題考查電腦組成原理，特別是 CPU 的工作原理、記憶體層級結構等，要求找出錯誤的敘述。

a) a machine cycle includes fetch, decode, execute, and store operations
機器週期（Machine Cycle）或稱指令週期（Instruction Cycle）是 CPU 執行一條指令所需的時間。傳統上，這個週期包含幾個基本階段：

1. Fetch (取指令)：從記憶體中讀取下一條指令。
2. Decode (解碼)：解析指令，確定要執行的操作。
3. Execute (執行)：執行指令的操作，可能涉及 ALU 計算、資料存取等。
4. Store (儲存)：將執行結果寫回記憶體或暫存器。
   有些模型可能將「儲存」步驟包含在執行階段，或者將其視為一個獨立的階段。但 fetch, decode, execute 是核心。將 store 視為一個獨立步驟也是常見的。因此，這個敘述可以被認為是正確的，儘管不同的模型在細節上可能略有差異。

b) cache level-1 is built into the processor chip, whereas cache level-2 is separate from the chip and on the motherboard.
記憶體層級結構（Memory Hierarchy）中，快取記憶體（Cache Memory）是 CPU 和主記憶體之間的高速緩衝。

• Level 1 Cache (L1 Cache)：通常是最小、最快、離 CPU 核心最近的快取，直接整合在 CPU 核心晶片內部。
• Level 2 Cache (L2 Cache)：比 L1 快取大，速度稍慢，通常也整合在 CPU 晶片內部，但可能與核心分離，或者與多個核心共享。
• Level 3 Cache (L3 Cache)：比 L2 快取更大，速度更慢，通常被多個 CPU 核心共享，並且也整合在 CPU 晶片內部。
• 主記憶體 (Main Memory, RAM)：比 L3 快取大且慢，位於主機板上。

題目中提到「cache level-2 is separate from the chip and on the motherboard」。這是不正確的。

本題考查程式碼的執行流程與變數值的變化，特別是迴圈的判斷條件和變數的更新。

程式碼逐步執行分析：

1. 初始化：
   i = 4
   目前 i 的值是 4。

2. 第一個 while 迴圈：
   while (i < 7):

   • 第一次迴圈判斷：i 是 4，4 < 7 為真。進入迴圈。
     • print(i)：印出 i 的值，即 4。
     • i = i + 2：i 變成 4 + 2 = 6。
   • 第二次迴圈判斷：i 是 6，6 < 7 為真。進入迴圈。
     • print(i)：印出 i 的值，即 6。
     • i = i + 2：i 變成 6 + 2 = 8。
   • 第三次迴圈判斷：i 是 8，8 < 7 為假。迴圈終止。

3. 第一個 while 迴圈結束後的 print(i)：
   print(i)：此時 i 的值是 8。印出 i 的值，即 8。

本題考查 Java 程式碼中陣列（array）和計數器（counter）的使用，以及物件導向概念中物件的狀態。

程式碼中有一個 StackExample 類別，它有一個整數陣列 StackEntry (大小為 10) 和一個整數計數器 StackCnt (初始值為 0)。push 方法用於將一個新元素添加到 StackEntry 陣列中，並遞增 StackCnt。StackCnt 充當陣列中下一個可用位置的索引。

題目中宣告了 StackGroup Stack1, Stack2;。然而，程式碼定義的是 StackExample 類別，而 StackGroup 是一個介面（interface）或父類別（superclass）。假設 Stack1 和 Stack2 是 StackExample 類別的實例（instances），並且它們各自維護自己獨立的 StackEntry 陣列和 StackCnt 計數器。
（註：若 StackGroup 是介面，則 Stack1 和 Stack2 必須被實例化為 StackExample 或實現 StackGroup 的其他類別。這裡我們假設它們是 StackExample 的實例。）

假設 Stack1 和 Stack2 是 StackExample 的獨立實例。

初始狀態：
每個 StackExample 實例都將有：

• StackEntry 陣列，大小為 10，所有元素初始為 0。
• StackCnt = 0。

執行語句：

1. Stack1.push(1);

   • Stack1 的 StackCnt 是 0。
   • 0 < 10 為真。
   • StackEntry[0] = 1; (將 1 放入 StackEntry 的第一個位置)
   • StackCnt++，Stack1 的 StackCnt 變為 1。
   • Stack1 的狀態：StackEntry = {1, 0, 0, ..., 0}, StackCnt = 1。

2. Stack2.push(5);

   • Stack2 的 StackCnt 是 0。
   • 0 < 10 為真。
   • StackEntry[0] = 5; (將 5 放入 StackEntry 的第一個位置)
   • StackCnt++，Stack2 的 StackCnt 變為 1。
   • Stack2 的狀態：StackEntry = {5, 0, 0, ..., 0}, StackCnt = 1。

核心觀念

本題考查語意網（semantic net）中動作事件的角色表示：

• agent：動作的執行者。
• object：動作作用的對象。
• type：動作的類型或動詞。

圖中央的 Action 代表「打排球」這個動作事件。

解題方法

句子為「John plays volleyball」，依語意角色拆解：

1. 執行動作者是 John，因此 agent 連接 John。
2. 動作作用的對象是 volleyball，因此 object 連接 volleyball。
3. 動作類型是 play，因此 type 應填 play；若依句子原本的時態呈現，也可寫成 plays。

本題考查二元樹的遍歷（traversal）演算法，分別是前序遍歷（pre-order traversal）和中序遍歷（in-order traversal）。

圖示是一個二元樹，節點標記如下：
根節點：A
A 的左子樹：B (左子節點), C (右子節點)
B 的左子節點：D
C 的左子節點：E, C 的右子節點：F
E 的左子節點：G, E 的右子節點：H

樹結構如下：
A
/
B C
/ /
D E F
/
G H

遍歷演算法定義：

• 前序遍歷 (Pre-order Traversal)：訪客節點 (Visit Node) -> 遍歷左子樹 (Traverse Left Subtree) -> 遍歷右子樹 (Traverse Right Subtree)。 順序：根-左-右。
• 中序遍歷 (In-order Traversal)：遍歷左子樹 (Traverse Left Subtree) -> 訪客節點 (Visit Node) -> 遍歷右子樹 (Traverse Right Subtree)。 順序：左-根-右。

計算 (a) 前序遍歷 (Pre-order Traversal):
按照 根-左-右 的順序：

1. 訪客 A。輸出：A
2. 遍歷 A 的左子樹：
   1. 訪客 B。輸出：B
   2. 遍歷 B 的左子樹：
      1. 訪客 D。輸出：D
      2. B 的左子樹已遍歷完畢。
   3. 遍歷 B 的右子樹：B 沒有右子節點。
   4. B 的左子樹已遍歷完畢。
3. 遍歷 A 的右子樹：
   1. 訪客 C。輸出：C
   2. 遍歷 C 的左子樹：
      1. 訪客 E。輸出：E
      2. 遍歷 E 的左子樹：
         1. 訪客 G。輸出：G
         2. E 的左子樹已遍歷完畢。
      3. 遍歷 E 的右子樹：
         1. 訪客 H。輸出：H

本題考查兩種常見的排序演算法：合併排序（Merge Sort）和插入排序（Insertion Sort）。

給定的陣列是：[3, 5, 7, 9, 4, 8, 1, 4]

a) Perform a merge sort and explain the processes (4%)

合併排序 (Merge Sort) 是一種分治（Divide and Conquer）演算法。它的基本思想是：

1. 分解 (Divide)：將待排序的陣列分成兩半，然後遞迴地對這兩半分別進行合併排序，直到子陣列的大小為 1（單一元素的陣列自然是有序的）。
2. 合併 (Conquer)：將兩個已排序的子陣列合併成一個已排序的陣列。

過程解釋與步驟：

原始陣列：[3, 5, 7, 9, 4, 8, 1, 4]

第一階段：分解

• [3, 5, 7, 9] 和 [4, 8, 1, 4]
  • [3, 5] 和 [7, 9]
    • [3] 和 [5] -> 合併 [3, 5]
    • [7] 和 [9] -> 合併 [7, 9]
  • [4, 8] 和 [1, 4]
    • [4] 和 [8] -> 合併 [4, 8]
    • [1] 和 [4] -> 合併 [1, 4]

第二階段：合併

• 合併 [3, 5] 和 [7, 9]：
  • 比較 3 和 7，取 3。
  • 比較 5 和 7，取 5。
  • 比較 null 和 7，取 7。
  • 比較 null 和 9，取 9。
  • 結果：[3, 5, 7, 9]
• 合併 [4, 8] 和 [1, 4]：
  • 比較 4 和 1，取 1。
  • 比較 4 和 4，取 4。
  • 比較 4 和 8，取 4。
  • 比較 null 和 8，取 8。
  • 結果：[1, 4, 4, 8]

第三階段：最終合併

• 合併 [3, 5, 7, 9] 和 [1, 4, 4, 8]：
  • 比較 3 和 1，取 1。
  • 比較 3 和 4，取 3。
  • 比較 5 和 4，取 4。
  • 比較 5 和 4，取 4。
  • 比較 5 和 8，取 5。
  • 比較 7 和 8，取 7。
  • 比較 9 和 8，取 8。
  • 比較 null 和 9，取 9。
  • 結果：[1, 3, 4, 4, 5, 7, 8, 9]

合併排序過程總結：

1. 將陣列不斷對半分，直到每個子陣列只有一個元素。
2. 從最小的子陣列開始，兩兩合併並排序。
3. 重複合併和排序，直到整個陣列被排序。

最終排序結果： [1, 3, 4, 4, 5, 7, 8, 9]

---

b) Perform an insertion sort and explain the processes (4%)

插入排序 (Insertion Sort) 是一種簡單的排序演算法。它將陣列分成已排序和未排序兩部分。一次，它從未排序的部分取一個元素，並將其插入到已排序部分的正確位置。

過程解釋與步驟：

原始陣列：[3, 5, 7, 9, 4, 8, 1, 4]

本題考查關聯式資料庫（SQL）與非關聯式資料庫（NoSQL）的比較。

a) definition (4%)

• SQL (Structured Query Language) Databases:

  • 也稱為關聯式資料庫 (Relational Databases)。
  • 基於關聯模型，資料儲存在具有預定義結構的表格（tables）中。
  • 表格由行（rows，代表記錄）和列（columns，代表屬性）組成，表格之間可以透過鍵（keys）建立關聯。
  • 使用 SQL 語言進行查詢和操作。
  • 嚴格遵循 ACID (Atomicity, Consistency, Isolation, Durability) 原則。

• NoSQL (Not Only SQL) Databases:

  • 非關聯式資料庫，不遵循傳統的表格結構。
  • 旨在處理大量、多樣化、快速變化的資料。
  • 通常採用 BASE (Basically Available, Soft state, Eventually consistent) 模型，強調可用性和最終一致性，而非嚴格的 ACID。
  • 有多種類型，如鍵值儲存 (Key-Value Stores)、文件導向 (Document-Oriented)、列導向 (Column-Oriented)、圖形資料庫 (Graph Databases)。

b) scalability (4%)

• SQL Databases:

  • 垂直擴展 (Vertical Scaling / Scale-up)：這是傳統 SQL 資料庫的主要擴展方式。透過升級硬體（如增加 CPU、RAM、儲存空間）來提升單一伺服器的處理能力。
  • 水平擴展 (Horizontal Scaling / Scale-out)：在傳統關聯式資料庫中實現水平擴展（如分片、複製）相對複雜，需要額外的工具和複雜的設計。在處理極大規模資料集時，可能面臨挑戰。

• NoSQL Databases:

  • 水平擴展 (Horizontal Scaling / Scale-out)：這是 NoSQL 資料庫的核心優勢。它們被設計成可以在多台伺服器上分佈式運行，可以透過增加更多伺服器來處理不斷增長的資料量和流量。這使得它們在處理大數據時具有顯著的優勢。

c) structure (4%)

• SQL Databases:

  • 結構化 (Structured)：資料具有固定的、預定義的結構（schema）。表格的欄位、資料類型和約束在創建時就已確定。
  • 模式固定 (Schema-on-write)：資料在寫入資料庫之前，必須符合預定義的結構。

• NoSQL Databases:

  • 半結構化或無結構 (Semi-structured or Unstructured)：資料結構可以非常靈活，甚至可以在運行時動態改變。