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

核心觀念

本題考銀行家演算法的安全性判定。每個程序的尚需資源量為：

若某程序的 Need 每一項都不大於目前可用資源，就能假設該程序完成，並將它已分配的資源歸還。若所有程序都能依序完成，這個順序就是安全序列，系統處於安全狀態。

解題方法

先計算各程序的尚需資源量：

可用資源為 $(0,0,x,1,2)$。一開始 $A=B=0$，因此 $P_0$、$P_2$ 都因需要 $A=1$ 而無法執行，$P_1$ 因需要 $B=2$ 而無法執行。$P_3$ 要求 $C=2$、$D=1$、$E=1$，所以必須有 $x\ge 2$ 才能先完成。

核心觀念

本題旨在測驗 IPv4 分類定址法（Classful Addressing）與子網路劃分（Subnetting）的運算能力，核心概念如下：

1. IPv4 類別預設遮罩：

• 類別 B（Class B）位址之首碼範圍為 $128.0.0.0 \sim 191.255.255.255$。
• 預設網路 ID 為前 16 位元，主機 ID 為後 16 位元，預設子網路遮罩為 255.255.0.0（以 CIDR 表示為 /16）。

2. 借位原則（Subnet Borrowing）：

• 子網路切割是透過向「主機位元（Host Bits）」借用 $n$ 個位元充當「子網路位元（Subnet Bits）」。
• 可劃分的子網路數量公式：
• 現行標準（RFC 1878 / CIDR，支援 Subnet Zero 與 All-Ones Subnet）：可劃分子網路數為 $2^n$。
• 早期標準（RFC 950，扣除全 0 與全 1 子網）：可劃分子網路數為 $2^n - 2$。

3. 子網路遮罩合成：

• 將所有網路位元與借用的子網路位元皆設為二進位 1，其餘主機位元設為二進位 0，再轉換為十進位點分標記法（Dotted-Decimal Notation）。

解題方法

步驟一：確認原始類別與位元配置

題目給定之 IP 位址為 $140.123.0.0$，其第一個八位元組數值為 $140$（落在 $128 \sim 191$ 區間），屬於標準 Class B 位址。

• 網路位元數：16 位元。
• 主機位元數：16 位元。
• 預設子網路遮罩：255.255.0.0。

步驟二：計算需借用的子網路位元數 $n$

題目要求將網路切割成至少 10 個子網路，且全部都要能連上電腦網路：

• 若依現行網際網路標準（RFC 1878 / CIDR）： $2^n \ge 10$ 當 $n = 3$ 時，$2^3 = 8 < 10$（不足以提供 10 個子網）。 當 $n = 4$ 時，$2^4 = 16 \ge 10$（滿足需求）。
• 若依傳統 RFC 950 標準（排除全 0 與全 1 之子網）： $2^n - 2 \ge 10 \implies 2^n \ge 12$ 同樣可得 $n \ge 4$。
• 因此，無論依循何種規範，皆必須向主機位元借用 4 個位元（$n = 4$）。

步驟三：計算並推導子網路遮罩

向第三個八位元組借用高位的 4 個位元後，新的網路遮罩總長度為： $16 + 4 = 20 \text{ 位元（即 /20）}$

核心觀念

最大堆積是一種完整二元樹，每個父節點的值都大於或等於子節點。插入新值時，先把它放在堆積最後一個位置，再與父節點比較；若新值較大，就向上交換，直到符合最大堆積性質。

含有 $n$ 個節點的完整二元樹高度為 $O(\log n)$，因此單次插入最多向上調整 $O(\log n)$ 層。

解題方法

依圖中的層序排列，原始最大堆積為 $[10,8,3,5,2,1]$。逐一插入題目數列，並在每次插入後向上調整：

1. 插入 $12$：先放在 $3$ 的下一個位置，接著依序與 $3$、$10$ 交換，得到 $[12,8,10,5,2,1,3]$。
2. 插入 $15$：先放在 $5$ 的下一個位置，接著依序與 $5$、$8$、$12$ 交換，得到 $[15,12,10,8,2,1,3,5]$。
3. 插入 $13$：先放在 $8$ 的下一個位置，再與 $8$、$12$ 交換，得到 $[15,13,10,12,2,1,3,5,8]$。

核心觀念

1. 氣泡排序法（Bubble Sort）原理： 氣泡排序法屬於交換排序（Exchange Sort）。在由小至大的排序過程中，演算法依序比較相鄰的兩個元素，若前項大於後項（即 $array[j] > array[j+1]$），則將兩者互換（Swap）。每一回合（Pass）會將目前未排序區間中的最大值，如氣泡般逐步「浮」至該區間的最右端定位。
2. 交換次數與逆序對（Inversion）的等價性： 在相鄰元素比較的排序法（如標準氣泡排序法）中，每一次相鄰元素的互換操作，恰好能且僅能消除原始序列中的一個逆序對（若 $i < j$ 且 $array[i] > array[j]$，則稱 $(array[i], array[j])$ 為一個逆序對）。因此，無論比對順序如何實作，氣泡排序法過程中的總交換次數恆等於初始陣列的逆序對總數。

解題方法

