111 高普考高考三級 電力工程 計算機概論 考古題詳解

核心觀念

十進位實數轉換為二進位時，必須將「整數部分」與「小數部分」分開處理：

1. 整數部分：採用連除法（除以 2 取餘數），由下而上（由最後一個商數至第一個餘數）排列，作為二進位整數的高位元至低位元。
2. 小數部分：採用連乘法（乘以 2 取整數），由上而下依序取出每次相乘後產生的整數部分，直至小數部分為 0 或達到指定精度。

解題方法

1. 整數部分 $(14)_{10}$ 轉二進位： $14 \div 2 = 7 \cdots\cdots \text{餘 } 0 \quad (\text{最低位元 LSB})$ $7 \div 2 = 3 \cdots\cdots \text{餘 } 1$ $3 \div 2 = 1 \cdots\cdots \text{餘 } 1$ $1 \div 2 = 0 \cdots\cdots \text{餘 } 1 \quad (\text{最高位元 MSB})$ 由下往上讀取，得到 $(14)_{10} = (1110)_2$。

2. 小數部分 $(0.625)_{10}$ 轉二進位： $0.625 \times 2 = 1.25 \cdots\cdots \text{取出整數 } 1$ $0.25 \times 2 = 0.5 \cdots\cdots \text{取出整數 } 0$ $0.5 \times 2 = 1.0 \cdots\cdots \text{取出整數 } 1$ 由上往下讀取，得到 $(0.625)_{10} = (0.101)_2$。

3. 合併整數與小數部分： $(14.625)_{10} = (1110.101)_2$

解題技巧

• 快速權重展開法（逆算驗算）： $1110.101_2 = 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 + 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3}$ $= 8 + 4 + 2 + 0.5 + 0.125 = 14.625$ 小數點後第一、二、三位的權重分別固定為 $0.5$、$0.25$、$0.125$。觀察 $0.625 = 0.5 + 0.125 = 2^{-1} + 2^{-3}$，即可心算得出小數部分為 $.101$。

【答案】 $(1110.101)_2$

(二) 十進位負整數 $-179$ 轉成 16-bit 二補數（2's complement）

核心觀念

二補數（2's Complement）為現代計算機最常用的有號數表示法。求負數之二補數步驟如下：

1. 先求該數之絕對值（正整數）的二進位表示。
2. 將其擴展至指定位元長度（本題為 16-bit，前方補 0）。
3. 取該二進位字串的二補數：即「一補數加 1」（位元反轉後加 1），或「自最低位（右端）往高位（左端）掃描，遇見第一個 1 之前與該 1 本身保持不變，其餘高位元全數反轉」。

解題方法

1. 求 $+179$ 之二進位表示： $179 = 128 + 32 + 16 + 2 + 1 = 2^7 + 2^5 + 2^4 + 2^1 + 2^0$ 因此 $(179)_{10} = (10110011)_2$。

2. 擴展為 16-bit 正整數： $(+179)_{10} = (0000\ 0000\ 1011\ 0011)_2$

3. 轉換為二補數：

• 步驟 A（求一補數，即各 bit 0 與 1 互換）： $1111\ 1111\ 0100\ 1100$
• 步驟 B（加 1 得到二補數）：

核心觀念

本題評量經典的「兩數之和」（Two-Sum Problem），為資料結構與演算法的核心題型。其主要測驗重點包括：

1. 陣列（Array）與搜尋演算法：如何在大小為 $k$ 的整數陣列中，有效率地檢索出滿足條件 $N_i + N_j = SUM$（其中 $i \neq j$）的數對。
2. 演算法時間與空間複雜度（Time and Space Complexity）：

