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

此題主要在考驗網路交換器（Network Switch）與路由器（Router）在轉送封包時所使用的資料結構。

網路交換器（Layer 2 Switch）主要根據 MAC 位址來決定封包的轉送路徑，它維護一個 MAC 位址對應埠號的表格，稱為 MAC 位址表（MAC Address Table）或稱轉送表格（Forwarding Table）。當交換器收到一個封包時，會查詢 MAC 位址表，找出目的 MAC 位址所連接的埠號，然後將封包從該埠號送出。

路由器（Router）則是在 Layer 3 運作，它根據 IP 位址來決定封包的轉送路徑，並維護一個路由表（Routing Table）。路由表包含了目的網路位址、下一跳位址（Next Hop）以及使用的介面等資訊。

此題考驗關於「加密」（Encryption）的基本定義。

加密是一種將原始資訊（明文，plaintext）轉換成無法辨識的密文（ciphertext）的過程，其目的是保護資訊的機密性，防止未經授權者讀取。這個轉換過程通常使用演算法（cipher）和金鑰（key）。

選項分析：
A. Transmission of information over secure lines to prevent illegal access.：這描述的是「安全傳輸」，例如使用 TLS/SSL，加密是安全傳輸的重要手段，但加密本身不直接等同於安全傳輸。

此題考驗對區塊鏈（Blockchain）中常見的共識機制（Consensus Mechanism）的了解。

共識機制是區塊鏈技術的核心，它確保區塊鏈網絡中的所有節點能夠就交易的有效性和區塊鏈的狀態達成一致。常見的共識機制包括：

• 工作量證明（Proof of Work, PoW）：參與者（礦工）需要解決一個計算上困難的數學難題，第一個解決難題的節點將獲得記帳權並創建新區塊。比特幣（Bitcoin）和早期以太坊（Ethereum）都使用 PoW。
• 權益證明（Proof of Stake, PoS）：參與者根據其持有的加密貨幣數量和時間來獲得記帳權。持有的越多，獲得記帳權的機率越大。
• 委託權益證明（Delegated Proof of Stake, DPoS）：持幣者將投票權委託給代表，由代表來進行記帳。

核心觀念

本題考查區塊鏈與數位資產的基本名詞。NFT 是 Non-fungible token 的縮寫，中文常譯為「非同質化代幣」或「非同質化 token」。

「非同質化」表示每個代幣具有可區別的身分或紀錄，不能像現金或一般同質化代幣一樣，與另一個同種類代幣直接互換而仍視為完全相同。NFT 可用來表示數位或實體資產的特定項目；持有 NFT 本身不必然代表持有該項目的著作權。

解題方法

辨認縮寫即可：NFT 的關鍵字是 Non-fungible，意指「非同質化」；token 指代幣。因此，NFT 展開為 Non-fungible token。

選項分析

核心觀念

UML（統一塑模語言）的類別圖通常以長方形表示一個類別，並由上而下分成三個區域：

1. 最上方：類別名稱
2. 中間：屬性
3. 最下方：操作（方法）

因此，最上方區域放的是類別名稱。

解題方法

題目問類別矩形的最上方區域包含什麼。依照上述排列，最上方對應類別名稱，所以選 A。

選項分析

• A. The class's name.（類別名稱）—正確。 類別矩形最上方的區域標示類別名稱。

核心觀念

本題考二元樹的 inorder traversal（中序走訪）。走訪順序為：

即 LNR（Left-Node-Right）。

解題方法

依照圖中的樹逐層進行中序走訪：

1. 根節點為 $7$，先走訪左子樹。
2. 左子樹根節點為 $5$：
   • $5$ 的左子樹為 $4$，而 $4$ 的左子樹為 $2$，因此先得到 $2$。
   • 接著走訪 $4$，再走訪 $4$ 的右側沒有節點。
   • 回到 $5$，再走訪其右子節點 $3$。
3. 左子樹走訪結果為：

4. 回到根節點 $7$。
5. 走訪右子樹根節點 $8$：
   • 先走訪左子節點 $9$。
   • 再走訪 $8$。
   • 最後走訪右子節點 $1$。

因此完整的中序走訪為：

