110 地方特考四等 資訊處理 計算機概要 考古題詳解

核心觀念

程式計數器（Program Counter, PC）是處理器中的特殊暫存器，用來儲存下一個要被擷取、解碼或執行之指令的記憶體位址。處理器依照 PC 所指的位址，到主記憶體擷取指令；擷取完成後，PC 通常會更新為下一個指令的位址。

因此，題目詢問「目前正在或即將被執行的指令位址」所儲存的元件，命題慣例所指即為程式計數器。

解題方法

判斷各選項的功能：

1. 是否為「專門儲存指令位址」的處理器元件？
2. 若不是，是否負責計算、選擇資料，或僅供一般用途使用？

具備「指令位址追蹤」功能的是程式計數器，因此選擇 (B)。

在一般指令循序執行時，PC 的更新可概念化表示為：

遇到跳躍、分支、函式呼叫或中斷時，PC 則會載入新的目標位址。

選項分析

(A) 加法器（adder） 錯誤。加法器是算術邏輯單元或處理器資料路徑中的組合邏輯電路，負責進行加法運算，例如計算：

它本身不負責持續儲存指令位址。

核心觀念

共享記憶體多處理器（shared memory multiprocessor）是指多個處理器共同存取同一個實體記憶體系統。其重點在於：

• 多個處理器共用同一實體記憶體位址空間。
• 各處理程序仍可擁有各自獨立的虛擬記憶體位址空間。
• 依處理器存取不同記憶體位置所需時間是否相同，可分為 UMA 與 NUMA。

其中：

• UMA（Uniform Memory Access，一致記憶體存取）：任一處理器存取任一記憶體位置，所需時間相同。
• NUMA（Nonuniform Memory Access，非一致記憶體存取）：處理器存取記憶體的時間，會因記憶體位置與處理器距離不同而有所差異。

解題方法

本題逐一檢查各選項是否符合共享記憶體多處理器、UMA、NUMA 的定義即可。

最重要的判斷是區分：

• 實體記憶體位址空間：多處理器共同使用。
• 虛擬記憶體位址空間：由各程序管理，通常彼此獨立，不必全部共用。

因此，聲稱「所有程序必須共享同一虛擬記憶體位址空間」的選項，即違反程序虛擬記憶體的基本概念。

選項分析

(A) 提供單一實體記憶體位置空間給多處理器使用

正確。共享記憶體多處理器的核心特徵，就是多個處理器可使用同一個實體記憶體位址空間。任一處理器可透過共同的位址系統存取記憶體內容。

(B) 於多處理器上的所有程序必須共享同一虛擬記憶體位置空間

錯誤。每個程序通常擁有自己的虛擬位址空間，作業系統透過虛擬記憶體與頁表，將不同程序的虛擬位址轉換至相應的實體位址。

核心觀念

指令階層平行性（Instruction-Level Parallelism, ILP）是指同一程式中，彼此沒有資料相依性的多個指令，可以在同一時間重疊或平行執行，以提高處理器效能。

發掘 ILP 的方式可分為：

• 靜態排程（static scheduling）：由編譯器在程式執行前分析指令相依性，安排哪些指令可同時執行，主要依賴軟體。
• 動態排程（dynamic scheduling）：由處理器在執行期間分析指令相依性，決定指令的發射與執行順序，主要依賴硬體。

本題問的是「需要依賴純軟體方式來發掘 ILP」的架構，因此關鍵在於判斷 ILP 是由編譯器靜態決定，還是由處理器硬體在執行時動態處理。

解題方法

判斷各選項所採用的排程機制：

1. 若由編譯器事先安排平行指令，屬於軟體發掘 ILP。
2. 若由處理器硬體在執行時判斷指令是否可平行、是否可亂序執行，屬於硬體發掘 ILP。

VLIW 將多個可同時執行的操作放入一個很長的指令字中，這些操作的組合與排程通常在編譯階段由編譯器完成。因此，VLIW 的 ILP 發掘主要依賴軟體。

【答案：A】

選項分析

(A) 很長指令字（VLIW）架構：正確

VLIW 架構的指令字很長，內含多個操作欄位，每個欄位可交給不同功能單元執行。例如，一個很長的指令字可能同時包含整數運算、浮點運算與記憶體存取操作。

VLIW 的核心特色是：

• 編譯器在編譯時分析指令間的資料相依性。
• 編譯器將彼此獨立、可平行執行的指令打包。
• 處理器執行時主要依照已排好的指令字執行。
• 硬體不必在執行期間大量分析指令相依性。

因此，VLIW 以編譯器靜態排程來發掘 ILP，符合題目所稱的純軟體方式。

(B) 超純量（superscalar）架構：錯誤

核心觀念

中央處理器執行時間（CPU execution time）是指程式在 CPU 上實際執行所耗用的時間，基本公式為：

由於：

因此也可寫成：

其中：

• Instruction Count：程式實際執行的指令總數。
• CPI（Cycles Per Instruction）：平均每一指令所需的時脈週期數。
• Clock Rate：處理器每秒產生的時脈週期數。

本題要求判斷何者「與中央處理器執行時間無關」，應直接對照上述公式。

解題方法

將各選項代入公式：

公式中直接出現：

1. 指令數（Instruction Count）
2. 每個指令時脈數（CPI）
3. 時脈速率（Clock Rate）

「快取錯失率（Cache Miss Rate）」並未直接出現在基本 CPU 執行時間公式中，因此依本題的命題架構，答案為（C）。