• 暴力搜尋法（Brute Force）：雙層迴圈尋找每一對組合，時間複雜度為 $O(k^2)$，空間複雜度為 $O(1)$。
• 排序配合雙指標法（Sorting with Two Pointers）：先進行排序（如快速排序或合併排序），再利用雙端向內夾擠，時間複雜度為 $O(k \log k)$，空間複雜度為 $O(1)$ 或 $O(k)$。
• 雜湊表法（Hash Table / Hash Set）：以空間換取時間，單次走訪查詢餘額，時間複雜度為 $O(k)$，空間複雜度為 $O(k)$。

解題方法

在國家考試中，手寫演算法以「排序配合雙指標法（Two-Pointer Method）」最為嚴謹且具代表性，能在不依賴外部進階資料結構庫（如 Hash Table 碰撞處理）的前提下，達到 $O(k \log k)$ 的時間複雜度與 $O(1)$ 的輔助空間複雜度。

演算法邏輯步驟

1. 輸入與前處理：

• 輸入包含 $k$ 個整數的陣列 $N$ 與目標值 $SUM$。
• 若 $k < 2$，直接印出「抱歉，找不到」並結束。
• 將陣列 $N$ 由小到大遞增排序（Ascending Sort），排序後設陣列索引為 $1$ 至 $k$。

2. 雙指標初始化：

• 設定左指標 $left = 1$（指向最小值）。
• 設定右指標 $right = k$（指向最大值）。
• 設定旗標變數 $found = \text{false}$。

3. 雙向夾擠檢索：

• 當 $left < right$ 時，計算當前和： $current\_sum = N[left] + N[right]$
• 判斷情況：
• 若 $current\_sum = SUM$：印出 $(N[left], N[right])$，將 $found$ 設為 $\text{true}$，並中斷迴圈結束演算法。
• 若 $current\_sum < SUM$：表示總和不足，將左指標右移（$left \leftarrow left + 1$），以增加數值。
• 若 $current\_sum > SUM$：表示總和過大，將右指標左移（$right \leftarrow right - 1$），以減少數值。

4. 輸出判斷：

• 若迴圈終止時 $found$ 仍為 $\text{false}$，則印出「抱歉，找不到」。

選項分析

本題為非選擇題（演算法設計申論題），無選項可作分析。針對本題三種常見解法之優缺點進行比較分析：

1. 暴力搜尋法（Brute Force）：

• 作法：使用兩層巢狀迴圈檢查所有 $\frac{k(k-1)}{2}$ 種數對組合。
• 分析：邏輯最簡單，但不具備演算法效率優化，時間複雜度達 $O(k^2)$。若資料量 $k$ 龐大時效能極差，於高普考評分標準中難以取得滿分。

2. 排序配合雙指標法（Two Pointers）（本解法採用）：

• 作法：先對陣列進行最佳化排序（如快速排序或堆積排序，耗時 $O(k \log k)$），再以雙指標由兩端線性掃描（耗時 $O(k)$）。

核心觀念

本題考查四種 CPU 排程演算法的執行順序與甘特圖表示：

• FCFS（先到先服務）：依進入系統的先後順序執行。
• SJF（短工作優先）：每次選擇 CPU 執行時間最短的行程；本題未標示搶先，因此採非搶先方式。
• Nonpreemptive priority（非搶先優先權）：選擇優先權最高的行程執行至完成。本題數字越小，優先權越高。
• RR（Round Robin，循環輪替）：每個行程最多執行一個時間片；時間片用完仍未完成，就排到就緒佇列尾端。本題時間片 $q=1$。

所有行程都在時間 $0$ 到達。當行程的 burst time 或優先權相同時，依題目給定的進入順序 $P_1、P_2、P_3、P_4、P_5$ 排定先後。

解題方法與甘特圖

每種演算法都依其規則決定執行順序，再將各行程的 burst time 累加，標出每段工作的起訖時間。

一、FCFS

依到達順序執行：$P_1、P_2、P_3、P_4、P_5$。

時間刻度：$0、10、11、13、14、19$。

二、SJF

依 burst time 由短至長排列。$P_2$ 與 $P_4$ 的 burst time 都是 $1$，依到達順序先執行 $P_2$；其後依序為 $P_4、P_3、P_5、P_1$。