核心觀念

子網路遮罩用來區分 IP 位址中的「網路部分」與「主機部分」。子網路編號就是將 IP 位址與子網路遮罩逐位元執行 AND 運算後得到的網路位址。

本題遮罩為 $255.255.255.192$。前三個八位元組的遮罩都是 $255$，因此前三個八位元組保持不變；最後一個八位元組的遮罩 $192$ 為二進位 $11000000$，代表最後一個八位元組有 $2$ 個網路位元、$6$ 個主機位元。

解題方法

直接對 IP 位址與子網路遮罩執行位元 AND 運算：

因此子網路編號為 $10.0.17.128$。

也可用區塊大小快速判斷。最後一個八位元組的區塊大小為：

此題考驗軟體開發生命週期中，程式碼的編譯、連結與執行過程。

當我們使用物件導向程式設計時，常見的做法是將類別的介面（interface）定義（通常在 .h 或 .hpp 檔案）與其實作（implementation，通常在 .cpp 檔案）分開。客戶端程式（client code）會引用這個類別的介面，但其具體的實作細節可能在另一個檔案中。

程式碼的整合過程如下：

1. Programming Phase (程式設計階段)：撰寫原始碼，包括介面定義和實作。
2. Compiling Phase (編譯階段)：編譯器將每個原始碼檔案（.cpp）轉換成對應的目標碼（object code，.o 或 .obj 檔案）。在這個階段，編譯器會檢查語法錯誤，並將介面定義與實作的資訊記錄在目標碼中。然而，如果客戶端程式引用了某個類別，編譯器知道這個類別的介面，但它可能還不知道這個類別的實作細節在哪個目標檔案裡，或者這個實作檔案還未被編譯。
3. Linking Phase (連結階段)：連結器（linker）負責將所有編譯好的目標碼檔案（.o/.obj）以及所需的函式庫（libraries）組合成一個可執行的檔案。

此題考驗 TCP/IP 協定中，如何將封包遞送到正確的應用程式。

TCP/IP 協定是一個分層模型，其中傳輸層（Transport Layer，例如 TCP 和 UDP）負責在主機之間傳遞資料，而網路層（Network Layer，例如 IP）負責將資料包從源主機傳遞到目的主機。

• IP 位址 (IP Address)：用於識別網路上的主機。網路層使用 IP 位址來決定封包要路由到哪個主機。
• MAC 位址 (MAC Address)：用於識別同一區域網路（LAN）上的網路介面卡（NIC）。它在資料連結層（Data Link Layer）使用。
• SSID (Service Set Identifier)：是 Wi-Fi 網路的名稱，與應用程式的資料遞送無關。
• Port Number (埠號)：在傳輸層（TCP/UDP）中使用。

此題考驗網路協定中，如何將 IP 位址解析（Resolution）為 MAC 位址。

• IP 位址 (IP Address)：是網路層（Layer 3）的位址，用於在網際網路範圍內識別主機。
• MAC 位址 (Data Link Address)：是資料連結層（Layer 2）的位址，用於在區域網路（LAN）內識別網路介面卡（NIC）。

當一個主機需要將封包傳送給同一區域網路內的另一台主機時，它需要知道目標主機的 MAC 位址。然而，應用程式通常只知道目標主機的 IP 位址。因此，需要一個機制來將 IP 位址解析為 MAC 位址。

這個機制就是 ARP (Address Resolution Protocol)。

ARP 的工作原理是：

1. 發送主機廣播一個 ARP 請求（ARP Request），內容是「誰的 IP 位址是 X.X.X.X？請告訴我你的 MAC 位址。」

核心觀念

系統呼叫（system call）是使用者程式向作業系統核心請求服務的介面，例如檔案操作、程序建立與裝置輸出。程式呼叫系統呼叫時，處理器會從使用者模式切換到核心模式，由核心執行具特權的服務，再將結果交回程式。

雙模式（dual mode）以使用者模式和核心模式區分程式的權限，避免一般程式直接執行特權操作，藉此保護作業系統與資源。

解題方法

