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

核心觀念

交換器與路由器都需要查表，決定收到資料後要從哪個介面送出：

• 交換器使用轉送表（forwarding table），通常記錄目的 MAC 位址與對應的輸出埠。
• 路由器使用路由表（routing table），記錄目的 IP 網路與對應的下一跳或輸出介面。

兩種表格的查詢依據不同，但用途相似：根據目的位址資訊，選出資料的轉送方向。

解題方法

題目指出交換器使用的結構「很像路由器的路由表」，關鍵在於辨認兩者的共同用途：查找目的資訊，決定輸出方向。交換器用來完成這項工作的表格稱為轉送表，因此答案是 B。

選項分析

核心觀念

本題考「加密」（encryption）的定義。加密是利用演算法與金鑰，將可讀的原始資訊（明文）轉換成不易直接理解的形式（密文），藉此保護資訊內容。

接收者持有適當的金鑰後，可將密文解密，還原成明文。加密的核心目的是讓未獲授權者無法直接讀懂資訊；它本身不等於傳送資料，也不負責偵測或修正傳輸錯誤。

解題方法

先辨認每個選項描述的功能，再與加密的定義比對：

• 若是在描述把資訊轉成難以理解的形式，符合加密。
• 若是在描述安全傳輸、錯誤偵測或錯誤防止，則屬於其他資訊安全或通訊功能。

選項分析

核心觀念

本題考「公有區塊鏈如何透過共識機制決定哪些交易與區塊可以被網路接受」。共識機制讓分散在不同節點上的參與者，在沒有中央管理者的情況下，對帳本內容達成一致。

工作量證明（Proof of Work, PoW）是常見的共識機制。參與者須投入計算資源，尋找符合條件的雜湊值；成功提出區塊後，其他節點可快速驗證其結果。這種機制提高了竄改區塊鏈的成本。

解題方法

辨認題目中的關鍵詞 consensus mechanism（共識機制），再檢視各選項是否是用來讓分散式網路確認區塊的正式機制。四個選項中，只有 proof of work 符合此定義，因此選 D。

選項分析

核心觀念

本題考查區塊鏈與數位資產的基本名詞。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）的順序是「左子樹 → 根節點 → 右子樹」。每個子樹都套用相同順序，直到走訪完所有節點。

解題方法

由最左側節點開始，依中序規則走訪：

• 根節點 $7$ 的左子樹：先走訪 $4$ 的左子節點 $2$，再走訪 $4$，接著走訪 $5$，最後走訪 $5$ 的右子節點 $3$，得到 $2453$。
• 接著走訪根節點 $7$。
• 根節點 $7$ 的右子樹：先走訪 $8$ 的左子節點 $9$，再走訪 $8$，最後走訪 $8$ 的右子節點 $1$，得到 $981$。

合併後的中序走訪結果為：

核心觀念

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

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

解題方法

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

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

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

核心觀念

類別的介面與實作分置於不同檔案時，客戶端程式透過介面取得類別宣告；實作檔則獨立編譯成目的檔。之後，連結器會將客戶端目的檔與實作目的檔連結，並解析彼此的函式或方法參照，產生可執行檔。

因此，實作程式碼與客戶端程式碼是在**連結階段（linking phase）**整合。

解題方法

依程式建置流程判斷：

1. 程式設計階段：撰寫介面、實作與客戶端程式。
2. 編譯階段：將各個原始碼檔分別翻譯成目的碼。
3. 連結階段：整合目的檔、解析跨檔案的參照，產生可執行檔。
4. 執行階段：載入並執行可執行檔中的指令。

題目問實作程式碼何時與客戶端程式碼合併，對應到整合目的檔的連結階段。

選項分析

核心觀念

這題考查 TCP/IP 網路分層中，如何將收到的資料交給目的主機上的正確應用程式。

網際網路協定（IP）負責將封包送到目的主機；傳輸層的 TCP 或 UDP 則使用**埠號（port number）**識別目的主機上要接收資料的應用程式或服務。目的 IP 位址與目的埠號合在一起，才能指出資料應送往哪台主機上的哪個服務。