選項分析

（A）程式中的指令數（Instruction Count）

錯誤選項。

指令數是 CPU 執行時間的直接決定因素之一。若平均 CPI 與時脈速率固定，指令數增加，所需的總時脈週期數也會增加：

因此，執行的指令越多，CPU 執行時間通常越長。

（B）每個指令時脈數（Clock Cycles Per Instruction）

錯誤選項。

Clock Cycles Per Instruction 即 CPI，代表平均執行一個指令所需的時脈週期數。CPU 執行時間公式為：

核心觀念

本題考查管道式處理器五階段流程，以及「算術運算溢位」在何時產生。

典型五階段管線如下：

1. 擷取（Fetch）：從記憶體取得指令。
2. 解碼（Decode）：解讀指令、讀取暫存器內容。
3. 執行（Execute）：由算術邏輯單元（ALU）進行算術或邏輯運算。
4. 記憶體存取（Memory）：進行資料記憶體讀寫。
5. 寫回（Write Back）：將運算結果寫入目的暫存器。

算術指令的滿溢（overflow）是指運算結果超出資料格式可表示的範圍。以固定長度的有號整數為例，若使用 $n$ 位元二補數表示，其可表示範圍為：

當 ALU 執行加法、減法等算術運算時，才會產生實際結果與滿溢旗標，因此最早可在「執行」階段偵測。

解題方法

判斷方式是依照「哪一個階段首次真正完成算術運算」來決定。

以有號整數加法為例，若兩個運算元 $A$、$B$ 的符號相同，而結果 $S$ 的符號與它們不同，即表示發生有號加法滿溢：

這項判斷必須等到 ALU 計算出結果 $S$ 後才能完成。ALU 位於執行（Execute）階段，因此滿溢最早在執行階段被偵測。

選項分析

核心觀念

本題考查程式由原始碼轉換成可執行程式時，各系統軟體的職責分工：

1. 編譯器（compiler）：將高階語言程式轉換成組合語言或目的碼。
2. 組譯器（assembler）：將組合語言轉換成目的檔案（object file）。
3. 聯結器（linker）：合併多個目的檔案與函式庫，解析外部符號與參考，並進行位址配置及重定位。
4. 載入器（loader）：將可執行程式載入主記憶體，準備執行。

本題詢問「不是聯結器負責的工作」，應找出屬於編譯器或組譯器的工作。

解題方法

判斷每個選項是否屬於聯結器的典型工作：

• 涉及「合併目的檔案」：屬於聯結器。
• 涉及「解決外部參考」：屬於聯結器。
• 涉及「位址配置與重定位」：通常歸入聯結器的工作範圍。
• 涉及「將低階語言轉成目的檔案」：屬於組譯器，不是聯結器。

因此，不符合聯結器職責的是將低階語言轉換成目的檔案。

選項分析

(A) 負責合併來自不同程式模組的目的（object）檔案

正確。程式通常會分成多個模組，各模組先分別轉換成目的檔案，再由聯結器將這些目的檔案合併，形成完整的可執行檔案。

例如主程式呼叫另一個模組中的函式，聯結器必須將兩個模組整合在一起，建立完整的程式映像。

(B) 確保程式中沒有未解決的參考（references）

正確。若一個目的檔案呼叫了另一個模組或函式庫中的函式，這種呼叫會形成外部參考。聯結器必須尋找對應的定義，將符號參考連接至正確的函式或資料位址。

若找不到對應定義，通常會產生「未定義參考」或「無法解析的外部符號」等聯結錯誤。

核心觀念

本題考查硬碟排程中的「最短搜尋時間優先」（Shortest-Seek-Time-First, SSTF）演算法。

SSTF 的規則是：每次都從目前讀寫頭所在的磁柱出發，選擇「距離目前位置最近」的下一筆磁柱；讀取完成後，讀寫頭位置更新至該磁柱，再重新計算下一次距離。

重點是每一步都要以「讀寫頭的最新位置」計算，不能固定以起始位置磁柱 4 判斷全部順序。

解題方法

資料位置如下：

起始位置為磁柱 4。

第一步，計算各資料與磁柱 4 的距離：

距離最近的是 B，因此先讀取 B，讀寫頭移至磁柱 5。

第二步，以磁柱 5 為目前位置：

距離最近的是 C，因此讀取 C，讀寫頭移至磁柱 8。

第三步，以磁柱 8 為目前位置：

距離最近的是 D，因此讀取 D，讀寫頭移至磁柱 9。

核心觀念

本題考查各種 RAID（Redundant Array of Independent Disks，獨立磁碟冗餘陣列）的資料配置方式，以及其正常運作所需的最低磁碟機數量。

常見 RAID 等級如下：

• RAID 0：資料分割（Striping），不具備容錯能力。
• RAID 1：資料鏡像（Mirroring）。
• RAID 2：以位元為單位分割資料，並使用漢明碼（Hamming Code）進行錯誤更正。
• RAID 5：資料與同位檢查資訊分散配置，具備單一磁碟故障容錯能力。
• RAID 1+0：先鏡像，再分割資料，兼具效能與容錯能力。

本題依命題慣例判斷各 RAID 等級的最低磁碟數量。

解題方法

判斷重點是：各 RAID 等級的資料配置與冗餘資訊，至少需要幾顆磁碟才能形成完整陣列。

因此，題目所列的「至少需要 2 顆」若用於 RAID 2，與一般考試採用的 RAID 規格表不符，故錯誤選項為 B。

