110 國安局特考三等 資訊組(選試英文) 計算機概論 考古題詳解

核心觀念

本題考查 CPU 的指令週期，以及指令格式中各欄位位元數所能表示的數量。

CPU 執行一條指令，通常依序經過擷取、解碼與執行。控制單元負責解讀指令並發出控制訊號；暫存器與算術邏輯單元（ALU）則配合完成資料傳送及運算。

指令欄位若有 $n$ 個 bits，可表示 $2^n$ 種不同編碼。因此，$n$ 位元的暫存器編號欄位最多可編碼 $2^n$ 個暫存器；$n$ 位元的位址欄位最多可表示 $2^n$ 個位址。

解題方法

（一）依序說明指令擷取、解碼與執行時，CPU 組織單元中的資料傳送與控制動作。

（二）先辨認暫存器編號與記憶體位址各占幾個 bits，再分別套用 $2^n$ 計算可表示的編號數量與位址數量。

（一）機器週期的三個步驟

1. 擷取（fetch） 程式計數器（PC）保存下一條待執行指令的位址。CPU 將 PC 的內容送至記憶體位址暫存器（MAR），控制單元發出讀取訊號；記憶體再將該位址的指令送至記憶體資料暫存器（MDR），並傳入指令暫存器（IR）。擷取完成後，PC 通常更新為下一條指令的位址。

2. 解碼（decode） 控制單元分析 IR 中的指令內容，判讀運算碼以確定要執行的操作，並辨認運算元欄位所指定的暫存器、記憶體位址或其他資料。接著，控制單元安排必要的資料傳送，並產生後續執行所需的控制訊號。

3. 執行（execute） CPU 依解碼結果完成指令指定的動作。例如，算術或邏輯運算由 ALU 處理；載入指令會讀取指定的記憶體資料並寫入目標暫存器；

核心觀念

需求分頁（demand paging）是一種虛擬記憶體管理方式：程式開始執行時，不必把全部頁面載入主記憶體；只有當處理器實際存取某頁，而該頁尚未在主記憶體中，才引發缺頁中斷，由作業系統將該頁從輔助記憶體載入。

一般分頁（regular paging）則是以固定大小的頁面與頁框管理記憶體；在典型比較中，程式開始執行前，作業系統會先把程式需要的頁面載入主記憶體，再讓它執行。兩者的主要差異在於頁面何時載入。

（一）需求分頁運作於哪種系統？

需求分頁主要運作於多程式系統（multiprogramming），而非傳統單程式系統（monoprogramming）。

理由如下：

1. 主記憶體需要同時容納多個行程 多程式系統會讓多個行程同時留在主記憶體中，處理器可在行程等待 I/O 時切換至其他行程。當所有行程的全部頁面都預先載入，記憶體容易不足；需求分頁只載入目前執行所需的頁面，能降低各行程的常駐記憶體需求。

2. 利用局部性原理減少載入量 程式執行時通常只會在某一段時間內反覆使用一小部分程式碼與資料，稱為區域性（locality）。需求分頁利用時間與空間局部性，先載入正在使用的頁面，降低不必要的磁碟 I/O，讓更多行程得以同時留在記憶體。

3. 缺頁處理適合由多程式排程配合 若發生缺頁，作業系統須從輔助記憶體讀入頁面；磁碟 I/O 期間，該行程會等待。多程式系統可改由其他已就緒行程使用處理器，減少處理器閒置。

需求分頁並非在技術上絕對不能用於單程式環境；但它的主要效益，是在記憶體有限時支援多個行程並提高資源利用率，因此典型上與多程式系統搭配。

（二）需求分頁與一般分頁的差異及優缺點

核心觀念

本題考查兩項計算機概論觀念：

1. 子網路遮罩與網段判斷：將 IP 位址與子網路遮罩逐位元進行 AND 運算，求出網路位址；兩個 IP 的網路位址相同，即屬於同一個子網路。
2. 數位簽章的驗證與不可否認性：傳送者以自己的私密金鑰簽署訊息摘要，接收者使用傳送者的公開金鑰驗章，並比對訊息摘要，以驗證訊息來源及完整性。