解題方法

先看題目問的是「訊息要交付給哪個應用程式」，而非「訊息要送到哪台主機」：

• 要找目的主機，使用 IP 位址。
• 要找主機上的目的應用程式或服務，使用埠號。

因此，題目問的是應用程式層級的交付，應選埠號。

選項分析

核心觀念

在乙太網路等區域網路中，主機傳送資料時，網路層使用 IP 位址識別目的主機；資料鏈結層則使用 MAC 位址識別同一區域網路中的網路介面。要把目的 IP 位址對應到資料鏈結層位址，會使用 ARP（Address Resolution Protocol，位址解析協定）。

解題方法

先看題目要求的轉換方向：由 IP 位址解析成資料鏈結層位址，也就是通常所說的由 IP 位址查得 MAC 位址。ARP 會在區域網路中廣播查詢，持有該 IP 位址的主機再回覆自己的 MAC 位址；查詢結果也可暫存在 ARP 快取中。

選項分析

核心觀念

系統呼叫（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 正確。

核心觀念

這題考有號整數的二補數與一補數表示法。

對 $k$ 位元的二補數，最高位是符號位，其表示範圍為：

二補數的負數可由「逐位反相後加 $1$」求得。一補數則以逐位反相表示負數，因此會有正零與負零兩種零的表示法。

解題方法

逐一依位元數套用表示範圍與轉換規則：

• 檢查 A 的二補數範圍是否包含最小值 $-2^{k-1}$。
• 對 B 逐位反相並加 $1$，確認其負值。
• 對照 C 的二補數轉換規則。
• 以 4 位元表示法檢查 D 中兩種編碼的意義。

選項分析

A. 錯誤。
二補數的範圍是 $-2^{k-1}$ 至 $2^{k-1}-1$，不是 $-(2^{k-1}-1)$ 至 $2^{k-1}-1$。例如 4 位元二補數範圍為 $-8$ 至 $7$，選項少列了 $-8$。

B. 正確。
$110010$ 是 6 位元二補數，最高位為 $1$，表示負數。逐位反相後加 $1$：

核心觀念

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

ACID 包含：

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

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

解題方法

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

選項分析

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

核心觀念

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

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

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

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

解題方法

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

選項分析

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

核心觀念

雙向鏈結串列的每個節點都用兩個指標連接前後節點：

• prev 指向前一個節點。
• next 指向下一個節點。

刪除中間節點時，要讓它的前一個節點直接連到它的下一個節點，並讓下一個節點反向連回前一個節點：

題目已說明 curNode 不是頭節點，也不是尾節點，因此它的 prev 和 next 都指向有效節點。

解題方法

將 curNode 記為 $C$，前一個節點記為 $P$，下一個節點記為 $N$。刪除前的連結是：

P <-> C <-> N

刪除 $C$ 時，將 P->next 改為 N，再將 N->prev 改為 P：

P <-> N

符合這兩個指標更新方式的是選項 A：

curNode->prev->next = curNode->next;
curNode->next->prev = curNode->prev;

這段程式碼只更新相鄰節點的指標，不會自行釋放 curNode 的記憶體；若題目要求釋放動態配置的節點，還需另行呼叫 free(curNode)。

選項分析

核心觀念

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

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

解題方法

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

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

選項分析

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

此題考查處理器架構，特別是 ARM 架構的應用。

核心觀念：

• ARM 架構：是一種 RISC (Reduced Instruction Set Computing) 指令集架構，以其低功耗、高效能的特性，廣泛應用於移動設備（如手機、平板）、嵌入式系統，近年來也逐漸進入伺服器和個人電腦領域。
• x86 架構：是 Intel 和 AMD 等公司生產的處理器所使用的 CISC (Complex Instruction Set Computing) 指令集架構，主導了傳統的個人電腦和伺服器市場。

分析選項：
(A) AMD Ryzen：
AMD Ryzen 系列處理器主要基於 AMD 自家的 x86-64 架構，與 ARM 架構不同。

此題考查深度學習模型，特別是與卷積神經網路 (Convolutional Neural Network, CNN) 相關的應用和架構。