選項分析

(A) RAID 0 至少需要 2 顆：正確

RAID 0 將資料分割後，分散寫入兩顆以上的磁碟，以提升平行讀寫效能。

若只有一顆磁碟，便無法形成「分散」配置，因此至少需要：

RAID 0 不提供鏡像或同位檢查，任一磁碟故障都可能造成整個陣列資料損失，但這不影響其最低磁碟數為 2 顆。

(B) RAID 2 至少需要 2 顆：錯誤

核心觀念

本題考查 32 位元單精確度 IEEE 754 浮點數格式：

其數值公式為：

其中：

• $S$：符號位元，$0$ 表示正數，$1$ 表示負數。
• $E$：以偏移值 $127$ 儲存的指數。
• $F$：小數部分，正常化數值的整數部分省略為隱含的 $1$。

解題方法

先將 $-18.625$ 轉換為二進位。

整數部分：

小數部分：

因此：

將其正常化：

1. 符號位元

因為數值為負數：

2. 指數部分

實際指數為 $4$，加上偏移值 $127$：

將 $131$ 轉換為 8 位元二進位：

3. 小數部分

正常化後的數值為：

省略最前面的隱含位元 $1$，小數部分為：

補足 23 位元：

4. 組合三個欄位

完整 32 位元表示為：

每 4 位元分組：

所以正確選項為 (D)。

選項分析

(A) $1000\;0010\;0100\;1010\;1000\;0000\;0000\;0000$

• 符號位元為 $1$，表示負數，這部分正確。
• 指數部分為 $10000010_2=130$，實際指數為：

核心觀念

本題考查記憶體的分類、揮發性，以及 DRAM、SRAM 與 ROM 的用途和容量特性。

• 讀寫記憶體（RWM）：可讀取也可寫入，常見類型包括 DRAM 與 SRAM。
• 唯讀記憶體（ROM）：主要供系統讀取資料，內容在斷電後仍能保留，屬於非揮發性記憶體。
• DRAM：以電容儲存資料，必須定期更新內容，容量大、成本低，常作為主記憶體。
• SRAM：以正反器電路儲存資料，不需定期更新，速度快但成本高、單位面積容量較小，常作為快取記憶體。
• BIOS：屬於主機板韌體，通常儲存在 ROM 類型的非揮發性記憶體中。

判斷本題的關鍵，是比較各類記憶體的「斷電後資料是否保留」、「單位成本與容量」及「典型用途」。

解題方法

逐一檢查各選項：

1. ROM 是否具有揮發性？
2. 一般計算機中 ROM 與 RWM 的容量大小關係。
3. SRAM 與 DRAM 的容量及成本特性。
4. BIOS 實際儲存在哪一類記憶體中。

其中，DRAM 通常作為容量較大的主記憶體；SRAM 雖然速度較快，但成本高、密度低，因此容量通常小於 DRAM。ROM 則主要存放開機程式與韌體，所需容量通常小於主記憶體。

選項分析

(A) 唯讀記憶體為揮發性的

錯誤。

揮發性記憶體在電源中斷後，儲存內容會消失，典型例子是 DRAM 與 SRAM。

ROM 的主要特性是斷電後仍能保存資料，因此屬於非揮發性記憶體。BIOS 等開機所需程式必須在關機後仍然存在，正是因為它儲存在非揮發性記憶體中。

(B) 計算機中的唯讀記憶體容量比讀寫記憶體小

正確，為本題答案。

在一般計算機系統中：

• RWM 中的 DRAM 通常作為主記憶體，需提供作業系統、應用程式及執行中資料使用，因此容量較大。
• ROM 主要存放 BIOS、韌體或固定的系統啟動程式，所需儲存空間通常較小。

因此，從現實世界中一般計算機的配置而言，ROM 容量通常小於 RWM 容量。

核心觀念

本題考「區段記憶體管理（segmentation）」與「分頁記憶體管理（paging）」的差異。

區段記憶體管理是依照程序的邏輯結構，將程序分成大小不固定的區段，例如：

• 程式碼區段（code segment）
• 資料區段（data segment）
• 堆疊區段（stack segment）
• 函式或模組區段

每個區段通常需配置一段連續的實體記憶體，並以「區段編號＋區段內位移」表示位址。系統會使用區段表（segment table）記錄各區段的起始位址與長度。

由於各區段大小不同，配置與釋放後容易在記憶體中留下大小不一的空閒區塊，因此會產生外部碎片（external fragmentation）。

解題方法

判斷本題可掌握三個特徵：

1. 最小配置單位是區段，不是分頁。
2. 區段大小不固定。
3. 通常以區段表記錄區段位置，且可能產生外部碎片。

逐一比對選項後，只有敘述「可能產生外部碎片」符合區段記憶體管理的特性。

選項分析

(A) 記憶體將以一個分頁（page）作為最小的配置單位

錯誤。

以分頁作為固定大小配置單位，是分頁記憶體管理的特徵。區段記憶體管理以區段作為主要配置單位，且區段大小可依程序的邏輯需求而不同。

分頁管理通常會產生內部碎片；區段管理則因區段大小不一且通常需連續配置，容易產生外部碎片。

(B) 同一個程序中的不同區段，大小皆相同

錯誤。

區段是依程序的邏輯用途劃分，大小不必相同。例如程式碼區段、資料區段與堆疊區段所需的容量通常不同，因此區段屬於「可變大小」的記憶體配置單位。