逐一檢查敘述是否符合系統呼叫的定義，並留意「只能」與「所有」等絕對用語。特別要區分「程式呼叫系統呼叫的動作」和「核心執行系統呼叫服務的階段」：呼叫由使用者程式發起，服務則由核心在核心模式執行。

選項分析

• A 正確。 系統呼叫提供程式存取作業系統資源與服務的介面，例如開啟檔案或讀取資料。
• B 正確。 系統呼叫的服務由核心在核心模式執行。程式雖在使用者模式發出請求，但處理器會切換至核心模式處理；

核心觀念

本題比較關聯式資料庫與 NoSQL 資料庫，並考查查詢語言、鍵（key）與索引（index）的差異。

關聯式資料庫常使用 SQL，但 SQL 標準與各資料庫產品的實作方言並不完全相同。鍵是資料模型中的識別與約束；索引則是資料庫用來加速查詢的結構，兩者相關但不相同。NoSQL 涵蓋多種資料模型，包括鍵值、文件、寬欄與圖形資料庫，不能一概視為鍵值資料庫。

解題方法

逐項檢查敘述是否適用於「所有」關聯式資料庫或「所有」NoSQL 資料庫，並留意選項是否把鍵與索引混為一談。題目以單選方式出題，但若按嚴格技術定義判斷，B、C、D 也各有不精確之處；以下依一般考試預期，將 A 視為命題要測的錯誤敘述。

選項分析

A. All relational databases use the same query language to access databases.

錯誤。關聯式資料庫普遍使用 SQL，但不同產品的 SQL 方言、函式、資料型別與語法支援可能不同；此外，「關聯式」描述的是資料模型，並不代表所有系統都必須用完全相同的查詢語言。因此「都使用相同查詢語言」說得過於絕對。

B. In relational databases, every table is indexed by a key.

嚴格來說不正確。資料表可以設定主鍵或其他鍵，作為資料列識別與完整性約束；但鍵不等於索引。資料庫可以為鍵建立索引，也可以不對某個資料表建立索引。

核心觀念

物聯網（IoT）是讓實體物件透過網路連線，並能傳送或接收資料、接受控制或與其他設備互動的技術。連線方式不限於某一種網路：設備可透過 WLAN（無線區域網路）、行動網路等方式連接，也可經由閘道器或手機與網際網路互通。

WLAN 與 WAN 的差異在於涵蓋範圍：WLAN 通常涵蓋家庭、辦公室等局部區域；WAN 則連接較廣大的地理範圍。兩者都能成為 IoT 設備通訊架構的一部分。

解題方法

逐項判斷敘述是否符合 IoT 設備的連線特性。題目問「錯誤」的敘述，因此要找出把 IoT 的網路連線能力限制得不正確的選項。

選項分析

A. An IoT device refers to an object that has network access.

正確。IoT 設備是具備網路連線能力的實體物件，常見例子包括智慧家電、感測器與穿戴裝置。設備也可能透過手機或閘道器連上其他網路服務，不一定要直接連接網際網路。

B. IoT devices can be accessed through WLAN, but not WAN.

核心觀念

這題考 最近最少使用置換法（LRU, Least Recently Used）。記憶體有 3 個頁框，頁面首次被存取時若不在記憶體中，就發生一次頁面錯誤；若頁框已滿，LRU 會淘汰「距離目前最近一次使用時間最久」的頁面。

解題方法

依序處理參照字串 abcdbafbacbac。表中的頁框由左至右記為「最久未使用 → 最近使用」；發生頁面錯誤且頁框已滿時，淘汰最左側頁面。

核心觀念

本題考查循序搜尋與分治搜尋的時間複雜度，以及比較一次能提供多少資訊。

假設每次比較都能判斷較輕的一側，或判斷兩側平衡。分治法可將硬幣分成數個大小相近的組，再依比較結果繼續搜尋候選組；每次比較都會大幅縮小候選範圍，因此所需比較次數呈對數成長。

解題方法

循序搜尋逐一檢查硬幣，最壞情況下須檢查到最後一枚，時間複雜度為 $O(N)$；若第一枚就是假幣，最佳情況只需一次比較。

分治搜尋每次把候選範圍縮小為原來的一部分。例如，每次約縮小為原來的三分之一，則比較次數約為：

