110 調查局特考三等 電子科學組 計算機概論 考古題詳解

核心觀念

本題涵蓋計算機組織與作業系統的基本觀念：

• 中斷的四種常見類別。
• 記憶體階層的區域性。
• 作業系統時間片與程序排程。
• I/O 命令種類。
• 不同進位制轉換。
• 三變數卡諾圖化簡。

---

（一）常見的四種中斷類別

核心觀念

計算機中常見的中斷來源可分為四類：

1. 程式中斷（Program）
2. 時間中斷（Timer）
3. I/O 中斷（I/O）
4. 硬體故障中斷（Hardware failure）

題目已給出程式中斷，因此另外三種為：

【答案】

• 時間中斷（Timer interrupt）
• I/O 中斷（I/O interrupt）
• 硬體故障中斷（Hardware failure interrupt）

解題技巧

可記憶為：

$\text{Program、Timer、I/O、Hardware failure}$

其中：

• 程式中斷：例如除以零、溢位、非法指令。
• 時間中斷：由計時器產生，用於分時系統與排程。
• I/O 中斷：I/O 裝置完成資料傳輸或發生錯誤時產生。
• 硬體故障中斷：例如電源異常、記憶體錯誤或硬體失效。

---

（二）記憶體階層的兩種局部性

核心觀念

記憶體階層利用程式存取資料的局部性，讓高速但容量小的記憶體，例如快取記憶體（Cache），提高整體存取速度。

兩種局部性如下：

1. 時間局部性（Temporal locality）
2. 空間局部性（Spatial locality）

【答案】

• 時間局部性：某一筆資料若最近被使用，短時間內再次被使用的機率很高。
• 空間局部性：某一筆資料被使用後，其鄰近位置的資料很可能很快被使用。

解題技巧

• 「同一筆資料重複使用」是時間局部性。
• 「附近資料一起被使用」是空間局部性。

例如迴圈反覆使用同一變數，屬於時間局部性；陣列依序讀取相鄰元素，屬於空間局部性。

---

（三）時間片與程序數量

核心觀念

時間片（Time slice）是作業系統分配給程序執行的一小段處理器時間。

已知：

$1\text{ 秒}=1000\text{ 毫秒}$

每一個時間片為：

$10\text{ 毫秒}$

第一問：每個程序均使用完整時間片

可分配的時間片數為：

$\frac{1000}{10}=100$

【答案】

$1$ 秒鐘內有 $100$ 個程序可以各獲得一個時間片。

第二問：一半程序只使用一半時間

假設共有 $N$ 個程序，其中一半使用完整時間片，另一半只使用一半時間。

• 一半程序使用時間：$10$ 毫秒
• 另一半程序使用時間：$5$ 毫秒

總使用時間為：

$\frac{N}{2}(10)+\frac{N}{2}(5)=1000$

整理得：

$5N+2.5N=1000$

$7.5N=1000$

$N=\frac{1000}{7.5}=133.\overline{3}$

因此最多可容納的完整程序數為：

$\boxed{133}$

【答案】

約有 $133$ 個程序可以在 $1$ 秒鐘內獲得一個時間片。

若嚴格要求程序必須分成完全相等的兩半，程序數須為偶數，則可取 $132$ 個；一般考試以平均每程序耗時 $7.5$ 毫秒計算，答案採 $133$ 個。

解題技巧

先將時間單位統一為毫秒，再以「平均每個程序耗用時間」計算：

$\frac{10+5}{2}=7.5\text{ 毫秒}$

所以：

$\frac{1000}{7.5}\approx133$

常見錯誤是直接以 $100$ 個時間片乘以 $2$，忽略只有一半程序能節省時間。

---

（四）I/O 命令種類

核心觀念

處理器對 I/O 模組下達命令時，常見的 I/O 命令可分為四類：

1. 控制（Control）
2. 測試（Test）
3. 讀取（Read）
4. 寫入（Write）

題目已給出控制命令，因此另外三種為：

