108 年 國立中山大學資訊管理學系碩士班甲組《計算機概論》

這題主要考驗函數的成長級別比較。我們需要判斷哪一個函數在 $n$ 趨近無窮大時，成長速度最快。

函數成長級別的比較，通常可以透過對數或觀察其指數來判斷。

選項 A 是 $n \log n$。
選項 B 是 $\frac{n \log n}{\log \log n}$。
選項 C 是 $n^{\sqrt{\log n}}$。
選項 D 是 $n^{100}$。

我們來比較這些函數的成長速度：

1. 比較 A 和 B：$\frac{n \log n}{\log \log n}$ 相較於 $n \log n$，分母有一個 $\log \log n$，這個值在 $n$ 趨近無窮大時也會趨近無窮大，所以 B 的成長速度比 A 慢。
2. 比較 A 和 D：$n^{100}$ 的指數是常數 100，而 $n \log n$ 的指數是 $\log n$ (隨著 $n$ 變大而變大)。因此，$n^{100}$ 的成長速度比 $n \log n$ 快。

這題考驗對惡意軟體 (malware) 的基本認識。我們逐一分析每個選項：

A. A computer might be infected without connecting to a network：
這是正確的。即使沒有連網，惡意軟體也可以透過 USB 隨身碟、外部儲存裝置、光碟等媒介傳播。

B. Malware might not be an executable file：
這是正確的。惡意軟體的形式多樣，除了可執行檔 (.exe, .com 等)，還包括腳本檔 (.vbs, .js)、文件中的巨集、甚至是單純的資料檔案（如圖片、PDF，利用漏洞來執行惡意程式碼）。

C. If a machine in a LAN has been infected, the machines in the same LAN might be infected.：
這是正確的。

這題考驗對 CPU 內部組件功能及其在指令執行週期中的角色的理解。CPU 的基本指令執行週期通常包含以下幾個階段：

1. Fetch (擷取)：從記憶體中取出下一條指令。
2. Decode (解碼)：解析指令，確定要執行的操作以及操作數。
3. Execute (執行)：執行指令所要求的操作。
4. Store (儲存)：將執行結果寫回記憶體或暫存器。

題目問的是哪個組件「執行」指令。

• CU (Control Unit)：控制單元。負責協調和指揮 CPU 內部的各個組件，發出控制信號，控制指令的擷取、解碼、執行和儲存等步驟。它決定 CPU 執行什麼，但不執行算術或邏輯運算。

這題考驗對密碼學中對稱式加密與非對稱式加密的理解。

A. Symmetric encryption system requires one secret key to perform encryption and decryption.
這是對稱式加密的定義。加密和解密使用同一把金鑰。此敘述正確。

B. Asymmetric encryption system requires one key pair to perform encryption and decryption.
這是非對稱式加密的定義。非對稱式加密使用一對金鑰：公鑰 (public key) 和私鑰 (private key)。通常，用公鑰加密的訊息只能用對應的私鑰解密，反之亦然。此敘述正確。

C. With the knowledge of a public key, it is hard to know the associated private key.
這是非對稱式加密的基礎。

這題考驗對網路協定堆疊 (protocol stack) 中常見協定的理解。

A. ARP is used for finding the MAC address of an IP address, so ARP is a protocol over IP.
ARP (Address Resolution Protocol) 的確是用來將 IP 位址解析成 MAC 位址的。然而，ARP 協定本身是運行在資料鏈結層 (Data Link Layer) 之上的，它被封裝在乙太網路影格 (Ethernet frame) 中傳輸，而不是被封裝在 IP 封包 (IP packet) 中。因此，ARP 協定並非運行在 IP 層之上 (protocol over IP)。它更像是 IP 層的輔助協定，用於 IP 層與資料鏈結層之間的轉換。所以這個敘述是 FALSE。

B. DNS queries are transmitted through UDP.
DNS (Domain Name System) 的查詢通常使用 UDP (User Datagram Protocol) 協定，因為 DNS 查詢通常是短暫且需要快速回應的

這題考驗對 TCP/IP 協定堆疊 (protocol stack) 的認識。TCP/IP 模型與 OSI 模型有所不同，但通常包含以下幾個主要的層級：

1. 應用層 (Application Layer)：提供網路應用程式介面，例如 HTTP, FTP, SMTP, DNS 等。
2. 傳輸層 (Transport Layer)：負責端對端 (end-to-end) 的數據傳輸，提供可靠或不可靠的服務，主要協定是 TCP 和 UDP。
3. 網路層 (Network Layer)：負責 IP 位址的路由和封包的轉送，主要協定是 IP。

核心觀念