固定大小是分頁管理的特徵，不是區段管理的特徵。

(C) 一個程序需要一個分頁表（page table）來記錄每個區段所在的位置

核心觀念

本題考查不同無號數進制的數值轉換與減法運算。不同進制的表示法，必須先換算成相同進制，才能比較大小。

常用轉換公式為：

其中 $b$ 為進制，$a_i$ 為各位數字。

解題方法

逐一將各選項的運算結果換算成十進位：

(A) $(1000001-100000)_2$

因此：

所以 (A) 的值為 $33$。

(B) $(76-34)_8$

因此：

所以 (B) 的值為 $34$。

(C) $(73-38)_{10}$

因為本身就是十進位：

所以 (C) 的值為 $35$。

(D) $(\text{CD}-\text{AF})_{16}$

十六進位中：

核心觀念

本題考查浮點數格式中各欄位的位元數，以及「精確度（precision）」所代表的意義。

圖示共有 $32$ 位元：

• $S$：第 $0$ 位，符號位元，共 $1$ 位。
• $C$：第 $1$ 至第 $8$ 位，指數欄位，共 $8$ 位。
• $M$：第 $9$ 至第 $31$ 位，尾數欄位，共 $23$ 位。

題目特別指出：小數點在 mantissa 的最左端，且小數點右邊第一位位元恆不為 $0$，並且「必須儲存」為精確度的位元之一。因此，精確度就是實際儲存在 $M$ 欄位中的位元數。

解題方法

尾數欄位 $M$ 的範圍為第 $9$ 位至第 $31$ 位，計算如下：

因此，尾數實際儲存 $23$ 位元。由於小數點右邊第一位也必須儲存，不能視為隱藏位元，所以浮點數表示法的精確度為：

指數欄位使用偏移值 $127$，只影響指數的表示方式，不影響精確度位元數。

核心觀念

本題考查不同進位制數字的轉換與大小比較。

進位制數字的位值公式為：

其中：

• 整數部分依各位數乘以 $b^0,b^1,b^2,\ldots$
• 小數部分依各位數乘以 $b^{-1},b^{-2},b^{-3},\ldots$

比較不同進位制數字時，必須先轉換成相同進位制，通常轉換為十進位最直接。

解題方法

① $110010.1011_2 < 65_8$

先將二進位轉為十進位：

小數部分為：

因此：

再將八進位轉為十進位：

比較可得：

所以第①式正確。

② $2_{10} < 10_4$

四進位的 $10_4$ 表示：

因此：

所以第②式正確。

③ $330.625_{10} < 506.5_8$

將八進位轉為十進位：

核心觀念

本題考查「有理數在不同進制下能否有限表示」的判斷方法。

將十進制小數化為最簡分數後，若分母的所有質因數都能在進制的基數中找到，該數即可用有限位數表示。

例如：

• $2$ 進制的基數質因數為 $2$
• $3$ 進制的基數質因數為 $3$
• $4$ 進制的基數質因數為 $2$
• $5$ 進制的基數質因數為 $5$

題目中的數為：

小數部分的最簡分母為 $5$，因此必須選擇基數含有質因數 $5$ 的進制。

解題方法

整數部分 $2468$ 在任何整數進制中都能以有限位數表示，判斷關鍵在於小數部分：

在 $5$ 進制中：

所以：

再將整數部分 $2468$ 轉為 $5$ 進制：

因此：

合併後：

這是有限位數的 $5$ 進制表示。

選項分析

(A) 2 進制：錯誤

$2$ 進制的基數只有質因數 $2$，但小數部分為：

分母含有質因數 $5$，無法在 $2$ 進制中有限表示，會形成循環小數。

例如小數部分轉換時：

核心觀念

多工器（Multiplexer, MUX）會根據「選擇輸入訊號」的二進位組合，從多組資料輸入中選出一組，送至輸出端。

若多工器有 $n$ 個選擇輸入位元，能表示的選擇狀態數為：

4-to-1 多工器共有 4 組資料輸入，必須能選擇其中任意 1 組，因此需要的選擇狀態數為 4。

解題方法

設需要 $n$ 個選擇輸入位元，則：

因此：

兩個選擇輸入位元可形成 4 種組合：

所以 4-to-1 多工器需要 2 個位元的選擇輸入訊號。

選項分析

核心觀念

本題考查：

• 四變數布林函數的最小項表示法。
• 隨意項（don’t care）的使用。
• 卡諾圖分組與布林代數化簡。
• 隨意項可視為 $1$ 或 $0$，應選擇有利於化簡的方式，但不能使原本的必要最小項消失。

題目給定：

其中 $m$ 為必須使函數值為 $1$ 的最小項，$d$ 為可自由設定的隨意項。

解題方法：利用卡諾圖分組

四變數最小項以 $ABCD$ 的二進位表示：

隨意項為：

$10=1010,\quad 11=1011,\quad 12=1100,\quad 13=1101,\quad 14=1110,\quad 15=1111$

在卡諾圖中，可利用隨意項擴大分組。

第一組取：

其二進位如下：

$0001,\ 0101,\ 1001,\ 1101$

在此群組中，$A$、$B$ 皆有變化，$C=0$、$D=1$ 固定，因此化簡為：

第二組取：

其二進位如下：

$0010,\ 0110,\ 1010,\ 1110$

在此群組中，$A$、$B$ 皆有變化，$C=1$、$D=0$ 固定，因此化簡為：