【答案】

• 測試（Test）
• 讀取（Read）
• 寫入（Write）

各命令功能

• 控制命令：要求 I/O 模組執行特定操作，例如啟動或停止裝置。
• 測試命令：查詢 I/O 模組或周邊裝置的狀態。
• 讀取命令：從周邊裝置取得資料並傳送至處理器或記憶體。
• 寫入命令：將處理器或記憶體中的資料傳送至周邊裝置。

解題技巧

可記成：

$\text{Control、Test、Read、Write}$

題目問「除了控制外的三種」，直接列出 $Test$、$Read$、$Write$ 即可。

---

（五）進位制轉換

1. 八進制數值 $2047.16$ 轉為二進制

核心觀念

每一位八進制數字可直接對應三位二進制數字：

$1\text{ 個八進制位數}=3\text{ 個二進制位數}$

對應如下：

$$\begin{array}{c|c} \text{八進制} & \text{二進制} \\ \hline 0 & 000\\ 1 & 001\\ 2 & 010\\ 4 & 100\\ 7 & 111\\ 6 & 110 \end{array}$$

逐位轉換：

$2_8=010_2$

$0_8=000_2$

$4_8=100_2$

$7_8=111_2$

小數部分：

$1_8=001_2$

$6_8=110_2$

因此：

核心觀念

本題考查三個區域網路基本概念：

1. Ethernet LAN 的常見傳輸速率。
2. 共用傳輸媒介中，主機如何競爭資料傳輸權。
3. 網路管理員如何集中配置大量電腦的網路參數。

本題為申論式問答題，沒有選項，因此不適用逐一選項分析。

---

(一) Ethernet LANs 的三種傳輸速率

解題方法

題目已給出 Ethernet 的早期標準速率 $10$ Mbps，要求再列出三種常見的後續傳輸速率。依基本 Ethernet 分類，傳輸速率依序提升為：

• Fast Ethernet：$100$ Mbps
• Gigabit Ethernet：$1$ Gbps
• 10-Gigabit Ethernet：$10$ Gbps

其中：

$$1\ \text{Gbps}=1000\ \text{Mbps}$$

因此，除 $10$ Mbps 外，應填寫：

$$100\ \text{Mbps},\quad 1\ \text{Gbps},\quad 10\ \text{Gbps}$$

解題技巧與常見陷阱

• 題目問的是「傳輸速率」，不是 Ethernet 的標準名稱。
• $1$ Gbps 必須理解為 $1000$ Mbps，不是 $100$ Mbps。
• 依命題當時一般計算機概論教材的基本 Ethernet 演進，答出 $100$ Mbps、$1$ Gbps、$10$ Gbps 即可。
• 不宜將傳輸媒介、網路拓撲或 IEEE 編號誤當成速率作答。

---

(二) 決定傳輸權利的兩種協定

核心觀念

在多部電腦共用同一傳輸媒介時，必須透過媒介存取控制協定（Media Access Control, MAC）決定哪一部電腦可以使用媒介傳送資料。

Ethernet 與無線區域網路常見的兩種媒介存取協定為：

1. CSMA/CD
2. CSMA/CA

解題方法

1. CSMA/CD

CSMA/CD 全名為 Carrier Sense Multiple Access with Collision Detection，中文為「具碰撞偵測的載波感測多重存取」。

其基本流程為：

1. 主機先感測傳輸媒介是否忙碌。
2. 媒介閒置時開始傳送。
3. 傳送過程中持續偵測是否發生碰撞。
4. 發生碰撞時停止傳送，等待隨機時間後再重傳。

CSMA/CD 主要用於傳統共用式、半雙工 Ethernet。

2. CSMA/CA

CSMA/CA 全名為 Carrier Sense Multiple Access with Collision Avoidance，中文為「具碰撞避免的載波感測多重存取」。

其基本流程為：

（一）AVL 樹中最小節點數

核心觀念