• 子網路遮罩（network mask）：在 IPv4 位址中，用 32 位元的二進位序列來表示哪部份是網路位址（用 1 表示），哪部份是主機位址（用 0 表示）。
• 連續 1 / 連續 0：合法的子網路遮罩必須是前面若干個 1，其後全為 0，不能出現 1、0、1 交錯的情況。
• 類別位址（classful）：Class A、B、C 的預設遮罩分別為 255.0.0.0、255.255.0.0、255.255.255.0。
• 遮罩長度：以「/n」表示前 n 位為 1（即子網路長度），取值範圍 $0\le n \le 32$，且可依需求調整（VLSM）。

---

解題方法
針對每個選項，檢驗其描述是否符合上述定義與規則。若敘述違背連續 1/0 的規則或預設值錯誤，即為 FALSE。逐項驗證即可得出唯一錯誤選項。

---

選項分析

選項	內容	判斷	理由
A	The first bit of a network mask must be 1	正確	合法遮罩必須以 1 開頭，否則無法表示任何網路位元。
B	The lowest bit of a network mask must be 0	正確	只要遮罩長度未達 32（即非 /32），最右側一定為 0；

這題考驗對虛擬記憶體分頁置換演算法中 LRU (Least Recently Used) 的理解與應用。

題目給定：

• 記憶體框 (frames) 數量：3
• 頁面參考字串 (reference string)：abcgabadbcabacd
• 置換演算法：LRU
• 初始狀態：所有記憶體框都是空的 (empty)

我們需要模擬頁面載入和置換的過程，並計算頁面錯誤 (page fault) 的次數。

LRU 演算法的規則：當需要載入一個不在記憶體中的頁面，而記憶體已滿時，會將「最近最少使用」的頁面替換出去。

模擬過程：
我們用一個列表來表示記憶體中的三個框，並記錄每個框中頁面的使用順序，最右邊是最近使用的，最左邊是最少使用的。

參考字串	記憶體框 (LRU -> MRU)	頁面錯誤 (Page Fault)	說明
	[]		初始狀態：記憶體為空
a	[a]	Yes	載入 'a'
b	[a, b]	Yes	載入 'b'
c	[a, b, c]	Yes	載入 'c' (記憶體滿)
g	[b, c, g]	Yes	'g' 不在記憶體中。LRU 是 'a'，將 'a' 替換為 'g'
a	[c, g, a]	Yes	'a' 不在記憶體中。LRU 是 'b'，將 'b' 替換為 'a'
b	[g, a, b]	Yes	'b' 不在記憶體中。LRU 是 'c'，將 'c' 替換為 'b'
a	[g, b, a]	No	'a' 在記憶體中。將 'a' 移到最右邊 (MRU)。記憶體變為 [g, b, a]
d	[a, b, d]	Yes	'd' 不在記憶體中。LRU 是 'g'，將 'g' 替換為 'd'

核心觀念
死結（deadlock）是指一組行程因互相持有且等待對方釋放資源而無法繼續執行的情形。產生死結必須同時滿足四大必要條件：

1. 互斥（Mutual Exclusion）：資源同時只能被一個行程使用。
2. 保持且等待（Hold and Wait）：行程已持有至少一個資源，同時又在等待其他資源。
3. 不可搶奪（No Preemption）：已分配的資源在未完成前不能被強制回收。
4. 循環等待（Circular Wait）：形成一條行程 → 資源 → 行程 … 的閉環。

資源配置圖（Resource‑Allocation Graph, RAG）用節點表示行程與資源，箭頭分別代表「請求」（request edge）與「分配」（assignment edge）。在 單一實例 的資源情況下，圖中出現**循環（circle）**即等同於死結；若資源有多個實例，循環只能說明可能發生死結，未必真的發生。

解題方法
針對選擇題，只要檢視每個敘述是否符合上述概念即可。判斷順序：

1. 先判斷敘述是否直接涉及四大必要條件或其衍生結論。
2. 檢查敘述是否過於絕對（如「一定」或「永不」），若有則需尋找例外情況。
3. 以資源配置圖的性質（單實例 vs 多實例）為依據，辨別「循環即死結」的正確性。

選項分析

這題考驗對 TCP (Transmission Control Protocol) 協定特性的理解。

A. Congestion control ensures that sender won't overflow receiver's buffer by transmitting too much or too fast.
這句話描述的是「流量控制 (Flow Control)」，而不是「壅塞控制 (Congestion Control)」。

• 流量控制：由接收端透過告知發送端其接收緩衝區 (receiver buffer) 的大小，來防止發送端發送過多數據，以免接收端緩衝區溢出。
• 壅塞控制：當網路本身出現壅塞時，TCP 會減慢發送速率，以減輕網路的負擔。

因此，這個敘述將壅塞控制的功能描述為流量控制的功能，是錯誤的。

B. The receiver side of a TCP connection maintains a buffer storing the data received; the sender side has a buffer, too.
這是正確的。

• 接收端緩衝區 (Receiver Buffer)：用於暫存接收到的數據，直到應用程式準備好讀取。這是流量控制的基礎。
• 發送端緩衝區 (Sender Buffer)：TCP 發送端也有緩衝區，用於暫存即將發送或已發送但尚未被確認 (ACK) 的數據。這些數據在收到 ACK 後才會從緩衝區中移除。