給定陣列初始狀態為： $array[7] = \{7, 12, 6, 4, 2, 77, 1\}$ 陣列長度 $n = 7$，元素索引為 $0 \sim 6$。以下依標準氣泡排序法（由左向右掃描、相鄰比較）逐步追蹤每一回合（Pass）的交換過程：

【第一回合（Pass 1）】（浮出未排序區間最大值至索引 6）

• 比較 $array[0]=7$ 與 $array[1]=12$：$7 \le 12$，不交換。
• 比較 $array[1]=12$ 與 $array[2]=6$：$12 > 6$，交換（第 1 次）$\rightarrow \{7, 6, 12, 4, 2, 77, 1\}$
• 比較 $array[2]=12$ 與 $array[3]=4$：$12 > 4$，交換（第 2 次）$\rightarrow \{7, 6, 4, 12, 2, 77, 1\}$
• 比較 $array[3]=12$ 與 $array[4]=2$：$12 > 2$，交換（第 3 次）$\rightarrow \{7, 6, 4, 2, 12, 77, 1\}$
• 比較 $array[4]=12$ 與 $array[5]=77$：$12 \le 77$，不交換。
• 比較 $array[5]=77$ 與 $array[6]=1$：$77 > 1$，交換（第 4 次）$\rightarrow \{7, 6, 4, 2, 12, 1, 77\}$
• 本回合結束狀態：$\{7, 6, 4, 2, 12, 1, 77\}$，最大值 $77$ 已就位。
• 本回合交換次數：$4$ 次。

【第二回合（Pass 2）】（浮出次大值至索引 5）

• 比較 $array[0]=7$ 與 $array[1]=6$：$7 > 6$，交換（第 5 次）$\rightarrow \{6, 7, 4, 2, 12, 1, 77\}$
• 比較 $array[1]=7$ 與 $array[2]=4$：$7 > 4$，交換（第 6 次）$\rightarrow \{6, 4, 7, 2, 12, 1, 77\}$
• 比較 $array[2]=7$ 與 $array[3]=2$：$7 > 2$，交換（第 7 次）$\rightarrow \{6, 4, 2, 7, 12, 1, 77\}$
• 比較 $array[3]=7$ 與 $array[4]=12$：$7 \le 12$，不交換。
• 比較 $array[4]=12$ 與 $array[5]=1$：$12 > 1$，交換（第 8 次）$\rightarrow \{6, 4, 2, 7, 1, 12, 77\}$
• 本回合結束狀態：$\{6, 4, 2, 7, 1, 12, 77\}$，數值 $12$ 已就位。
• 本回合交換次數：$4$ 次。

【第三回合（Pass 3）】（浮出第 3 大值至索引 4）

• 比較 $array[0]=6$ 與 $array[1]=4$：$6 > 4$，交換（第 9 次）$\rightarrow \{4, 6, 2, 7, 1, 12, 77\}$
• 比較 $array[1]=6$ 與 $array[2]=2$：$6 > 2$，交換（第 10 次）$\rightarrow \{4, 2, 6, 7, 1, 12, 77\}$

核心觀念

本題評量**RSA 非對稱式密碼系統（RSA Cryptosystem）之金鑰生成原理，涉及數論中的尤拉總計函數（Euler's Totient Function）與模反元素（Modular Multiplicative Inverse）**求解。

1. 模數（Modulus）： $n = p \times q$
2. 尤拉總計函數 $\phi(n)$： 當 $p$、$q$ 為質數時，小於且互質於 $n$ 的正整數個數為： $\phi(n) = (p - 1)(q - 1)$
3. 私鑰指數 $d$ 的定義： 公鑰指數 $e$ 與私鑰指數 $d$ 在模 $\phi(n)$ 下互為乘法反元素，滿足同餘方程式： $e \cdot d \equiv 1 \pmod{\phi(n)}$ 即存在整數 $k$，使得： $e \cdot d = k \cdot \phi(n) + 1$

解題方法

步驟一：計算模數 $n$ 與尤拉函數 $\phi(n)$

題目給定兩質數 $p = 3$、$q = 11$：

• 模數 $n$： $n = p \times q = 3 \times 11 = 33$
• 尤拉總計函數 $\phi(n)$： $\phi(n) = (p - 1)(q - 1) = (3 - 1)(11 - 1) = 2 \times 10 = 20$

步驟二：確認公鑰指數 $e$ 之合法性

題目給定公鑰 $e = 7$。 驗證 $\gcd(e, \phi(n)) = \gcd(7, 20) = 1$，兩者互質，符合 RSA 加密指數要求。

步驟三：求解私鑰指數 $d$（模反元素）

依據定義，私鑰 $d$ 必須滿足： $7d \equiv 1 \pmod{20}$ 此式等價於尋找整數 $k$，使得： $7d = 20k + 1 \implies d = \frac{20k + 1}{7}$

由最小非負整數 $k$ 開始代入檢驗：

• 當 $k = 0$ 時，$d = \frac{1}{7}$（非整數）
• 當 $k = 1$ 時，$d = \frac{20(1) + 1}{7} = \frac{21}{7} = 3$（整數解）

步驟四：給出 $d$ 值的可能範圍

在模算術體系中，同餘解具週期性，通解為： $d \equiv 3 \pmod{20} \implies d = 3 + 20k \quad (k \in \mathbb{Z})$