AVL 樹是一種高度平衡的二元搜尋樹，任何節點的左、右子樹高度差最多為 $1$。要求高度為 $h$ 時的最小節點數，必須使每個節點都盡量接近允許的最不平衡狀態。

以下採用常見定義：

• 空樹高度為 $-1$
• 只有根節點的樹高度為 $0$
• $N_h$ 表示高度為 $h$ 的 AVL 樹之最小節點數

解題方法

為使高度為 $h$ 的 AVL 樹節點數最少，根節點的兩棵子樹高度必須為 $h-1$ 與 $h-2$。因此：

$$N_h=1+N_{h-1}+N_{h-2}$$

其中 $1$ 是根節點。

初始條件為：

$$N_0=1,\qquad N_1=2$$

計算前幾項：

$$N_2=1+2+1=4$$ $$N_3=1+4+2=7$$ $$N_4=1+7+4=12$$

令 Fibonacci 數列滿足：

$$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}$$

可得：

$$N_h=F_{h+3}-1$$

使用 Binet 公式：

$$F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}$$

其中：

$$\phi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}$$

所以高度為 $h$ 的 AVL 樹中，最小節點數的精確表示式為：

$$\boxed{ N_h=\frac{\phi^{h+3}-\psi^{h+3}}{\sqrt{5}}-1 }$$

解題技巧與陷阱

• 題目若以「邊數」定義高度，答案為 $F_{h+3}-1$。
• 若題目以「層數」定義高度，且單一根節點高度為 $1$，則答案會寫成：

$$N_h=F_{h+2}-1$$

• 關鍵不是直接套公式，而是先寫出遞迴式：

$$N_h=1+N_{h-1}+N_{h-2}$$

---

（二）依序插入二進位堆積

核心觀念

二進位堆積必須同時符合：

1. 完整二元樹形狀：新節點依序由上到下、由左到右加入。
2. 堆積順序：父節點必須符合堆積的大小關係。

題目未明確說明是最大堆積或最小堆積。以下依一般考試與資料結構題的常見設定，採用「最大堆積（max heap）」解答，即：

$$\text{父節點}\geq \text{子節點}$$

每次插入後，將新節點與父節點比較；若新節點較大，便向上調整。

逐次插入結果

以下以陣列表示堆積，陣列採 $1$ 起始索引：

插入值	插入並向上調整後的最大堆積
$10$	$[10]$
$12$	$[12,10]$
$1$	$[12,10,1]$
$14$	$[14,12,1,10]$
$6$	$[14,12,1,10,6]$
$5$	$[14,12,5,10,6,1]$
$8$	$[14,12,8,10,6,1,5]$
$15$	$[15,14,8,12,6,1,5,10]$
$3$	$[15,14,8,12,6,1,5,10,3]$
$9$	$[15,14,8,12,9,1,5,10,3,6]$
$7$	$[15,14,8,12,9,1,5,10,3,6,7]$
$4$	$[15,14,8,12,9,4,5,10,3,6,7,1]$
$11$	$[15,14,11,12,9,8,5,10,3,6,7,1,4]$
$13$	$[15,14,13,12,9,8,11,10,3,6,7,1,4,5]$
$2$	$[15,14,13,12,9,8,11,10,3,6,7,1,4,5,2]$

例如插入 $15$ 時：

$$[14,12,8,10,6,1,5,15]$$

先與父節點 $10$ 交換：

$$[14,12,8,15,6,1,5,10]$$

再與父節點 $12$ 交換：

$$[14,15,8,12,6,1,5,10]$$

最後與根節點 $14$ 交換：

$$[15,14,8,12,6,1,5,10]$$

最後的堆積圖

由最終陣列：

$$[15,14,13,12,9,8,11,10,3,6,7,1,4,5,2]$$

可畫成：

第四題詳解

（一）遞迴函數輸出結果

核心觀念

本題考查：

• 遞迴函數的呼叫順序
• 遞迴終止條件
• 函數呼叫後的返回順序
• 前序處理與後序處理的差異