這題定義了一個二進位字串上的二元運算 $\oplus$，並要求判斷其性質。

運算定義： $s \oplus s'$ 是將字串 $s$ 的最後一個字元替換為字串 $s'$ 的最後一個字元。
範例：$01001 \oplus 110 = 01000$。
在這裡，$s = 01001$，其最後一個字元是 '1'。
$s' = 110$，其最後一個字元是 '0'。
將 $s$ 的最後一個字元 '1' 替換為 '0'，得到 $01000$。

我們要判斷以下性質：
A. 結合律 (Associative)：$(s \oplus s') \oplus s'' = s \oplus (s' \oplus s'')$
B. 交換律 (Commutative)：$s \oplus s' = s' \oplus s$
C. 特定運算結果：$010010 \oplus 1111110 = 0100010$

我們來逐一驗證：

驗證交換律 (Commutative)：
$s \oplus s'$ 的結果是將 $s$ 的最後一個字元換成 $s'$ 的最後一個字元。
$s' \oplus s$ 的結果是將 $s'$ 的最後一個字元換成 $s$ 的最後一個字元。
除非 $s$ 和 $s'$ 的最後一個字元相同，否則 $s \oplus s' \neq s' \oplus s$。
例如：
設 $s = 010$，最後一個字元是 '0'。
設 $s' = 111$，最後一個字元是 '1'。
$s \oplus s' = 011$ (將 $s$ 的 '0' 換成 $s'$ 的 '1')
$s' \oplus s = 110$ (將 $s'$ 的 '1' 換成 $s$ 的 '0')
$011 \neq 110$。
所以，此運算不是交換律的。選項 B 錯誤。

驗證結合律 (Associative)：
我們需要檢查 $(s \oplus s') \oplus s''$ 是否等於 $s \oplus (s' \oplus s'')$。
設 $s = s_1 s_2 ... s_{n-1} s_n$
設 $s' = s'_1 s'_2 ... s'_{m-1} s'_m$
設 $s'' = s''_1 s''_2 ... s''_{p-1} s''_p$