因此時間複雜度為 $O(\log N)$。但一次比較通常只能指出假幣在哪一組，不能直接指出那組中的哪一枚是假幣。以 $N=3^k$ 且每次均分三組為例，無論假幣在哪一枚，都需要逐層縮小候選組，直到剩下一枚，不能一律只比較一次。

選項分析

核心觀念

本題考查網頁的用戶端—伺服器模型與網路安全。用戶端向伺服器送出請求，伺服器收到請求後回傳回應；這種互動方式描述通訊角色與資料交換流程，不代表伺服器不會受到用戶端攻擊。

網頁瀏覽也會帶來安全風險：惡意網站或遭入侵的網站可利用瀏覽器、外掛程式或系統漏洞攻擊使用者；伺服器則可能因惡意或刻意構造的請求而遭受攻擊。

解題方法

逐項判斷敘述是否符合網頁運作與安全實務。特別留意選項 C 的「所以」：用戶端發送請求、伺服器回應，並不能推導出伺服器不會被用戶端攻擊。伺服器仍須處理使用者送來的請求，而請求內容可能被用來利用程式漏洞或耗盡伺服器資源。

選項分析

• A 正確。 使用者通常透過瀏覽器等用戶端，連線並存取網頁伺服器，符合用戶端—伺服器模型。
• **B 正確。

此題考驗對二補數（Two's Complement）和一補數（One's Complement）表示有號整數（signed integers）的理解。

基本概念：

