110 公務人員升官等薦任 電子工程 計算機概論 考古題詳解

核心觀念

本題考查 交互回授 NOR 閘組成的循序邏輯電路。循序電路的輸出會回授到其他閘的輸入，因此需列出各閘的布林方程式，再求穩定輸出。

圖中的小圓點代表反相；因此右側兩個閘都是 NOR 閘。左側兩個閘為 AND 閘。

解題方法

令下方 NOR 閘的輸出為 $y$。依照圖中的連線，可列出：

先計算兩個 AND 閘的輸出：

核心觀念

本題考查進位制轉換，以及負整數在固定位元長度下的二補數表示法。

• 二進位每 $3$ 個位元可對應一個八進位數字，因此十六進位可先轉成二進位，再由右向左每 $3$ 位分組。
• $n$ 位元二補數的表示範圍為 $-2^{n-1}$ 至 $2^{n-1}-1$。求負數表示時，可將其絕對值寫成固定長度二進位，再逐位反相並加 $1$。

解題方法

（一）將 $(86E)_{16}$ 轉換成八進位

先將每個十六進位數字轉成 $4$ 位元二進位：

由右向左每 $3$ 位分組：

各組轉成八進位數字：

因此：

（二）以 $8$ 個 bits 儲存十進位 $-35$

$8$ 位元二補數的表示範圍為 $-128$ 至 $127$，因此 $-35$ 可以表示。

核心觀念

本題考最大公因數（GCD）的求法，以及如何分別用遞迴函式與 for 迴圈實作。採用歐幾里得演算法：對正整數 $a,b$，若 $a \ge b > 0$，則

當餘數為 $0$ 時，最後一個非零除數就是最大公因數。此性質成立的原因是：$a$ 與 $b$ 的公因數，恰好也是 $b$ 與 $a\bmod b$ 的公因數。

解題方法

先將兩個輸入整理為 $a \ge b$。反覆以較大的數除以較小的數，並以「除數、餘數」取代原來的兩數；餘數成為 $0$ 時停止。遞迴版以函式呼叫表達反覆更新，迴圈版則以 for 迴圈執行相同更新。

例如 $x=48,\ y=18$：

最後一個非零餘數前的除數為 $6$，所以 $\gcd(48,18)=6$。

（一）遞迴函式

int gcd_recursive(int x, int y) {
 if (x < y) {
 return gcd_recursive(y, x);
 }

 if (y == 0) {
 return x;
 }

 return gcd_recursive(y, x % y);
}

若輸入均大於 $2$，程式仍會正確處理；函式也將「其中一數為 $0$」設為遞迴終止條件。當 $x<y$ 時先交換兩數，使後續計算符合歐幾里得演算法的形式；否則繼續呼叫 gcd_recursive(y, x % y)。

核心觀念

本題考查 IEEE 802.11 的 **CSMA/CA（載波感知多重存取／碰撞避免）**與 RTS/CTS 握手。隱藏終端問題是：X、Y 都能與 AP 通訊，但彼此無法偵測對方的訊號，因此 Y 可能在 X 傳送時也開始傳送，造成 AP 收到碰撞資料。

解題方法

IEEE 802.11 可使用 RTS/CTS 機制，在傳送較長資料前先保留無線媒介：

1. X 先向 AP 傳送 RTS（Request to Send，要求傳送）。
2. AP 收到 RTS 後，回覆 CTS（Clear to Send，允許傳送）。
3. CTS 會由 AP 傳送。圖中的 Y 雖然偵測不到 X，卻能收到 AP 的 CTS。

核心觀念

AVL tree 是符合二元搜尋樹排序規則，且每個節點左右子樹高度差不超過 $1$ 的二元樹。平衡因子定義為：

每個節點都必須滿足 $BF(v)\in\{-1,0,1\}$。插入或刪除節點後，若有節點的平衡因子超出範圍，就沿著失衡方向進行旋轉，恢復平衡。

原樹的結構為：

 40
 / \
 25 70
 \ / \
 35 55 80
 / \
 75 85

解題方法

（一）插入 key 值 90

依二元搜尋樹規則，$90$ 大於 $40、70、80、85$，因此插入為 $85$ 的右子節點：

 40
 / \
 25 70
 \ / \
 35 55 80
 / \
 75 85
 \
 90

插入後，節點 $70$ 的右子樹比左子樹高 $2$，有 $BF(70)=-2$。失衡發生在右子樹的右側，屬於 RR 型，因此對 $70$ 做一次左旋。旋轉後結果為：

 40
 / \
 25 80
 \ / \
 35 70 85
 / \ \
 55 75 90

共有 $9$ 個節點，且各節點都符合 AVL 平衡條件。

（二）刪除 key 值 40

核心觀念

本題考查三種常見的惡意程式或密碼破解方式。作答時要分清楚它們的感染或偽裝方式、主要行為，以及攻擊目標：

• 巨集病毒利用文件中的巨集程式碼散播或執行惡意行為。
• 特洛伊木馬偽裝成正常或有用的程式，誘使使用者執行。
• 字典攻擊以常見單字、慣用密碼或其變形，逐一嘗試登入密碼。

解題方法

本題是名詞解釋題，逐項說明「是什麼、如何運作、造成什麼風險」即可。辨別時可抓住關鍵字：巨集病毒看文件巨集；特洛伊木馬看偽裝與誘騙執行；字典攻擊看候選密碼逐一嘗試。

（一）巨集病毒（macro virus）

巨集病毒是以應用程式的巨集語言撰寫的惡意程式，常見於支援巨集的文書或試算表文件。當使用者開啟受感染文件，並允許或觸發巨集執行時，病毒即可執行其指令；部分巨集病毒也會感染範本或其他文件，使後續文件繼續帶有病毒。

其危害包括竄改或刪除文件內容、複製自身、散播到其他文件，或執行其他惡意操作。防範方式包括停用不必要的巨集、只允許可信來源的巨集，以及使用防毒軟體掃描文件。

（二）特洛伊木馬（Trojan horse）