$s \oplus s'$ 的結果是 $s_1 s_2 ... s_{n-1} s'_m$。
$(s \oplus s') \oplus s''$ 的結果是將 $(s \oplus s')$ 的最後一個字元（即 $s'_m$）替換成 $s''$ 的最後一個字元（即 $s''_p$）。
所以，$(s \oplus s') \oplus s'' = s_1 s_2 ... s_{n-1} s''_p$。

這題考驗對雲端運算 (Cloud Computing) 基本概念、服務模式以及常見應用的理解。

A. Cloud computing is a type of distributed network environments.
雲端運算的核心就是將計算資源（伺服器、儲存、網路等）集中化，並透過網路（通常是網際網路）提供給使用者。這些資源本身通常是分散在不同的地理位置的數據中心，並透過網路互相連接和協調工作。因此，雲端運算確實是一種分散式的網路環境。此敘述正確。

B. SaaS (Software as a Service) is a type of business models in cloud computing.
SaaS 是雲端運算的三種主要服務模式之一 (IaaS, PaaS, SaaS)。它是一種透過網路提供軟體應用程式的商業模式，使用者無需安裝、維護軟體，只需透過瀏覽器或其他客戶端存取即可。此敘述正確。

C. Google's Gmail is an example of SaaS.
Gmail 是一個典型的 SaaS 應用。使用者透過網頁瀏覽器或行動應用程式存取 Gmail 服務，而 Google 負責伺服器、軟體、維護和更新。使用者只需專注於使用郵件功能。此敘述正確。

這題考驗對 TLS/SSL (Transport Layer Security / Secure Sockets Layer) 協定的理解。

A. TLS/SSL is a security protocol that provides end-to-end communication security over TCP.
TLS/SSL 運行在 TCP 和應用層之間，為應用層協定（如 HTTP, FTP）提供一個安全的通道。它確實透過加密、驗證和完整性檢查來確保端到端 (end-to-end) 的通訊安全。此敘述正確。

B. TLS/SSL applies asymmetric cryptography to ensure user authentication.
TLS/SSL 的握手 (handshake) 過程會用到非對稱式加密（公鑰加密）來進行身份驗證。例如，伺服器會使用其私鑰來簽署證書的一部分，而客戶端則使用伺服器的公鑰（來自證書）來驗證簽名，從而確認伺服器的身份。

這題考驗對「引導 (bootstrap)」程式的理解。引導程式是電腦啟動過程中執行的第一段程式碼。

A. A bootstrap is the program which resides in ROM.
引導程式通常儲存在電腦的 ROM (Read-Only Memory) 或 EEPROM (Electrically Erasable Programmable Read-Only Memory) 等非揮發性記憶體中，以便在系統通電後，CPU 能夠從固定位置讀取並執行。此敘述正確。

B. A bootstrap is to initialize the operating system during startup.

這題考驗對電腦硬體基本組件及其分類的理解。

A. All I/O devices use a common device controller to communicate with the operating system.
這是錯誤的。不同的 I/O 設備（如硬碟、顯示卡、網路卡、鍵盤、滑鼠）通常需要專門的或不同種類的設備控制器 (device controller) 來與作業系統溝通。例如，硬碟有硬碟控制器，顯示卡有顯示控制器。它們的通訊方式和控制訊號都不同。雖然作業系統提供了統一的介面（透過驅動程式），但底層的硬體控制器是各異的。

B. I/O devices are peripherals of a computer system.
I/O (Input/Output) 設備，如鍵盤、滑鼠、顯示器、印表機、硬碟等，都是電腦系統的外部設備，用於與使用者或外部環境進行數據交換。它們被統稱為電腦的周邊設備 (peripheral devices)。此敘述正確。

核心觀念

• 二進位補碼 (Two’s complement)：用於表示有號整數的常用方式。
  • 正數的補碼＝原始二進位表示。
  • 負數的補碼＝先取一的補碼（逐位取反），再加一。
• 一的補碼 (One’s complement)：負數的表示方法，直接取正數的逐位取反。
• 位元需求：
  • 在 N 位 的二補碼系統，可表示範圍 $[-2^{N-1},\;2^{N-1}-1]$。
  • 在 N 位 的一補碼系統，可表示範圍 $[-(2^{N-1}-1),\;(2^{N-1}-1)]$，最負的數無法以 $-2^{N-1}$ 表示，需要額外一位。

---

解題方法

1. 先釐清每個選項的敘述是否符合上述定義與位元需求。
2. 針對每個選項，列出所涉及的運算或位元數，驗證其正確性。
3. 若有「需要 N+2 位」之類的位元計算，代入小例 (如 $N=1,2,3$) 估算，確認通式是否成立。
4. 以二補碼的產生流程（取一補碼再加一）檢查選項 D。

---

選項分析

選項	內容	判斷與說明
A	Two's complement of 36 is 1011011	36 的二進位為 $100100_2$（最少 6 位）。若使用 7 位表示，正數 36 為 0100100。1011011 的最高位是 1，代表負數。

這題考驗對多道程式設計 (Multiprogramming) 和多處理機系統 (Multiprocessing) 的區別與理解。

A. Multiprogramming indicates that there are multiple processes residing in memory.
多道程式設計的核心概念就是允許多個程式（進程, process）同時存在於主記憶體中。當一個進程因為等待 I/O 操作而暫停時，CPU 可以切換到另一個就緒的進程繼續執行，從而提高 CPU 的利用率。所以，多個進程同時存在於記憶體是多道程式設計的前提。此敘述正確。

B. Multiprocessing system refers that there are multiple CPUs within a computer system.
多處理機系統 (Multiprocessing system) 的定義就是指一台電腦系統中包含兩個或兩個以上的中央處理器 (CPU)。這使得系統能夠真正地並行執行多個進程。

這題考驗對圖論中計算所有節點對之間最短路徑的時間複雜度。

題目給定：

• 一個有向圖 G (V, E)，其中 V 是節點集合，E 是邊集合。
• 圖以矩陣形式表示，這通常意味著鄰接矩陣 (adjacency matrix)。
  • 如果圖有 V 個節點，那麼鄰接矩陣的大小是 $V \times V$。
  • 儲存這個矩陣需要 $O(V^2)$ 的空間。
  • 檢查兩節點之間是否有邊，或邊的權重，時間複雜度是 $O(1)$。

問題是：找出所有節點對之間的最短路徑 (all-pairs shortest path) 的時間複雜度。

解決這個問題的經典演算法有：

1. Floyd-Warshall 演算法：

   • 這是一個動態規劃演算法，用於找出圖中所有節點對之間的最短路徑。
   • 它處理的是加權圖（可以有負權邊，但不能有負權環）。
   • 時間複雜度為 $O(V^3)$。
   • 空間複雜度為 $O(V^2)$（用於儲存距離矩陣）。

2. Dijkstra 演算法：

   • Dijkstra 演算法用於找出從單一源節點到所有其他節點的最短路徑 (single-source shortest path)。
   • 它適用於權重非負的圖。
   • 如果使用優先佇列 (priority queue)，其時間複雜度為 $O(E \log V)$ 或 $O(E + V \log V)$（取決於優先佇列的實現）。
   • 如果圖是稠密的 (dense graph)，即 $E \approx V^2$，則複雜度為 $O(V^2 \log V)$ 或 $O(V^2)$（如果使用簡單陣列或 Fibonacci heap）。
   • 要找出所有節點對的最短路徑，我們需要對每個節點執行一次 Dijkstra 演算法。

核心觀念

• 前綴 (Prefix) 記法的特點是「運算子在前、運算元在後」。
• 由前綴式轉換成中綴式，只要依序讀取符號，對於運算子必須先取得其兩個左（第一）與右（第二）運算元。
• 轉換過程常用 遞迴 或 右至左堆疊 兩種方式，最關鍵的是保留運算子與運算元的相對順序，且在寫出中綴式時遵守算術的 運算子優先權（* / 高於 + -），不必額外加上括號。

---

解題方法

1. 先把字元切開：題目給的前綴式

$-\;A\;+\;*\;/\;B\;C\;D\;E$

依序為 - , A , + , * , / , B , C , D , E。

2. 使用遞迴解析（從左往右讀）

   • 讀到 - → 為運算子，必須解析兩個子樹。
   • 左子樹：下一個符號 A 為 operand → A。
   • 右子樹：接下來的 + 為運算子，繼續往下解析兩個子樹。

3. 解析 + 的左子樹

   • * 為運算子 → 解析其兩個子樹。
   • * 的左子樹：/ 為運算子 → 其左子樹 B、右子樹 C，得到 $B / C$。
   • * 的右子樹：D 為 operand → D。
   • 合併得到 $(B / C) * D$。

4. 解析 + 的右子樹

   • 下一個符號 E 為 operand → E。

5. 組合 +

   • 左子樹 $(B / C) * D$、右子樹 E →

$(B / C) * D + E$

6. 組合根 -
   • 左子樹 A、右子樹 $(B / C) * D + E$ →

這題考驗對程式碼中巢狀迴圈 (nested loop) 的執行過程以及變數累加的理解。

程式碼如下：

w = 0;
for (i = 0; i <= 5; i++)
  for (j = 0; j <= i; j++)
    w = w + 2;

我們需要計算變數 w 在迴圈結束後的最終值。
外層迴圈 for (i = 0; i <= 5; i++) 會執行 6 次，i 的值分別為 0, 1, 2, 3, 4, 5。
內層迴圈 for (j = 0; j <= i; j++) 的執行次數取決於外層迴圈變數 i 的值。
在每次內層迴圈的迭代中，w 的值會增加 2。

我們來計算內層迴圈總共執行的次數：

• 當 i = 0 時：j 從 0 迴圈到 0 (j <= 0)。內層迴圈執行 1 次。 w 增加 $1 \times 2 = 2$。
• 當 i = 1 時：j 從 0 迴圈到 1 (j <= 1)。內層迴圈執行 2 次。 w 增加 $2 \times 2 = 4$。
• 當 i = 2 時：j 從 0 迴圈到 2 (j <= 2)。內層迴圈執行 3 次。 w 增加 $3 \times 2 = 6$。
• 當 i = 3 時：j 從 0 迴圈到 3 (j <= 3)。內層迴圈執行 4 次。 w 增加 $4 \times 2 = 8$。

這題考驗對 Hadoop 分散式檔案系統 (HDFS) 的理解。

A. It is often used as an implementation of "data lake".
「資料湖 (Data Lake)」是一種儲存大量原始資料的儲存庫，HDFS 是 Hadoop 生態系統中的核心組件，它能夠儲存各種結構和非結構化的資料，因此常被用作資料湖的底層儲存系統。此敘述正確。

B. The data/slave node(s) keeps track of the locations of data blocks.
HDFS 的架構包含 NameNode (主節點) 和 DataNodes (從節點)。NameNode 負責管理檔案系統的元數據 (metadata)，包括檔案的命名空間、檔案的權限以及數據塊 (data blocks) 在哪些 DataNodes 上的位置資訊。DataNodes 則負責儲存實際的數據塊。

這題考驗對常見的深度學習 (Deep Learning) 框架的認識。

深度學習框架是為了簡化深度學習模型的開發、訓練和部署而設計的軟體庫或平台。它們通常提供張量運算、自動微分、GPU 加速等功能。

A. Tensorflow：由 Google 開發，是目前最流行和廣泛使用的深度學習框架之一。
B. MXNet：由亞馬遜開發，也是一個流行的深度學習框架。

這題考驗對深度學習 (Deep Learning) 的常見挑戰和限制的理解。

A. A trained model is generally considered a "black-box".
深度學習模型的決策過程往往難以解釋，尤其對於複雜的神經網路。我們可以看到輸入和輸出，但很難理解模型是如何做出決策的。這種「黑箱」特性是深度學習的一個重要挑戰，尤其在需要可解釋性的領域（如醫療、金融）。此敘述是深度學習的常見挑戰。

B. It usually needs massive computation.
深度學習模型的訓練通常需要處理大量的數據，並進行複雜的計算（如矩陣乘法、梯度下降）。這需要強大的計算能力，例如高性能的 GPU。因此，計算資源的需求是深度學習的一個主要限制。此敘述是深度學習的常見挑戰。

C. It requires a lot of feature engineering.

這題考驗對大數據分析 (Big Data Analytics) 近期趨勢的了解。

A. The adoption of "data lake".
資料湖 (Data Lake) 是一種集中式的儲存庫，可以儲存大量的結構化、半結構化和非結構化數據。它允許企業以原始格式儲存數據，並在需要時進行分析，這已成為大數據儲存和管理的重要趨勢。此敘述是近期趨勢。

B. The rise of heterogeneous computing.
異質運算 (Heterogeneous Computing) 指的是利用不同類型的計算單元（如 CPU、GPU、FPGA、ASIC 等）來協同工作，以優化計算性能和效率。在大數據分析中，GPU 等加速器被廣泛應用於加速機器學習、深度學習等計算密集型任務。此敘述是近期趨勢。

C. The popularization of in-memory analytics.
記憶體內分析 (In-memory Analytics) 指的是將數據儲存在主記憶體 (RAM) 中進行分析，而不是儲存在硬碟等傳統儲存介質上。

這題考驗對大規模並行處理 (Massively Parallel Processing, MPP) 分析資料庫系統的認識。

MPP 架構的資料庫系統通常包含大量的節點 (nodes)，每個節點都有自己的 CPU、記憶體和磁碟，並且節點之間透過高速網路連接。這種架構非常適合處理海量數據的分析查詢，因為它可以將查詢任務分解並分佈到多個節點上並行執行。

A. Vertica：Vertica 是一個知名的 MPP 資料庫，專為大規模數據分析而設計。
B. Aster：Aster Data (現已被 Teradata 收購) 也是一個 MPP 資料庫系統。

這題考驗對 C 語言中鏈結串列 (linked list) 操作的理解，特別是如何在鏈結串列的末端添加新節點。

假設我們有一個非空的鏈結串列，並且 lastPtr 指向鏈結串列的最後一個節點。newPtr 指向要插入的新節點。每個節點都有一個 nextPtr 成員，指向下一個節點。

我們要將 newPtr 指向的節點添加到 lastPtr 所指向節點的後面，並更新 lastPtr 指向新的最後一個節點。

操作步驟如下：

1. 將原鏈結串列的最後一個節點 (lastPtr) 的 nextPtr 指向新的節點 (newPtr)。這將新節點連接到鏈結串列的末尾。
   lastPtr->nextPtr = newPtr;
2. 更新 lastPtr，使其指向新的鏈結串列的最後一個節點，也就是 newPtr。
   lastPtr = newPtr;

現在我們檢查選項：

A.
lastPtr = newPtr; // 這會讓 lastPtr 指向新節點，但原來的鏈結串列末端還沒連到新節點。

這題考驗對 SQL (Structured Query Language) 中 UPDATE 語句的語法和邏輯的理解。

題目要求：將 account 資料表中，餘額 (balance) 大於 50,000 的所有帳戶，其餘額增加 2% 的利息。

我們來分析各個選項：

A. UPDATE account a SET a.balance = a.balance * 1.02 WHERE a.balance > 50000

• UPDATE account a: 指定要更新的資料表是 account，並給它一個別名 a。
• SET a.balance = a.balance * 1.02: 設定 balance 欄位的新值。a.balance * 1.02 表示將原餘額乘以 1.02，這相當於增加了 2% 的利息。
• WHERE a.balance > 50000: 指定更新的條件，只更新 balance 大於 50,000 的記錄。
  這個語句的語法和邏輯都是正確的，完全符合題目要求。

B. UPDATE account a SET a.balance += a.balance * 1.02 IF a.balance > 50000

這題考驗對 C 語言中結構 (struct) 作為函數參數傳遞方式的理解。

在 C 語言中，結構 (struct) 是一種複合資料型別，可以包含多個不同類型的成員。將結構傳遞給函數有以下幾種方式：

A. Pass by structure members (傳遞結構成員)：
可以單獨將結構中的某個或某些成員作為參數傳遞給函數。例如，如果一個結構 Person 有 name 和 age 成員，我們可以傳遞 person.age 給一個函數。這種方式實際上是傳遞成員的值。

B. Pass entire structure by value (傳遞整個結構，傳值)：
可以直接將整個結構變數作為函數參數傳遞。

這題考驗對 C 語言中陣列 (array) 邊界檢查 (bounds checking) 的理解。

在 C 語言中，陣列的邊界檢查不是由編譯器或執行時自動完成的。這意味著，如果你嘗試存取一個陣列範圍之外的元素（例如，一個大小為 10 的陣列，你嘗試存取索引為 10 或 -1 的元素），C 語言不會拋出錯誤或顯示「Syntax error」。

相反，存取陣列邊界之外的記憶體空間，會導致：

• 讀取：可能會讀取到該記憶體位置上的任意值。這些值可能來自其他變數、堆疊中的其他數據，或者是未初始化的記憶體。

這題考驗對 Python 3 中條件判斷語句的認識。

Python 3 中的條件判斷語句用於實現程式的選擇結構，即根據不同的條件執行不同的程式碼塊。

A. if elif ... else：這是 Python 中實現多重選擇 (multiple selections) 的標準語法。if 語句檢查第一個條件，如果為真則執行對應的程式碼塊。如果為假，則檢查 elif（else if）語句的條件，依此類推。最後的 else 語句是可選的，如果前面的所有條件都為假，則執行 else 的程式碼塊。這個結構可以處理多個互斥的條件。

這題考驗對 C 語言中三元運算符 (ternary operator ?:) 的嵌套使用以及程式輸出結果的判斷。

程式碼分析：

#include <stdio.h>

int main() {
  int k, n = 20;
  // 關鍵在於這行：k 的值如何確定
  k = (n > 5 ? (n <= 10 ? 10: 20) :50);
  // 接著打印 n 的值
  printf("%d\n", n);
  return(0);
}

1. 變數初始化：

   • int n = 20;：變數 n 被初始化為 20。
   • int k;：變數 k 被宣告，但尚未初始化。

2. 三元運算符計算 k 的值：
   k = (n > 5 ? (n <= 10 ? 10: 20) :50);
   我們一步步解析這個嵌套的三元運算符：

核心觀念

• 陣列 (Array)：在記憶體中以連續的位址排列，每個元素大小相同，故稱為密集 (dense) 結構。
• 鏈結串列 (Linked List)：每個節點 (node) 包含資料 (data)與指向下一節點的指標 (pointer)。節點本身可散佈於任意記憶體位置，彼此不必相鄰。
• 指標 (Pointer)：在 C 語言中，指標變數儲存的是位址 (address)，而非實際資料本身。指標可指向任意型別的變數或結構體。

---

解題方法
此題屬於概念辨識題，需對四個敘述分別驗證其正確性。檢驗步驟：

1. 判斷陣列是否為密集結構 → 檢視陣列的記憶體配置特性。
2. 確認鏈結串列的資料元素是否需要相鄰儲存 → 依鏈結串列的實作方式判斷。
3. 檢查 C 語言指標的用途，特別是「存放下一筆資料」的說法是否符合指標本質。
4. 核對鏈結串列的定義是否與選項 D 相符。

若僅有一項敘述與實際概念相左，即為錯誤選項。

---

選項分析

• A. Arrays are dense data structures.

  • 陣列在記憶體中以連續位址排列，元素之間不留空洞，符合「密集」(dense) 的定義。
  • 結論：正確。

• B. Data elements in a linked list need not be stored in an adjacent space in memory.

這題考驗對程式語言分類，特別是函數式程式語言 (functional programming language) 的認識。

函數式程式語言的特點包括：

• 將計算視為數學函數的求值。
• 避免使用可變狀態 (mutable state) 和副作用 (side effects)。
• 強調純函數 (pure functions)，即對於相同的輸入，總是產生相同的輸出，且沒有副作用。
• 一等公民的函數 (first-class functions)，函數可以像變數一樣被傳遞、賦值和返回。

讓我們逐一分析選項：

A. R：R 語言主要用於統計計算和圖形展示。雖然它支援函數式編程的某些特性（如高階函數），但它也廣泛使用命令式和物件導向的編程風格，並且經常涉及副作用。它不被視為純粹的函數式程式語言，但可以被用來進行函數式編程。

B. Scala：Scala 是一種多範式程式語言，它結合了物件導向和函數式程式設計的特點。它對函數式編程有非常強的支持，例如不可變資料結構、高階函數、模式匹配等。

這題考驗對結構化數據 (structured data) 的理解。

結構化數據是指預先定義了資料模型，並且數據以易於查詢和分析的格式儲存的數據。通常，結構化數據具有明確的欄位、記錄和關係。

A. XML files：XML (Extensible Markup Language) 檔案使用標籤來定義數據的結構和層次。它是一種半結構化數據的表示方式，但其嚴格的標籤結構和層次關係使其可以被視為一種形式的結構化數據，尤其是在進行解析和查詢時。

B. Tabular data in relational databases：這是結構化數據的典型例子。關聯式資料庫中的數據是以表格 (table) 的形式儲存的，每個表格有定義好的欄位 (columns) 和記錄 (rows)，並且表格之間可能有關聯。這種數據模型非常明確，易於查詢和分析。

C. Text in emails：電子郵件的文本內容通常被認為是非結構化數據 (unstructured data)。雖然郵件有標題（如收件人、寄件人、主旨）和正文，但郵件正文的內容是自由格式的文本，其內部結構和含義對機器來說難以直接理解和分析，需要進一步的自然語言處理 (NLP) 技術。

這題考驗對不同資料結構特性的理解，以及如何利用它們來實現反向順序輸出。

題目情境：

• 有一系列客戶名稱，已按字母順序排序。
• 這些名稱儲存在某種資料結構中。
• 要求找出最簡單的方法來以反向字母順序列印這些名稱。

我們逐一分析每個資料結構的特性：

A. Stack (堆疊)：
堆疊是一種 LIFO (Last-In, First-Out) 的資料結構。如果我們將按字母順序排序的名稱依序壓入堆疊，那麼當我們再依序從堆疊中彈出 (pop) 時，元素的順序將會是 LIFO，也就是最後壓入的元素（字母順序最後的名稱）會先被彈出，接著是倒數第二個，依此類推。這正好是反向字母順序。
因此，堆疊是實現這個目標的一個非常簡單且直接的方法。

B. Binary Search Tree (二元搜尋樹)：
二元搜尋樹 (BST) 的中序遍歷 (in-order traversal) 會按字母順序（或數值順序）訪問節點。

這題考驗對 C/C++/Java 中基本資料型別的理解，以及它們在迴圈控制中的適用性。

迴圈控制（特別是計數迴圈，counting loop）通常需要一個變數來作為計數器。這個計數器需要滿足以下條件：

1. 能夠表示整數值。
2. 能夠進行遞增或遞減操作。
3. 能夠進行比較操作（如 i <= 5）。

我們來分析各個選項：

A. double：double 是浮點數 (floating-point number) 型別，用於表示帶有小數點的數字。雖然可以對 double 類型的變數進行加減運算和比較，但在控制計數迴圈時，使用浮點數作為計數器通常不是最佳選擇，原因如下：
* 精度問題：浮點數運算可能存在精度誤差，導致迴圈的終止條件判斷不準確，甚至可能導致無限迴圈或提前結束迴圈。

這題考驗對位元運算 (bitwise operations) 的理解，特別是如何用來操作特定位元。

「Turn off a particular bit」是指將某個位元從 1 變為 0，而其他位元保持不變。

我們來分析各個位元運算：

A. AND (位元 AND)：
x AND y 的結果，只有在 x 和 y 的對應位元都為 1 時，結果的該位元才為 1，否則為 0。
如果我們想將某個位元變成 0，我們可以將該位元與 0 進行 AND 運算 (bit AND 0 = 0)。
如果我們想讓某個位元保持不變，我們可以將該位元與 1 進行 AND 運算 (bit AND 1 = bit)。
因此，要將某個特定位元關閉（變成 0），我們可以與一個「遮罩 (mask)」進行 AND 運算。這個遮罩的目標位元是 0，而其他所有位元都是 1。
例如，假設我們要關閉數字 11011011 的第 3 位（從右邊算起，0-indexed）。
目標位是 1。我們需要一個遮罩，其第 3 位是 0，其他位是 1。
遮罩：11111011 (假設是 8 位元)。

這題考驗對 C/C++ 中陣列 (array) 和個別元素作為函數參數傳遞時的預設方式。

在 C/C++ 中：

1. 整個陣列 (Entire arrays)：
   當我們將一個陣列傳遞給函數時，實際上是傳遞了該陣列的第一個元素的位址。這意味著函數接收到的是一個指標，指向陣列的起始位置。這是一種「傳址 (pass by reference)」或稱為「傳指標 (pass by pointer)」的方式。在函數內部，可以透過這個指標來存取和修改原始陣列的所有元素。
   例如：

   void processArray(int arr[]) { // arr 實際上是一個 int*
       // ...
   }
   int myArray[10];
   processArray(myArray); // myArray decay to pointer to its first element
   

   因此，除非有特殊語法（如 C++ 的 std::array 或傳遞陣列的副本，這在 C 風格的陣列傳遞中不常見），整個陣列是「by-reference」傳遞的。

這題考驗對 SQL 語句中 UNION ALL 和 WHERE 子句的結合使用的理解，以及結果集的行數和欄數的計算。

首先，我們分析子查詢：
SELECT * FROM A UNION ALL SELECT * FROM B

• Table A:

  ID	V
  1	A
  3	X
  5	C

• Table B:

  ID	V
  3	X
  5	Y
  6	Z

• UNION ALL: 這個操作會將兩個查詢的結果集合併起來，並且保留所有行，包括重複的行。

  • 從 A 中選取的行：(1, A), (3, X), (5, C)
  • 從 B 中選取的行：(3, X), (5, Y), (6, Z)

  合併後的結果集 (在 UNION ALL 操作之後，WHERE 之前) 如下：

  ID	V
  1	A
  3	X
  5	C
  3	X
  5	Y
  6	Z

  這個中間結果集有 6 行。

這題考驗對 C/C++ 中指標 (pointer) 的基本定義。

指標 (pointer) 是一種特殊的變數，它的值是另一個變數的記憶體位址。
換句話說，指標「指向」記憶體中的某個位置。

我們來分析各個選項：

A. strings：字串 (string) 在 C/C++ 中通常表示為字元陣列 (char[]) 或字串指標 (char*)。指標本身可以指向字串的起始位置，但指標的值不是字串本身，而是字串的位址。