（一）子網路判斷

解題方法

遮罩為 $255.255.255.128$，換成二進位如下：

前 25 個位元為網路部分，因此這是 /25 子網路。最後一個八位元組中，最高位元屬於網路位元，遮罩值為 $128$；其餘 7 個位元屬於主機位元。

先分別計算兩個 IP 的網路位址：

因此：

• $140.116.61.150$ 的網路位址是 140.116.61.128。
• $140.116.61.60$ 的網路位址是 140.116.61.0。

兩個網路位址不同，所以兩部電腦不屬於同一個子網路。

140.116.61.150 所在子網路的 IP 範圍

/25 代表每個子網路有 $2^{32-25}=128$ 個位址。最後一個八位元組的網段以 128 為區塊大小，範圍分成：

• $0 \sim 127$
• $128 \sim 255$

因此，包含 150 的網段是 $128 \sim 255$：

• 子網路位址：140.116.61.128
• 廣播位址：140.116.61.255
• 可用主機位址範圍：140.116.61.129 ～ 140.116.61.254
• 該子網路涵蓋的完整位址範圍：140.116.61.128 ～ 140.116.61.255

子網路位址代表該網段本身，廣播位址用於向該網段所有主機廣播；一般主機可使用的範圍不包含這兩個位址。

（二）數位簽章：訊息確認與不可否認性

核心觀念

核心觀念

二元表示樹中，運算子是內部節點，運算元是葉節點。後置運算式採用後序走訪：先走訪左子樹，再走訪右子樹，最後輸出根節點。

前置運算式則先讀運算子，再讀其左、右運算元；若運算元本身是運算式，便依序繼續解析。

解題方法

（一）求後置運算式

圖中的根節點是 $+$，左子樹為以 $\times$ 為根的樹，右子節點是 $d$。$\times$ 的左子節點是 $a$，右子樹是以 $+$ 為根、子節點為 $b$ 與 $c$ 的樹。

依後序走訪：

1. 先走訪 $\times$ 的左子節點：$a$
2. 再走訪 $\times$ 的右子樹：$b,c,+$
3. 輸出 $\times$：得到 $a,b,c,+,\times$
4. 再走訪根節點 $+$ 的右子節點：$d$
5. 最後輸出根節點 $+$

因此後置運算式為：

核心觀念

本題考查「兩數和問題」（Two Sum）：從 $k$ 個整數中，找出兩個不同位置的數 $N_i$、$N_j$，使其和等於指定的 $SUM$：

限制 $i<j$ 可避免同一對數字重複檢查，也確保不會把同一個輸入元素配對給自己。

解題方法

使用兩層迴圈列舉所有不同位置的配對。外層選定第 $i$ 個數，內層只檢查它後面的數 $N_j$。每組配對只會檢查一次。

輸入 k、N[1..k]、SUM
found ← false

for i ← 1 to k-1
 for j ← i+1 to k
 if N[i] + N[j] = SUM
 印出 (N[i], N[j])
 found ← true

if found = false
 印出「沒有任何配對和剛好等於 SUM」

以題目數列 $3,8,13,2,17,18,10$ 為例：

核心觀念

二元搜尋（binary search）適用於已排序的數列。每次取目前搜尋範圍的中間位置，將中間值與目標值比較：

• 中間值等於目標值：搜尋成功。
• 中間值小於目標值：只搜尋右半部。
• 中間值大於目標值：只搜尋左半部。

本題數列已由小到大排列，目標值為 $35$。每次比較後，搜尋範圍大致縮小為原來的一半。

解題方法

將數列以位置 $1$ 至 $11$ 編號：

以目前範圍的中間位置為比較點，中間位置可用 $\lfloor (低位 + 高位)/2 \rfloor$ 計算：

1. 第一次比較：範圍為位置 $1$ 至 $11$，中間位置為 $\lfloor(1+11)/2\rfloor=6$，數值是 $14$。 $14<35$，因此排除位置 $1$ 至 $6$，改搜尋位置 $7$ 至 $11$。