核心觀念：

• 卷積神經網路 (CNN)：一種特別擅長處理圖像數據的深度學習模型，其核心是卷積層 (convolutional layers)，能夠自動學習圖像中的空間層次特徵。
• ImageNet：是一個大規模的圖像資料庫，常被用來訓練和評估圖像識別演算法。它本身不是一個模型，而是一個資料集。
• ResNet, Inception, GoogLeNet：都是在 ImageNet 資料集上表現優異的著名深度學習模型架構，它們都廣泛使用了卷積層，是 CNN 的代表性結構。
• WordNet：是一個英語詞彙的語義網絡，用於自然語言處理 (NLP) 任務，通常不直接基於 CNN，雖然 CNN 也可應用於 NLP，但 WordNet 本身是一個知識庫，而不是 CNN 模型。

分析選項：
(A) WordNet：
WordNet 是一個語言學資料庫，用於表示單詞之間的語義關係（同義詞、上位詞、下位詞等）。它主要用於自然語言處理 (NLP)，並非基於 CNN 模型。

此題考查程式語言的執行方式，特別是解釋型語言 (Interpreted Languages) 和編譯型語言 (Compiled Languages)。

核心觀念：

• 編譯型語言 (Compiled Languages)：程式碼在執行前，會被編譯器 (compiler) 轉換成機器碼 (machine code) 或中間碼 (intermediate code)。執行時直接運行這些轉換後的代碼。常見的編譯型語言有 C, C++, Java (編譯成位元組碼後由 JVM 解釋執行，但編譯步驟是必要的)。
• 解釋型語言 (Interpreted Languages)：程式碼在執行時，由解釋器 (interpreter) 一行一行讀取、分析並執行。不需要預先編譯成機器碼。常見的解釋型語言有 Python, JavaScript, Ruby, R。
• 組合語言 (Assembly Language)：是一種低階語言，與特定處理器架構緊密相關。組合語言需要透過組合器 (assembler) 轉換成機器碼才能執行。因此，它不是解釋型語言，而是需要編譯（組合）的。

此題考查差分隱私 (Differential Privacy) 的機制，這是個進階的資訊安全與隱私保護概念。

核心觀念：

• 差分隱私 (Differential Privacy, DP)：是一種用於保護資料庫中個體隱私的數學框架。其核心思想是，對於一個查詢 (query)，無論資料庫中是否包含某個特定個體的數據，查詢結果的機率分佈都應該非常相似。這樣，攻擊者就無法透過觀察查詢結果來推斷出特定個體的資訊。
• 差分隱私機制：為了實現差分隱私，通常會在查詢結果中加入適量的隨機雜訊。這些雜訊的添加方式有不同的數學模型，稱為差分隱私機制。

分析選項：
(A) Linear mechanism：
線性機制 (Linear Mechanism) 是一種差分隱私機制，它透過向查詢結果添加一個與查詢敏感度 (sensitivity) 成比例的隨機向量來實現差分隱私。

(B) Laplace mechanism：
拉普拉斯機制 (Laplace Mechanism) 是差分隱私中最常見和基礎的機制之一。它透過向查詢結果添加服從拉普拉斯分佈 (Laplace distribution) 的隨機雜訊來實現差分隱私。這種機制對於計算型查詢（如計數、求和）特別有效。

此題考查虛擬化技術 (Virtualization Technologies) 的概念與應用。

核心觀念：

• 虛擬化 (Virtualization)：是一種軟體技術，它允許將單個物理硬體資源（如伺服器、儲存設備、網路）模擬成多個虛擬資源。每個虛擬資源都可以被視為一個獨立的實體，並可以運行自己的作業系統和應用程式。
• Hypervisor (虛擬機管理器)：是運行在硬體或作業系統之上，負責創建和管理虛擬機的軟體。

分析選項：
(A) By using virtualization technologies, a physical machine can become multiple machines of different operating systems.
這是虛擬化的核心功能之一。透過 Hypervisor，一台物理伺服器可以運行多個虛擬機 (VM)，每個 VM 都可以安裝並運行不同的作業系統（例如，Linux, Windows, macOS）。這大大提高了硬體資源的利用率。此敘述是正確的。