所以：

這正是選項（C）。

選項分析

（A）$\bar{A}B+A\bar{B}$

此式代表 $A$ 與 $B$ 互異，也就是 $A\oplus B$。

檢查必要最小項 $m(1)$：

此時 $A=0,B=0$，因此：

但題目指定 $m(1)$ 必須為 $1$，故選項（A）錯誤。

（B）$\bar{A}C+A\bar{C}$

核心觀念

本題考查布林函數轉換為「正規最小項和」的表示法。正規最小項和要求：

• 每一項都必須包含所有變數 $A、B、C$。
• 函數值為 $1$ 的輸入組合，轉換成對應的最小項 $m_i$。
• 最小項編號依變數順序 $ABC$ 的二進位值決定，其中 $A$ 為最高位元。

例如：

• $ABC=001$，對應 $m_1$；
• $ABC=111$，對應 $m_7$。

解題方法一：代數展開

原函數為：

先將每一項補入缺少的變數。

對 $AB$ 而言，利用 $C+\bar{C}=1$：

對 $\bar{A}C$ 而言，利用 $B+\bar{B}=1$：

因此：

依照 $ABC$ 的排列順序，逐項判定最小項編號：

所以：

因此選擇：

解題方法二：直接列出函數為 $1$ 的情況

原式：

第一部分 $AB=1$ 的條件是 $A=1、B=1$，此時 $C$ 可為 $0$ 或 $1$：

• $ABC=110\Rightarrow m_6$
• $ABC=111\Rightarrow m_7$

第二部分 $\bar{A}C=1$ 的條件是 $A=0、C=1$，此時 $B$ 可為 $0$ 或 $1$：

核心觀念

雙向移位器由多個 D 型正反器組成，用來儲存資料；每個正反器的輸入端 $D$，必須依控制訊號選擇不同來源：

• 向左移位：接收右側相鄰正反器的輸出。
• 向右移位：接收左側相鄰正反器的輸出。
• 邊界位置：接收外部串列輸入或補入指定值。

因此，每個 D 型正反器的 $D$ 輸入端需要在兩個以上資料來源中進行選擇，最適合使用多工器（Multiplexer, MUX）。

解題方法

以 4 位元雙向移位器為例，設正反器輸出為 $Q_3,Q_2,Q_1,Q_0$，方向控制訊號為 $S$。

以 $Q_1$ 所對應的正反器為例：

• 向左移位時，$D_1$ 應接收 $Q_0$。
• 向右移位時，$D_1$ 應接收 $Q_2$。

因此，$D_1$ 的輸入可表示為：

這正是 2 對 1 多工器的功能：

其他各位元的 D 輸入也以相同方式，利用多工器依方向控制訊號選擇左、右相鄰位元的資料。故雙向移位器除了 D 型正反器外，最適合使用的邏輯元件是多工器。

選項分析

(A) 編碼器（Encoder）錯誤

編碼器的功能是將多條輸入線中的啟用訊號，轉換成較少位元的二進位編碼。例如將 $8$ 條輸入編碼成 $3$ 位元輸出。

核心觀念

本題考查「加權碼」的表示方式。$84\text{-}2\text{-}1$ 碼的四個位元權值依序為：

每一個十進制數字以 4 個位元表示，位元值為 $1$ 的權值相加後，必須等於該十進制數字。十進制數 $58$ 必須拆成兩個數字「5」與「8」分別編碼，再串接為 8 位元。

解題方法

先求十進制數字 $5$ 的 $84\text{-}2\text{-}1$ 碼：

因此四個位元依序為：

再求十進制數字 $8$ 的編碼：

因此四個位元為：

將「5」與「8」的編碼依序串接：

所以：

選項分析

• (A) $10111000$：正確

前四位 $1011$ 表示：

後四位 $1000$ 表示：

核心觀念

本題考查一階述詞邏輯中的：

• 全稱量詞 $(\forall x)$：表示「對所有的 $x$」。
• 蘊涵符號 $\rightarrow$：表示「若……則……」。
• $\text{dog}(x)$：$x$ 是狗。
• $\text{black}(x)$：$x$ 是黑色的。

題目公式為：

其完整意思是：

對所有的 $x$ 而言，只要 $x$ 是狗，$x$ 就是黑色的。

因此可翻譯為「所有的狗都是黑色的」。

解題方法

判讀蘊涵式時，先確認箭頭兩側的方向：

表示：

若 $A$，則 $B$。

本題中：

• 前件 $A=\text{dog}(x)$：$x$ 是狗。
• 後件 $B=\text{black}(x)$：$x$ 是黑色。

所以公式要求的是：

也就是「狗」是條件，「黑色」是結果，不能將兩者對調。

選項分析

(A) 所有動物中的狗都是黑色的

此選項可理解為「在動物範圍內，所有狗都是黑色的」。若題目明確將論域限定為所有動物，則其意思與本題公式相近；但原公式本身只表達「所有狗都是黑色的」，沒有額外加入「動物中的」這項限制。

依題目公式的直接、標準翻譯，應選擇表達最完整且最精確的 (C)，因此 (A) 不作為標準答案。

(B) 所有動物中黑色的都是狗

此選項表示：

若某個動物是黑色的，則它是狗。

形式上較接近：

核心觀念

本題考查 UML 各類圖形的用途，重點在於辨識「結構模型」與「行為模型」：