• 二補數 (2's Complement)：這是電腦中最常用的表示負數的方法。對於一個 k 位元數：
  • 正數範圍：$0$ 到 $2^{k-1} - 1$。
  • 負數範圍：$-2^{k-1}$ 到 $-1$。
  • 總共可以表示 $2^k$ 個不同的數。
  • 求負數的二補數方法：對其正數形式的二進位表示進行位元反轉（invert），然後加 1。
• 一補數 (1's Complement)：另一種表示負數的方法。對於一個 k 位元數：
  • 正數範圍：$0$ 到 $2^{k-1} - 1$。
  • 負數範圍：$- (2^{k-1} - 1)$ 到 $-1$。
  • 總共可以表示 $2^k - 1$ 個不同的數（因為有兩個表示 0 的方式：+0 和 -0）。
  • 求負數的一補數方法：對其正數形式的二進位表示進行位元反轉（invert）。

選項分析：

A. Given a k-bit register, the range of signed integers that can be represented by 2's complement is between $-(2^{k-1}-1)$ and $(2^{k-1}-1)$.

• 錯誤。對於 k 位元二補數：
  * 最大正數是 $2^{k-1} - 1$。
  * 最小負數是 $-2^{k-1}$。
  * 所以範圍是 $[-2^{k-1}, 2^{k-1} - 1]$。
• 選項中給出的範圍是 $[- (2^{k-1}-1), (2^{k-1}-1)]$，這是錯誤的。例如，對於 3 位元二補數 (k=3)：
  * 正確範圍是 $[-2^{3-1}, 2^{3-1}-1] = [-2^2, 2^2-1] = [-4, 3]$。
  * 選項給出的範圍是 $[-(2^{3-1}-1), (2^{3-1}-1)] = [-(2^2-1), (2^2-1)] = [-3, 3]$。
• 因此，此敘述是錯誤的。

核心觀念

本題考查關聯式資料庫的 ACID 交易特性、實體關係模型，以及資料庫如何處理並行存取。

ACID 包含：

• 原子性（Atomicity）：交易中的操作要全部完成，或全部取消，不能只完成一部分。
• 一致性（Consistency）：交易執行前後，資料庫都必須符合既定的完整性限制。
• 隔離性（Isolation）：並行執行的交易，其結果應符合一定的隔離規則，避免彼此造成不合理的干擾。
• 持久性（Durability）：交易提交後，即使系統故障，結果仍須保存。

關聯式資料庫通常使用鎖等並行控制機制管理多筆交易，但鎖的目的是協調衝突、維持隔離性，不代表任何時刻只能有一位使用者修改資料。

解題方法

先判斷各選項描述的是哪個概念，再檢查定義是否精確。A、D 對應 ACID 特性，B 描述實體關係模型；C 則是關於鎖與並行控制的說法。關鍵在於區分「控制衝突」與「全面禁止多人同時修改」。

選項分析

A. 正確。
原子性要求一筆交易視為不可分割的整體。例如轉帳包含扣款與入帳兩個步驟，若其中一步失敗，資料庫應回復交易，不留下只扣款、未入帳的部分結果。

核心觀念

本題考查雲端運算的服務模式，以及它如何運用分散式系統提供運算與儲存資源。

常見的雲端服務模式有三種：

• IaaS（基礎設施即服務）：提供虛擬機器、儲存空間、網路等基礎運算資源。
• PaaS（平台即服務）：提供應用程式開發、測試與部署所需的平台環境。
• SaaS（軟體即服務）：提供可直接使用的軟體服務。

雲端運算通常透過網路整合多部伺服器的運算與儲存能力。處理大量資料時，常將工作分散到多台機器，而非仰賴單一機器。

解題方法

逐一檢視選項是否符合雲端運算的服務模式與運作方式。前三項分別描述常見服務分類、IaaS 提供的資源，以及雲端運算的分散式特性；最後一項則聲稱大量資料可在「單一機器」中儲存與處理，與分散式運算的典型做法不符。

選項分析

A. 正確。
IaaS、PaaS、SaaS 是雲端運算最常見的三種服務模式分類，分別對應基礎設施、平台與軟體服務。

此題考驗對 C 語言中雙向鏈結串列（Doubly Linked List）節點刪除操作的理解。

雙向鏈結串列的每個節點都包含指向前一個節點的指標 (prev) 和指向下一個節點的指標 (next)。
要刪除一個節點 curNode，我們需要修改其前一個節點 (curNode->prev) 和後一個節點 (curNode->next) 的指標，將它們連接起來，繞過 curNode。

假設 curNode 是要被刪除的節點。
它有兩個鄰居：

• 前一個節點：prev_node = curNode->prev
• 後一個節點：next_node = curNode->next

為了刪除 curNode，我們需要：

1. 讓 prev_node 的 next 指標指向 next_node。
   • prev_node->next = next_node;
   • 或者寫成 curNode->prev->next = curNode->next;
2. 讓 next_node 的 prev 指標指向 prev_node。
   • next_node->prev = prev_node;
   • 或者寫成 curNode->next->prev = curNode->prev;

題目假設 curNode 不是頭節點也不是尾節點，這意味著 curNode->prev 和 curNode->next 都是有效的節點指標（不是 NULL）。

選項分析：

A.
curNode->prev->next = curNode->next;
curNode->next->prev = curNode->prev;

• 這個選項的程式碼正是我們推導出的刪除節點的標準操作。
• curNode->prev->next = curNode->next;：將 curNode 的前一個節點的 next 指標指向 curNode 的下一個節點。

核心觀念

監督式學習使用帶有標籤的訓練資料，讓模型學習輸入與正確輸出之間的關係。分類是常見的監督式學習任務，例如根據已標記的資料判斷新資料所屬類別。

非監督式學習則使用沒有標籤的資料，從資料中找出群集或結構；分群是常見任務。

解題方法

逐一判斷各方法是否通常以已標記資料訓練：

• 若方法學習如何預測已知的類別標籤，屬於監督式學習。
• 若方法只依據資料間的相似性分組，沒有使用類別標籤，屬於非監督式學習。

選項分析

• A. Support vector machine（支援向量機）—正確。 分類型支援向量機使用已標記的訓練資料，尋找能區分不同類別的決策邊界，屬於監督式學習。
• B. Naïve Bayes classifier（樸素貝氏分類器）—正確。 分類器由帶有類別標籤的訓練資料估計各類別的先驗機率與特徵條件機率，再據此預測新資料的類別，屬於監督式學習。

此題考驗對常見處理器架構的認識，特別是 ARM 架構。

ARM 架構：
ARM（Advanced RISC Machines）是一家英國的半導體智慧財產權（IP）核設計公司。它設計了基於 RISC（Reduced Instruction Set Computing）指令集的處理器架構，並將其授權給其他公司（如 Apple, Qualcomm, Samsung, Nvidia）來設計和製造自己的處理器晶片。ARM 架構以其低功耗、高能效比而聞名，廣泛應用於移動設備（智能手機、平板電腦）、嵌入式系統，近年來也開始進入伺服器和個人電腦市場。

選項分析：

A. AMD Ryzen.

• x86 架構。AMD Ryzen 處理器是基於 x86 指令集架構的，這是 Intel 和 AMD 在個人電腦和伺服器領域長期使用的架構。

B. Apple Silicon.

• ARM 架構。Apple 從 2020 年開始將其 Mac 電腦從 Intel 的 x86 架構轉移到自家設計的 Apple Silicon

此題考驗對深度學習模型和數據集的認識，特別是與卷積神經網路（Convolutional Neural Network, CNN）相關的。

卷積神經網路 (CNN)：
CNN 是一種專門設計用於處理網格狀數據（如圖像）的神經網路。其核心是卷積層（Convolutional Layer），通過使用可學習的濾波器（kernels）來提取數據中的局部特徵。CNN 在圖像識別、目標檢測、自然語言處理等領域取得了巨大成功。

選項分析：

A. WordNet.

• 不是基於 CNN。WordNet 是一個英語詞彙資料庫，主要用於自然語言處理（NLP）任務，例如詞義消歧、同義詞查找等。雖然深度學習技術（包括基於 RNN 或 Transformer 的模型）也可用於 NLP，但 WordNet 本身是一個基於圖結構的詞彙關聯資料庫，與 CNN 的核心應用（圖像處理）不同。

B. ResNet (Residual Network).

• 基於 CNN。ResNet 是一種非常著名的深度卷積神經網路架構，由微軟研究院提出。它引入了殘差連接（residual connections），解決了深度網路訓練中的梯度消失問題，使得訓練非常深的網路成為可能。ResNet 在圖像識別任務中取得了突破性成果。

此題考驗對程式語言執行方式（編譯式 vs. 解譯式）的了解。

• 編譯式語言 (Compiled Languages)：程式碼在執行前，會被編譯器（Compiler）一次性地轉換成機器碼（Machine Code）或中間碼（Intermediate Code）。執行時，直接運行機器碼，速度較快。常見的編譯式語言有 C, C++, Java (編譯成位元組碼，再由 JVM 解譯或 JIT 編譯), Go, Rust, Assembly。
• 解譯式語言 (Interpreted Languages)：程式碼在執行時，由解譯器（Interpreter）逐行讀取、分析並執行。執行過程相對較慢，但開發和調試更為靈活。常見的解譯式語言有 Python, JavaScript, Ruby, PHP。

注意： 許多現代語言採用混合模型，例如 Java 編譯成位元組碼後，由 Java 虛擬機器（JVM）進行解譯或即時編譯（JIT, Just-In-Time compilation）。

此題考驗對「差分隱私」（Differential Privacy）概念及其實現機制的理解。

差分隱私 (Differential Privacy)：
差分隱私是一種嚴格的數學定義，用於保證在一個數據集上進行查詢或分析時，任何單一記錄的加入或移除對結果的影響都足夠小，從而保護個體隱私。其核心思想是向查詢結果中添加適量的隨機雜訊。

實現差分隱私的機制（Noise Mechanisms）：
為了實現差分隱私，通常會在計算結果上添加隨機雜訊。常見的雜訊機制包括：

• Laplace Mechanism (拉普拉斯機制)：在輸出結果中添加服從拉普拉斯分佈的雜訊。這種機制對於計算統計量（如計數、總和、平均值）非常有效，並且能夠提供差分隱私。
• Gaussian Mechanism (高斯機制)：在輸出結果中添加服從高斯（常態）分佈的雜訊。這也是一種常用的差分隱私機制，特別是在處理連續型數據或需要較強隱私保證的場景。
• Exponential Mechanism (指數機制)：這是一種更通用的機制，適用於輸出空間複雜的查詢（例如，選擇最佳項目）。它根據一個分數函數（score function）來定義一個概率分佈，然後從該分佈中採樣。

此題考驗對「虛擬化」（Virtualization）技術的理解。

虛擬化技術允許在一台物理硬體上模擬出多個虛擬的計算環境，每個虛擬環境都可以運行自己的作業系統和應用程式。

選項分析：

A. By using virtualization technologies, a physical machine can become multiple machines of different operating systems.

• 正確。這是虛擬化的核心優勢之一。例如，一台物理伺服器可以運行一個虛擬化平台（如 VMware ESXi, Hyper-V, KVM），然後在這個平台上創建多個虛擬機器（VMs），每個 VM 可以安裝不同的作業系統（如 Windows Server, Linux 發行版, FreeBSD）。

B. Virtualization can make programs run faster.

• 不一定，通常不會讓單一程式運行更快，反而可能略慢。虛擬化技術的主要優勢在於資源的整合、彈性、隔離性和管理便利性，而不是提升單一應用程式的執行速度。由於虛擬化層（Hypervisor）的存在，會引入一些額外的開銷（overhead），因此在相同的硬體上，虛擬機中的程式執行速度通常會略低於直接運行在物理機上。但是，對於整體系統的效率和資源利用率，虛擬化有顯著提升。所以這句話的表述是錯誤的。

C. Virtualization technologies can virtualize RAM and CPU, but not network.

• 錯誤。虛擬化技術可以虛擬化幾乎所有的硬體資源，包括 CPU、RAM、儲存設備（硬碟）、網路介面卡（NIC）、USB 設備等。虛擬化網路（Virtual Networking）是一個非常成熟且重要的領域，它允許創建虛擬交換機、虛擬路由器、虛擬網卡，並配置複雜的網路拓撲。

D. Virtualization can protect machines from system crashes.

• 間接正確，但表述不夠精確。虛擬化本身不能「防止」系統崩潰。

核心觀念
本題考察「演算法 (algorithm)」的基本定義與常見的表示方式。必須了解以下概念：

1. 演算法：解決特定問題的有限步驟程序，具備「輸入、輸出、確定性、有限性」四大特性。
2. 流程圖 (flowchart)：以圖形符號（開始、判斷、處理等）連接之方式呈現演算法的執行流程。
3. 偽代碼 (pseudocode)：使用類似程式語言的文字描述演算法，強調語意的清晰與步驟的順序，較不受圖形布局限制。
4. 演算法的適用範圍：不僅限於電腦程式設計，亦可用於日常生活、工程、管理等任何需要明確步驟的問題求解。

解題方法
逐一檢視選項的敘述是否符合上述概念，判斷其真偽。此類複選題的關鍵在於「每個選項的語意是否完整且無矛盾」，不需要計算，只需概念比對。

1. 先確認每個敘述的主詞與限定範圍是否正確。
2. 檢查是否有過度推論（如將演算法限制於程式設計）或語意不完整（如比較兩種表示方式時缺少「相對於」的說明）。
3. 對於比較性敘述（選項 D）判斷其相對精確度，需依照「偽代碼能直接描述演算法的控制結構與細節」來評估。

選項分析

• A. A flowchart is a way of presenting an algorithm.
  正確。流程圖是一種視覺化的表示法，用圖形符號描述演算法的執行順序與分支，屬於「呈現演算法」的方式之一。

此題考驗對圖論（Graph Theory）中路徑尋找演算法的理解，特別是貪婪演算法（Greedy Algorithm）和單源最短路徑（Single Source Shortest Path, SSSP）及所有點對最短路徑（All-Pairs Shortest Path, APSP）的問題。圖的表示方法是鄰接矩陣（Adjacency Matrix）。

圖的表示：

• 鄰接矩陣（Adjacency Matrix）：一個 N×N 的矩陣，其中 $M[i][j]$ 表示從頂點 i 到頂點 j 的邊的權重。如果沒有邊，則通常用 $\infty$ 表示。對於有向加權圖，陣列大小為 $N \times N$。

演算法與問題：

• 單源最短路徑 (SSSP)：找出從一個特定源點到圖中所有其他頂點的最短路徑。
  • Dijkstra's Algorithm：適用於邊權重非負的圖。時間複雜度通常是 $O(E \log V)$ 或 $O(V^2)$ (使用鄰接矩陣)。
  • Bellman-Ford Algorithm：適用於包含負權邊但無負權環的圖。時間複雜度是 $O(VE)$。
• 所有點對最短路徑 (APSP)：找出圖中任意兩個頂點之間的最短路徑。
  • Floyd-Warshall Algorithm：適用於包含負權邊但無負權環的圖。時間複雜度是 $O(V^3)$。
  • 多次運行 Dijkstra's Algorithm：如果邊權重非負，可以對每個頂點運行一次 Dijkstra。
• 貪婪演算法 (Greedy Algorithm)：在每一步選擇當前看起來最好的選項，期望最終能得到全域最优解。Dijkstra's Algorithm 是一種貪婪演算法。

選項分析：

A. A greedy algorithm can find an optimal path of a single source to a single destination.

• 正確。Dijkstra's Algorithm 是一種貪婪演算法，用於解決單源最短路徑問題。當我們找到從單源點到所有其他點的最短路徑時，其中就包含了到任何單一目標點的最短路徑。所以，這個說法是正確的。

B. It takes the time complexity of O(N³) to find optimal paths of all sources to all destinations.

• 正確。對於一個有 N 個頂點的圖，使用鄰接矩陣表示，Floyd-Warshall Algorithm 的時間複雜度是 $O(N^3)$。這是計算所有點對最短路徑的標準演算法。

C. A greedy algorithm can find optimal paths of a single source to all destinations.

• 正確。

此題考驗對排序演算法（Sorting Algorithms）的理解，包括時間複雜度、空間複雜度和穩定性（Stability）。

演算法分析：

A. Quick sort is a divide-and-conquer algorithm, so its worst-case time complexity is O(nlogn).

• 錯誤。Quick Sort 確實是一種分治（Divide-and-Conquer）演算法。但是，它的最壞情況時間複雜度是 $O(N^2)$，這發生在每次選擇的基準點（pivot）都是當前子陣列的最大或最小值時（例如，輸入陣列已經排序或逆序排序）。
• 平均情況時間複雜度是 $O(N \log N)$。
• 最佳情況時間複雜度也是 $O(N \log N)$。
• 因此，該陳述錯誤，因為最壞情況不是 $O(N \log N)$。

B. Merge sort takes less time complexity, O(nlogn), than insertion sort and as much space as insertion sort.

• 部分正確，部分錯誤。
  * 時間複雜度：Merge Sort 的時間複雜度（最佳、平均、最壞）都是 $O(N \log N)$。Insertion Sort 的時間複雜度是：最佳 $O(N)$，平均 $O(N^2)$，最壞 $O(N^2)$。因此，Merge Sort 的時間複雜度 $O(N \log N)$ 確實比 Insertion Sort 的平均和最壞情況 $O(N^2)$ 要快。

核心觀念

• 陣列 (Array) 與鏈結串列 (Linked List) 的空間需求
  • 陣列：須事先配置固定大小的記憶體，常以最大可能筆數 $N$ 為基礎。除了資料本身，還可能保留一個指向首端或尾端的指標 (4 bytes)。
  • 鏈結串列：每一筆資料佔用自己的記憶體區塊，內含資料 $D$ 與指向下一節點的指標 (4 bytes)。整個結構再額外保留一個頭指標 (4 bytes)。
• 記憶體單位：題目已給定
  • 資料記錄大小 $D$ (bytes)
  • 整數 2 bytes
  • 指標 4 bytes

解題方法

1. 依題意列寫兩種實作的總記憶體公式。
2. 依選項所敘述的情境代入公式或比較差異。
3. 注意「實際儲存筆數 $n$」與「最大可能筆數 $N$」的差別：陣列的空間與 $N$ 成正比、鏈結串列則與實際筆數 $n$ 成正比。

空間公式推導

• 陣列實作
  $\text{Array\_size}=N\cdot D + 4$
  （$N$ 筆資料，每筆 $D$ 位元組，加上一個指標）

• 鏈結串列實作（存放 $k$ 筆資料）
  $\text{Linked\_size}=k\,(D+4)+4$
  $k$ 為實際儲存的筆數，$D$ 為資料，$4$ 為每筆的 next 指標，外加 4 bytes 的頭指標。

選項分析