函數如下：

def F(y):
 print(y)
 if (y < 2):
 F(y + 1)
 else:
 print(y)
 print(y)

每次呼叫 F(y) 時，執行順序為：

1. 先執行第一次 print(y)
2. 判斷 y < 2
3. 若成立，遞迴呼叫 F(y + 1)
4. 遞迴函數返回後，執行最後一次 print(y)

解題方法

初始執行 F(0)。

函數呼叫	第一次輸出	執行內容	最後輸出
F(0)	0	呼叫 F(1)	0
F(1)	1	呼叫 F(2)	1
F(2)	2	執行 else 中的 print(2)	2

在 F(2) 中：

• 進入函數時輸出一次 $2$
• 因為 $2 < 2$ 不成立，執行 else，再輸出一次 $2$
• 函數最後的 print(y) 再輸出一次 $2$

因此 F(2) 共輸出：

$$2,\ 2,\ 2$$

F(2) 返回後，回到 F(1)，執行最後的 print(1)；再回到 F(0)，執行最後的 print(0)。

解題技巧

遞迴題應將輸出分成兩類：

• 遞迴呼叫前的輸出：由 $0 \to 1 \to 2$，依序產生
• 遞迴呼叫返回後的輸出：由 $2 \to 1 \to 0$，依序產生

其中終止層 F(2)因為同時執行進入時的輸出、else 中的輸出，以及函數末端的輸出，所以 $2$ 會連續出現三次。

【答案】

輸出結果為：

0
1
2
2
2
1
0

---

（二）C++ 函數輸出結果

核心觀念

本題考查：

• for 迴圈執行流程
• 奇偶數判斷：j % 2 == 0
• 變數更新順序
• unsigned long long int 整數運算
• 費氏數列的遞迴關係

函數初始值為：

$$x=0,\qquad y=1$$

迴圈中：

• 當 $j$ 為偶數時：$x \leftarrow x+y$
• 當 $j$ 為奇數時：$y \leftarrow y+x$

最後：

第五題詳解

（一）利用公開金鑰技術確認寄件者身分

核心觀念

本小題考的是公開金鑰密碼系統中的：

• 數位簽章（Digital Signature）
• 私密金鑰與公開金鑰的用途
• 身分認證與資料完整性

公開金鑰系統中，每個人擁有一對金鑰：

• 公開金鑰：可以公開給他人，用來驗證數位簽章或加密資料。
• 私密金鑰：只能由本人保管，用來產生數位簽章或解密資料。

若要讓 M 男生確認情書確實由 C 女生所傳送，關鍵在於必須使用 C 女生的私密金鑰產生數位簽章。

解題方法

C 女生傳送情書時，處理流程如下：

1. C 女生先對情書內容計算雜湊值：

$h=H(\text{情書內容})$

2. C 女生使用自己的私密金鑰對雜湊值進行簽章，產生數位簽章：

$S=\operatorname{Sign}_{K_{C,\text{private}}}(h)$

3. C 女生將「情書內容」與「數位簽章」一併傳送給 M 男生。

4. M 男生取得 C 女生的公開金鑰，對數位簽章進行驗證，並重新計算情書內容的雜湊值。

5. 若驗證結果相同，表示：

• 數位簽章是由 C 女生的私密金鑰產生；
• 情書內容在傳送途中未遭到竄改；
• 因此可確認情書確實由持有 C 女生私密金鑰的人所傳送。

常見陷阱

• 不能使用 M 男生的公開金鑰來證明寄件者是 C 女生。 M 的公開金鑰主要用於讓他人加密資料，只有 M 的私密金鑰能解密。

• 單純使用 C 女生的公開金鑰加密情書，不是數位簽章的正確表達。 考試作答應使用「C 的私密金鑰簽章，M 使用 C 的公開金鑰驗證」的標準術語。

• 數位簽章主要提供：

• 身分認證

• 資料完整性

• 不可否認性