• 類別圖（Class Diagram）：描述類別、屬性、方法及類別間的靜態關係。
• 部署圖（Deployment Diagram）：描述系統軟體元件配置於硬體節點的情形。
• 物件圖（Object Diagram）：描述特定時間點的物件實例及其關係。
• 循序圖（Sequence Diagram）：描述物件或參與者之間傳遞訊息的內容，以及訊息發生的先後順序。

題目中的關鍵語句是「物件間的訊息傳遞與順序」，這正是循序圖的核心功能。

解題方法

判斷 UML 圖形時，可先找題幹關鍵字：

• 出現「類別、屬性、方法、繼承、關聯」：偏向類別圖。
• 出現「硬體節點、伺服器、裝置、部署」：偏向部署圖。
• 出現「物件實例、某一時間點的狀態」：偏向物件圖。
• 出現「訊息、呼叫、生命線、時間順序」：偏向循序圖。

循序圖以垂直方向表示時間先後，並以物件或參與者的生命線表示互動對象；訊息通常由一條生命線指向另一條生命線，用來呈現方法呼叫或訊息傳遞的順序。

因此，本題答案為 （D）循序圖。

選項分析

（A）類別圖（Class Diagram）錯誤

類別圖屬於 UML 的結構圖，主要描述：

• 類別名稱
• 屬性
• 操作或方法
• 繼承、關聯、聚合、組合及相依等關係

它著重於系統中「有哪些類別」及「類別彼此如何關聯」，屬於較靜態的設計觀點，並非用來表示物件之間訊息傳遞的時間順序。

核心觀念

本題考查 C++ 的「純虛擬函式」與「抽象類別（abstract class）」。

在 C++ 中，將虛擬函式宣告為純虛擬函式，通常寫成：

virtual void show = 0;

只要類別中含有至少一個純虛擬函式，該類別就是抽象類別。抽象類別具有以下特性：

1. 不能直接建立物件。
2. 可以被其他類別繼承。
3. 衍生類別必須實作所有繼承而來的純虛擬函式，才能成為具體類別。
4. 衍生類別也可以不實作純虛擬函式，此時衍生類別仍是抽象類別。
5. 同一類別可以同時具有純虛擬函式與一般虛擬函式。

解題方法

判斷各選項是否正確時，應分別檢查純虛擬函式對「建立物件」、「繼承關係」及「函式種類」的影響。

關鍵區分如下：

• 「不能建立物件」是抽象類別的限制。
• 「不能繼承其他類別」並不是抽象類別的限制。
• 抽象類別仍然可以作為基底類別，被其他類別繼承。

因此，只要找出把「不能建立物件」誤植成「不能繼承其他類別」的選項，即可判定答案。

選項分析

(A) 一個類別如果含有純虛擬函式，則該類別無法用來建立一個物件

正確。

含有純虛擬函式的類別屬於抽象類別，不能直接宣告該類別的物件。例如：

class Animal {
public:
 virtual void speak = 0;
};

Animal a; // 錯誤：Animal 是抽象類別

不過，抽象類別可以作為基底類別，透過具體的衍生類別建立物件：

class Dog : public Animal {
public:
 void speak override {}
};

Dog d; // 正確

因此，A 的敘述正確。

(B) 一個類別如果含有純虛擬函式，則該類別無法繼承其他類別

錯誤，故為本題答案。

含有純虛擬函式的類別雖然不能直接建立物件，但仍然可以繼承其他類別。例如：

class Base {
public:
 virtual void run {}
};

class Derived : public Base {
public:
 virtual void show = 0;
};

Derived 同時繼承了 Base，並且自行宣告純虛擬函式 show。因此，含有純虛擬函式並不會限制類別的繼承能力。

核心觀念

本題考查 Python 的下列觀念：

1. 串列（list）是可變動（mutable）的資料型態。
2. 函式參數傳遞的是物件參考；函式內的參數 list 與外部的串列指向同一個串列物件。
3. 透過索引指定值，例如 list[2] = 7，會直接修改原串列。
4. Python 串列索引從 $0$ 開始，因此：

各索引對應為：

所以 list[2] 的初始值是 $3$。

解題方法

依照程式執行順序逐行判斷：

1. 執行：

print(list[2])

此時 list[2] = 3，輸出第一個數字：

$3$

2. 呼叫：

function(list)

函式參數 list 指向外部同一個串列。

3. 函式內執行：

print(list[2])

尚未修改串列內容，因此輸出第二個數字：

$3$

4. 執行：

list[2] = 7

這會直接將原串列的第 2 索引元素由 $3$ 改為 $7$。串列變成：

[1, 2, 7, 4]

5. 函式內再次執行：

print(list[2])

此時 list[2] = 7，輸出第三個數字：

$7$

6. 函式結束後執行：

核心觀念

本題考查二維陣列在「列為主（Row-Major）」儲存方式下的記憶體位址計算。

Row-Major 的排列方式是：先連續存放同一列的所有元素，再存放下一列。每列有 $4$ 個元素，因此從一列移動到下一列，記憶體位址增加 $4$。

兩個元素間的位址差可用下式計算：

解題方法

已知：

• $A[6][3]$ 的記憶體位址為 $1022$
• 共有 $4$ 行
• 每個元素占用 $1$ 個記憶體位址
• 採用 Row-Major

從 $A[1][1]$ 移動到 $A[6][3]$：

1. 列由 $1$ 移動到 $6$，相差 $5$ 列，每列有 $4$ 個元素：

2. 行由 $1$ 移動到 $3$，相差 $2$ 個元素：