時間刻度：$0、1、2、4、9、19$。

三、Nonpreemptive priority

優先權數字越小，優先權越高。依優先權由高至低為 $P_2、P_5、P_1、P_3、P_4$。$P_1$ 與 $P_3$ 的優先權同為 $3$，依到達順序先執行 $P_1$。

核心觀念

本題的核心觀念為分散式系統與電腦網路通訊中的經典理論——兩軍問題（Two Generals' Problem），以及不可靠傳輸媒介上的共識問題（Consensus Problem）與三向交握（Three-Way Handshake）原理。

1. 不可靠通訊通道（Unreliable Channel）： 在傳統郵件或無連接網路中，通訊鏈路具備「封包遺失（Packet Loss）」與「傳輸延遲（Transmission Delay）」的不確定性。
2. 共同知識（Common Knowledge）與共識極限： 電腦科學已嚴格證明：在不可靠的通訊環境中，任何有限次數（Finite Steps）的訊息交換，都無法達成 $100\%$ 確定性的共識。 最後一個發送確認訊息的一方，永遠無法得知該確認訊息是否成功送達對方手中，進而引發「無限確認遞迴（Infinite Acknowledgment Loop）」。

解題方法

將題目中的「傳統寄信」映射為計算機網路的「不可靠傳輸協定」，「赴約」映射為「分散式節點的狀態提交（State Commit / Agreement）」。

解題切入點為邊界狀態分析法（Worst-Case Analysis）：題目問的是「一定會」或「能確定」（即 $100\%$ 的確定性保證）。因此，只要能推導出任何一種因通訊失敗（遺失或延遲）而導致雙方認知脫節的情境，即可判定「無法確定」或「不會一定去」。

各小題詳細解析

(一) 志銘按照定的時間地點準時赴約，春嬌一定會去嗎？

• 分析： 此情況等同於網路中的「單向傳輸（One-Way Transmission）」，志銘發送請求後即單方面執行動作。 由於傳統寄信屬於不可靠傳輸，可能面臨以下兩種不可抗力因素：

1. 信件遺失：春嬌自始至終皆未收到信件。
2. 信件延遲過久：信件在約會時間過後才送達。

在上述兩種情況下，春嬌完全不知悉約會時間與地點。雖然春嬌具備「有邀約一定欣然赴約」的前提，但因未接收到有效訊息，根本不可能出現在約定地點。

• 結論：春嬌不會一定去（即不一定會去）。

(二) 春嬌回確認信後，按約定時間到達時，能確定志銘一定會在那邊嗎？

• 分析： 此情況等同於「雙向交握（Two-Way Handshake）」，即志銘發送請求（SYN），春嬌發送確認（ACK）。 春嬌雖然成功寄出確認信，但春嬌所處的狀態面臨資訊不對稱：

1. 春嬌的確認信同樣可能在郵寄過程中遺失或延遲送達。
2. 春嬌寄出確認信後，無法得知志銘是否確實收到該回信。
3. 若志銘未收到春嬌的確認信，志銘可能認為「春嬌未收到原始邀請」或「春嬌不打算赴約」，進而取消赴約行程。

因此，春嬌到達現場時，無法排除志銘因未收到確認信而缺席的可能性。

• 結論：春嬌不能確定志銘一定會在那邊。

(三) 志銘收到確認信後再回信「讚，我一定會去的」，兩個人都會確定對方一定會準時到現場赴約嗎？

核心觀念

本題考多表置換密碼的解密。依題目規則，英文字母以 $A=0,\ B=1,\ldots,Z=25$ 編碼，並使用公式：

$P_i=(C_i-K_i)\bmod 26$

若相減結果為負數，加上 $26$ 後再換回字母。

解題方法

將密文逐字轉成數值，依序減去對應的密鑰值，再對 $26$ 取餘數：