(B) Virtualization can make programs run faster.
一般來說，虛擬化本身並不會直接使程式「跑得更快」。程式的執行速度主要取決於硬體性能和程式本身的優化。虛擬化引入了額外的軟體層 (Hypervisor)，可能會帶來一些效能開銷 (overhead)。然而，在某些特定場景下，虛擬化可以間接提升效率：
* 資源調度優化：透過虛擬化平台，可以更靈活地分配和調度資源給需要的虛擬機，從而讓關鍵應用獲得足夠的資源，間接提升其性能。
* 快速部署與恢復：虛擬機的創建、遷移和備份恢復速度遠快於物理機，這可以加速開發、測試和部署過程，從而提高整體專案的效率。
* 隔離性：虛擬化提供的隔離性可以防止一個應用程式的錯誤影響到其他應用程式，減少因錯誤導致的停機時間，從而提高系統的可用性和整體生產力。
但是，如果單純問「執行速度」，虛擬化通常會帶來少量效能損耗。因此，這個敘述的「直接性」和「普遍性」有待商榷。更準確的說法是「提高效率」或「提高生產力」，而不是「跑得更快」。
然而，在某些現代虛擬化技術和硬體輔助下，效能損耗已經非常小，甚至在某些特定負載下，透過更好的資源管理，虛擬機的表現可能與物理機相當。
在考試題目中，若沒有特別指明「直接速度提升」，這句話的涵義可能偏向「提高整體營運效率」或「優化資源分配」。
讓我們暫時保留這個選項，並繼續分析其他選項。

(C) Virtualization technologies can virtualize RAM and CPU, but not network.
這是錯誤的。現代的虛擬化技術不僅可以虛擬化 CPU 和 RAM，還可以虛擬化網路 (Network Interface Cards, NICs)、儲存 (Storage Controllers, Disk Drives) 等。例如，虛擬網路技術 (如 VLAN, vSwitch) 允許虛擬機之間以及虛擬機與外部網路之間進行通訊。

(D) Virtualization can protect machines from system crashes.
虛擬化透過提供隔離性，可以保護 其他 虛擬機免受單一虛擬機系統崩潰 (system crash) 的影響。如果一個 VM 發生崩潰，它通常不會導致運行在同一物理硬體上的其他 VM 或 Hypervisor 本身崩潰。這提高了系統的穩定性和可用性。

核心觀念
本題考察「演算法 (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) 的應用。

核心觀念：

• 圖 (Graph)：由頂點 (vertices, V) 和邊 (edges, E) 組成的結構。有向圖 (directed graph) 表示邊有方向，加權圖 (weighted graph) 表示邊有權重（通常是距離或成本）。
• 最短路徑問題 (Shortest Path Problem)：
  • 單源最短路徑 (Single Source Shortest Path, SSSP)：找出從一個起始頂點到圖中所有其他頂點的最短路徑。
  • 所有頂點對最短路徑 (All-Pairs Shortest Path, APSP)：找出圖中任意兩個頂點之間的最短路徑。
• 貪婪演算法 (Greedy Algorithm)：在每一步選擇當下看起來最好的選項，期望最終能得到全局最优解。
• Dijkstra 演算法：是解決單源最短路徑問題的經典貪婪演算法，適用於邊權重非負的情況。
• Floyd-Warshall 演算法：是解決所有頂點對最短路徑問題的動態規劃演算法。
• 最小生成樹 (Minimum Spanning Tree, MST)：是連通圖的子圖，包含圖中所有頂點，且邊的權重總和最小，並且沒有迴圈。Prim 和 Kruskal 演算法是解決 MST 的貪婪演算法。

分析選項：
(A) A greedy algorithm can find an optimal path of a single source to a single destination.
這個敘述是正確的。Dijkstra 演算法就是一個貪婪演算法，用於解決單源最短路徑問題。它可以在找到從單一來源點到所有其他點的最短路徑的同時，也找到了到任何單一目的地的最短路徑。前提是圖中沒有負權重的邊。