3. 總位址差：

因此：

所以 $A[1][1]$ 的記憶體位址為 $1000$。

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的走訪、搜尋、插入與刪除之時間複雜度。

BST 的基本性質為：

• 左子樹所有節點的鍵值小於根節點。
• 右子樹所有節點的鍵值大於根節點。
• 每個子樹本身也符合二元搜尋樹性質。

時間複雜度主要取決於樹高 $h$：

• 搜尋：$\Theta(h)$
• 插入：$\Theta(h)$
• 刪除：$\Theta(h)$
• 中序走訪全部節點：$\Theta(n)$

若樹形極度偏斜，樹高可能為 $n$；若樹形平衡，樹高約為 $\log n$。最佳狀況則可能只需處理根節點，時間為 $\Theta(1)$。

解題方法

逐一判斷各操作在題目所指定的最佳或最差狀況下之時間複雜度：

1. 需要走訪全部 $n$ 個節點的操作，通常為 $\Theta(n)$。
2. 只需沿著樹高搜尋或移動的操作，其複雜度為 $\Theta(h)$。
3. 最差狀況使用 $h=n$。
4. 最佳狀況若目標節點就在根節點，且刪除不需額外處理，則為 $\Theta(1)$。

選項分析

(A) 由根節點開始，以中序方式走訪此二元搜尋樹的時間複雜度為 $\Theta(n)$

此敘述正確。

中序走訪順序為：

1. 走訪左子樹
2. 處理根節點
3. 走訪右子樹

無論 BST 的形狀為何，都必須訪問全部 $n$ 個節點。每個節點只處理固定次數，因此總時間為：

即使樹形平衡，中序走訪仍需輸出所有節點，不能降為 $\Theta(\log n)$。

(B) 在最差狀況下搜尋一個數值的時間複雜度為 $\Theta(n)$

此敘述正確。

BST 搜尋時，從根節點開始，每次比較後選擇左子樹或右子樹，因此最多沿著一條根到葉節點的路徑進行搜尋，時間複雜度為：

核心觀念

本題考查完滿二元樹（perfect binary tree）的結構與節點數量公式。

依題目定義：

• 根節點深度為 $0$
• 每往下一層，深度增加 $1$
• 所有葉節點深度相同
• 每個非葉節點的分支度為 $2$

因此，高度為 $15$ 表示樹的節點深度從 $0$ 到 $15$，共 $16$ 層；且每一層的節點數量都是前一層的 $2$ 倍。

解題方法

深度為 $i$ 的節點數量為：

高度為 $15$，所以總節點數為各層節點數量總和：

這是首項為 $1$、公比為 $2$ 的等比級數：

計算得：

因此，完滿二元樹共有 $65535$ 個節點。

也可直接使用完滿二元樹的節點數公式：

其中 $h$ 為高度。代入 $h=15$：

選項分析

• (A) 32767：錯誤

$32767=2^{15}-1$

這是高度為 $14$ 的完滿二元樹節點數：

核心觀念

本題考查作業系統的「最短剩餘時間優先」排程法（Shortest Remaining Time First, SRTF）。

SRTF 是「可搶先式」的最短工作優先排程：

• 每一時刻選擇剩餘 CPU 執行時間最短的程序。
• 新程序到達時，若其 CPU Burst Time 小於目前執行程序的剩餘時間，便搶先執行。
• 若剩餘時間相同，通常採用先到先服務（FCFS）或讓目前程序繼續執行。

程序等待時間公式為：

解題方法

各程序資料如下：

依 SRTF 排程，遇到剩餘時間相同時，依先到先服務處理：

$t=0$ 至 $t=1$

只有 P1 到達，因此執行 P1。

• P1 已執行 1 單位
• P1 剩餘時間為 $4-1=3$

$t=1$ 至 $t=2$

此時 P2、P3 到達：

• P1 剩餘 3
• P2 剩餘 2
• P3 剩餘 1

選擇剩餘時間最短的 P3，執行完畢。

$t=2$ 至 $t=4$

此時 P4 到達，程序剩餘時間為：

• P1：3
• P2：2
• P4：2

P2 與 P4 剩餘時間相同，P2 較早到達，因此先執行 P2。即使 $t=3$ 時 P5 到達，P2 此時剩餘時間為 1，與 P5 的 CPU Burst Time 同為 1，依同值時讓原程序繼續執行的原則，P2 執行至 $t=4$ 完成。

$t=4$ 至 $t=5$

剩餘程序：

• P1：3
• P4：2
• P5：1

選擇 P5，於 $t=5$ 完成。

$t=5$ 至 $t=7$

剩餘：

• P1：3
• P4：2

選擇 P4，於 $t=7$ 完成。

$t=7$ 至 $t=10$

最後執行 P1，於 $t=10$ 完成。

完整排程如下：

核心觀念

本題考的是多執行緒環境下的 thread-safe（執行緒安全）函數。

若多個執行緒同時執行同一函數，函數仍能維持資料正確性，不產生資料競爭（data race）、不使共享資料遭到不一致的修改，即可稱為具備執行緒安全性。

執行緒安全的核心在於：

• 共享資料必須受到適當同步機制保護。
• 同一時間只能讓一個執行緒修改特定共享資料。
• 常見保護方式包括 mutex、lock、semaphore、atomic operation 等。

因此，本題應從「是否能避免多執行緒同時存取共享資料造成衝突」切入判斷。

解題方法

逐一檢查各選項是否為 thread-safe 函數的必要特性：

1. 是否完全禁止系統呼叫？
2. 是否保護共享全域變數？
3. 是否禁止遞迴？
4. 是否禁止忙碌等待？

其中只有「妥善處理共享資料」直接涉及執行緒安全的核心定義，因此選擇 B。

選項分析

(A) 在函數中不可以呼叫任何系統呼叫（system calls）

錯誤。

系統呼叫本身不代表函數不具備執行緒安全性。許多系統呼叫可以由多個執行緒安全地使用，例如檔案操作、記憶體配置或執行緒同步相關的系統服務。

是否 thread-safe，取決於系統呼叫所操作的資源，以及是否具有適當的同步控制。例如，多個執行緒同時寫入同一檔案時，必須處理檔案位置與寫入順序；但這不代表函數完全不能呼叫系統呼叫。

因此，「不可呼叫任何系統呼叫」不是必要條件。

(B) 在函數中所有用到的共享全域變數（shared global variables）都會加以保護，以保證一次只有一個執行緒可以修改其值

正確，為本題官方答案。

共享全域變數可被多個執行緒同時存取。若一個執行緒正在修改變數，另一個執行緒也同時讀取或修改，可能產生資料競爭，使結果取決於執行時序。

例如，下列操作並非單一不可分割動作：

它通常包含：

1. 讀取 $x$；
2. 將 $x$ 加 $1$；
3. 將結果寫回 $x$。

若兩個執行緒同時執行，可能發生：

• 執行緒甲讀取 $x=0$；
• 執行緒乙也讀取 $x=0$；
• 執行緒甲寫回 $1$；
• 執行緒乙寫回 $1$。

最後結果為 $1$，而非預期的 $2$。

核心觀念

本題考虛擬記憶體的有效記憶體存取時間（Effective Memory-Access Time, EAT）與分頁錯誤比率（Page Fault Rate）的關係。

設定：

• 一般記憶體存取時間：$120\text{ ns}$
• 平均分頁錯誤處理時間：$8\text{ ms}$
• 分頁錯誤比率：$p$
• 有效記憶體存取時間上限：$130\text{ ns}$

分頁錯誤處理時間遠大於一般記憶體存取時間，因此即使分頁錯誤比率極低，也會明顯增加平均存取時間。

解題方法

先統一時間單位：

採用考試常見的近似公式：

代入題目條件：

因此：

這表示分頁錯誤比率約為：

換算成「平均每幾次記憶體存取發生一次分頁錯誤」：

所以分頁錯誤發生頻率必須約低於每 $80$ 萬次記憶體存取一次，亦即分頁錯誤比率不能高於約 $1/800,000$。

較精確地將一般存取時間納入加權平均：

令其不大於 $130$ ns：

其倒數仍約為 $80$ 萬次，因此不影響選項判斷。

選項分析

核心觀念

本題考查雲端計算的服務模式，主要區分：

• SaaS（Software as a Service，軟體即服務）：直接使用雲端供應商提供的完整應用軟體。
• PaaS（Platform as a Service，平台即服務）：使用雲端供應商提供的開發、執行與部署平台，建置並提供自己的應用程式或資料庫服務。
• IaaS（Infrastructure as a Service，基礎設施即服務）：租用虛擬主機、儲存設備、網路等基礎運算資源。
• TaaS（Test as a Service，測試即服務）：由雲端提供軟體測試、效能測試或相容性測試等功能。

本題的關鍵在於「建置一個生物資訊資料庫給研究人員使用」。題目描述的是建構並部署一項資料服務，而非單純使用現成軟體，因此屬於平台即服務。

解題方法

判斷雲端服務模式時，可先看使用者在雲端中扮演的角色：

1. 若只是直接操作供應商已完成的軟體，屬於 SaaS。
2. 若使用供應商提供的開發環境、資料庫環境及部署平台，建置自己的系統，屬於 PaaS。
3. 若自行管理作業系統、應用程式與資料，只租用虛擬硬體資源，屬於 IaaS。
4. 若主要需求是進行軟體或系統測試，屬於 TaaS。

本題要建立生物資訊資料庫，通常需要使用雲端提供的資料庫引擎、程式執行環境、開發工具與部署機制，再由建置者設計資料結構及服務功能，提供網際網路研究人員查詢。因此符合 PaaS 的定義。

選項分析

(A) SaaS：錯誤

SaaS 是直接使用雲端供應商提供的完整軟體，例如線上文書處理、網路郵件或雲端客戶關係管理系統。

核心觀念

本題考查磁碟排程演算法及磁頭移動距離。

• FCFS：依照要求進入磁碟佇列的先後順序服務。
• SSTF：每次選擇距離目前磁頭位置最近的要求。
• SCAN：磁頭沿固定方向移動，服務沿途要求；到達磁軌端點後反向移動。本題指定先往磁軌 $0$ 的方向移動，因此需先走到磁軌 $0$，再反向服務其餘要求。
• 磁頭移動距離為相鄰兩次磁軌位置差的絕對值：

$\text{移動距離}=|目前磁軌-下一個磁軌|$

解題方法

目前磁頭位於磁軌 $100$，要求順序為：

$65,\ 87,\ 4,\ 106,\ 187,\ 31,\ 145$

一、FCFS

依原始順序服務：

$100\rightarrow65\rightarrow87\rightarrow4\rightarrow106\rightarrow187\rightarrow31\rightarrow145$

各段移動距離為：