(B) It takes the time complexity of $O(N^3)$ to find optimal paths of all sources to all destinations.
這個敘述是正確的。Floyd-Warshall 演算法是一種解決所有頂點對最短路徑問題的動態規劃演算法，其時間複雜度為 $O(N^3)$，其中 N 是頂點的數量。當圖由鄰接矩陣表示時，Floyd-Warshall 演算法的實現通常會用到三重迴圈，時間複雜度為 $O(N^3)$。

(C) A greedy algorithm can find optimal paths of a single source to all destinations.
這個敘述是正確的。如前所述，Dijkstra 演算法是解決單源最短路徑問題的貪婪演算法。它能找出從一個源點到所有其他頂點的最短路徑。

此題考查排序演算法 (Sorting Algorithms) 的性質，包含時間複雜度、空間複雜度、穩定性以及相關資料結構。

核心觀念：

• 排序演算法：將一組資料依據特定規則排列的演算法。常見的包括 Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort 等。
• 時間複雜度 (Time Complexity)：演算法執行時間與輸入規模 n 的關係。
• 空間複雜度 (Space Complexity)：演算法執行時額外佔用的記憶體空間與輸入規模 n 的關係。
• 穩定性 (Stability)：如果排序演算法對於相等元素的相對順序保持不變，則稱該演算法是穩定的。
• 分治法 (Divide and Conquer)：將問題分解為子問題，遞迴解決子問題，然後合併子問題的解。
• 二元搜尋樹 (Binary Search Tree, BST)：一種二元樹，其中每個節點的值大於其左子樹中所有節點的值，並小於其右子樹中所有節點的值。

分析選項：
(A) Quick sort is a divide-and-conquer algorithm, so its worst-case time complexity is $O(n\log n)$.
Quick sort 確實是一種分治法演算法。它透過選擇一個基準值 (pivot) 將數列分割成兩部分（小於 pivot 的和大于 pivot 的），然後遞迴地排序這兩部分。
然而，Quick sort 的最壞情況時間複雜度是 $O(n^2)$，發生在每次分割時，分割點都極端不平衡（例如，數列本身已經排序好，且 pivot 總是選取第一個或最後一個元素）。
其平均情況和最佳情況時間複雜度是 $O(n\log n)$。
由於題目提到了「worst-case」，而 $O(n\log n)$ 是平均情況，所以此敘述是錯誤的。

(B) Merge sort takes less time complexity, $O(n\log n)$, than insertion sort and as much space as insertion sort.
* 時間複雜度比較：

核心觀念

• 陣列實作 (Array)：使用一段連續的記憶體空間儲存資料。若預先知道最大容量 $N$，可一次配置 $N$ 個資料格；每筆資料佔用 $D$ 位元組，額外的指標（如 front、rear）僅需 4 位元組（假設使用 32‑bit 整數作為索引）。
• 鏈結串列實作 (Linked List)：每筆資料以 節點 形式存放，節點內含資料本身 $D$ 位元組以及指向下一節點的 指標（4 位元組）。根據實際儲存筆數 $n$ 動態配置記憶體。
• 記憶體需求公式
  • 陣列：$M_{\text{array}} = D \times N + O_{\text{array}}$，其中 $O_{\text{array}}$ 為固定開銷（指標或索引）
  • 鏈結串列：$M_{\text{list}} = (D + 4) \times n + O_{\text{list}}$，其中 $O_{\text{list}}$ 為鏈表頭指標的 4 位元組

解題方法

1. 依題目條件確定固定開銷：
   • 陣列只需要 4 位元組的「rear」指標（題目暗示只加 4），故 $O_{\text{array}} = 4$。
   • 鏈結串列需一個「head」指標，同樣 4 位元組，$O_{\text{list}} = 4$。
2. 針對每個選項代入上述公式，檢驗是否相符。
   • 若選項涉及 最大 資料筆數 $N$，則在鏈結串列的記憶體需求中取 $n = N$（最壞情況）。
   • 若選項敘述「比陣列多 $4N+4$ 位元組」，直接比較兩式的差值。

選項分析