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

核心觀念

本題評量資料結構中「運算式樹（Expression Tree）與後序式求值」以及「二元樹走訪（Binary Tree Traversal）之樹形還原」兩大核心主題：

1. 算術運算式與後序拜訪（Postorder Traversal / Postfix Expression）：

• 運算式樹（Expression Tree）的內部節點（Internal Node）皆為運算子（Operator），外部節點／葉節點（Leaf Node）皆為運算元（Operand）。
• 對二元運算式樹進行後序拜訪（左子樹 $\to$ 右子樹 $\to$ 根節點），所得即為後序式（Postfix Expression，又稱逆波蘭表示法 Reverse Polish Notation, RPN）。
• 後序式的求值本質上依賴堆疊（Stack）：由左至右逐一讀取符號，遇運算元則推入（Push）堆疊；遇雙元運算子則依序彈出（Pop）兩個運算元，先彈出者為「右運算元」、後彈出者為「左運算元」，進行計算後再將結果推回堆疊。

2. 二元樹後序走訪與結構決定性：

• 後序走訪順序為「左子樹 $\to$ 右子樹 $\to$ 樹根」。因此，任一子樹走訪序列的最後一個節點必定是該子樹的根節點（Root）。
• 僅憑單一走訪序列（無中序走訪輔助）無法唯一決定二元樹。3 個節點所能構成相異二元樹的總數符合卡特蘭數（Catalan Number）： $C_3 = \frac{1}{3+1}\binom{2 \times 3}{3} = \frac{1}{4} \times 20 = 5$
• 只要分配節點使後序走訪維持 $C \to B \to A$，即可枚舉出所有合法的二元樹形態。

解題方法

(一) 後序式數值計算推導

後序運算式為： $A\ B\ C\ /\ D\ -\ E\ \ast\ +\ F\ G\ /\ -$ 代入數值：$A=5, B=6, C=2, D=3, E=2, F=9, G=3$，運算式轉化為： $5\quad 6\quad 2\quad /\quad 3\quad -\quad 2\quad \ast\quad +\quad 9\quad 3\quad /\quad -$

使用堆疊（Stack）進行模擬追蹤（由左至右讀取）：

最後留在堆疊頂端的數值即為計算結果，值為 $2$。

(二) 後序走訪為 $C, B, A$ 之所有二元樹推導

後序拜訪的走訪定義為：「左子樹 $\to$ 右子樹 $\to$ 根節點」。 已知後序走訪輸出依序為 $C, B, A$：

1. 確定根節點：最後輸出的節點必為整棵樹的根節點，故根節點為 $A$。
2. 分配其餘節點（$B, C$）：

• 根據後序走訪規則，左子樹所有節點必在右子樹所有節點之前輸出。

核心觀念

1. 遞迴函式（Recursive Function）：函式在執行過程中直接或間接呼叫自身。遞迴通常包含兩個關鍵要素：

• 終止條件（Base Case）：結束遞迴呼叫的條件，避免無窮遞迴（本題為 $q = 0$ 時返回 $1$）。
• 遞迴關係（Recursive Step）：將大問題化簡為結構相同但規模較小的子問題（本題為 $p \times f(p, q-1)$）。

2. 次方／冪次運算（Exponentiation）：利用數學遞迴定義： $p^q = \begin{cases} 1, & \text{當 } q = 0 \\ p \times p^{q-1}, & \text{當 } q > 0 \end{cases}$

解題方法

1. 分析函式功用： 觀察函式 int f(int p, int q)：

• 當 $q \neq 0$ 時，回傳值為 $p \times f(p, q-1)$。
• 當 $q = 0$ 時，回傳值為 $1$。
• 由數學歸納法可知： $f(p, q) = p \times f(p, q-1) = p \times p \times f(p, q-2) = \dots = p^q \times f(p, 0) = p^q \times 1 = p^q$
• 因此，此程式的功用為：計算並印出整數 $a$ 的 $n$ 次方（即 $a^n$）。

2. 追蹤執行結果（Trace）：

• 題目給定輸入整數依序為 $2$ 及 $8$，即變數 $a = 2$、$n = 8$。
• 呼叫 c = f(2, 8)，展開遞迴呼叫過程： $f(2, 8) = 2 \times f(2, 7)$ $f(2, 7) = 2 \times f(2, 6)$ $\vdots$ $f(2, 1) = 2 \times f(2, 0)$ $f(2, 0) = 1$
• 回溯計算： $c = 2^8 = 256$
• 主程式印出敘述為 printf("c = %d", c);（字串格式中無換行字元 \n）。
• 螢幕最終輸出為：c = 256。

解題技巧

• 輸出格式細節：作答時須注意 printf 格式字串是 "c = %d"，不可只寫數字 256，應完整寫出前綴 c = 。
• 輸入格式注意：scanf("%d,%d", &a, &n); 格式字串中有逗號，實務執行時輸入的兩數間必須鍵入逗號；題目已給定依序輸入 $2$ 與 $8$，直接代入計算即可。

(二)

核心觀念

1. 位元補數運算子（Bitwise NOT, ~）：將變數的每個二進位位元進行反向（$0$ 變 $1$，$1$ 變 $0$）。
2. 位元左移運算子（Bitwise Left Shift, <<）：將二進位位元向左平移指定的位元數，右側空出位元補 $0$。在未發生溢位的情況下，向左平移 $k$ 位相當於數值乘以 $2^k$。
3. 整數提升（Integer Promotion）與遮罩（Masking）：在 C 語言中，char 參與算術或位元運算時會自動提升為 int 型別。

核心觀念

1. 分頁記憶體管理（Paging Memory Management）：

• 作業系統將實體記憶體分割成固定大小的區塊，稱為頁框（Page Frame）；邏輯記憶體則分割成相同大小的區塊，稱為分頁（Page）。
• 分頁大小公式： $\text{分頁大小} = \frac{\text{可用記憶體總容量}}{\text{分頁總數}}$
• 分頁配置原則：記憶體配置必須以「整頁」為最小配置單位。若程式大小無法被分頁大小整除，不足一頁的部分仍必須配置完整的一頁，此時會產生內部碎裂（Internal Fragmentation）。因此，程式所需分頁數應採用無條件進位（天花板函數，Ceiling Function）： $\text{所需分頁數} = \left\lceil \frac{\text{程式所需容量}}{\text{分頁大小}} \right\rceil$

2. 十進位轉二進位（Radix Conversion）：

• 整數部分：採用連除法（除以 2 取餘數）。將十進位整數連續除以 2，記錄每次的餘數，直到商數為 0，最後將餘數「由下往上」（由最低有效位 LSB 排至最高有效位 MSB）反向讀取。
• 小數部分：採用連乘法（乘以 2 取整數）。將十進位小數連續乘以 2，取出乘積的整數部分，再將剩餘的小數部分繼續乘以 2，重複此步驟直到小數部分為 0 或達到所需精確度，最後將整數「由上往下」依序順向讀取。

解題方法

(一) 分頁需求量與未被使用分頁數計算

1. 計算單一分頁大小： $\text{分頁大小} = \frac{60\text{ MB}}{15} = 4\text{ MB}$

2. 計算程式 A 所需分頁數： 程式 A 大小為 $21\text{ MB}$： $\text{程式 A 分頁數} = \left\lceil \frac{21\text{ MB}}{4\text{ MB}} \right\rceil = \lceil 5.25 \rceil = 6\text{ 個分頁}$ (配置 $6 \times 4\text{ MB} = 24\text{ MB}$，其中內部碎裂為 $24 - 21 = 3\text{ MB}$)

3. 計算程式 B 所需分頁數： 程式 B 大小為 $27\text{ MB}$： $\text{程式 B 分頁數} = \left\lceil \frac{27\text{ MB}}{4\text{ MB}} \right\rceil = \lceil 6.75 \rceil = 7\text{ 個分頁}$ (配置 $7 \times 4\text{ MB} = 28\text{ MB}$，其中內部碎裂為 $28 - 27 = 1\text{ MB}$)

核心觀念

本題涵蓋「資訊安全」與「網路傳輸計量」兩大計算機概論核心主題：

1. 惡意程式與威脅防禦：

• 間諜軟體（Spyware）：未經使用者知情或授權，秘密安裝於主機並監控、竊取使用者隱私與機敏資料的惡意程式。
• 釣魚軟體／網路釣魚（Phishing）：運用社交工程（Social Engineering）手法，偽裝成合法、可信任的實體（如金融機構、入口網站），誘騙使用者交出憑證或個資；「釣魚軟體」則指用以展示偽冒介面、竊取憑證或傳遞釣魚訊息的惡意程式與釣魚工具包（Phishing Kit）。
• 縱深防禦（Defense-in-Depth）：針對釣魚攻擊，防護手段應涵蓋端點安全軟體、網路與瀏覽器過濾、多因素驗證機制及使用者安全意識。

2. 網路傳輸速率計算：

• 資料量單位換算：$1\text{ Byte (B)} = 8\text{ bits (b)}$。
• 傳輸速率公式： $\text{傳輸速率 (Transmission Rate)} = \frac{\text{傳輸資料量 (bits)}}{\text{傳輸時間 (seconds)}}$
• 常見單位標準：儲存容量與網路速率常涉及二進制（$1\mathrm{K} = 1024$）與十進制（$1\mathrm{K} = 1000$）的慣用定義。

解題方法

(一) 間諜軟體與釣魚軟體之說明及電腦防衛作法

1. 間諜軟體（Spyware）

• 定義：在使用者未同意或不知情的情況下，秘密植入系統並在背景持續運行的惡意軟體。
• 行為特徵：記錄鍵盤輸入（Keylogger）、側錄螢幕畫面、蒐集瀏覽紀錄、竊取帳號密碼與信用卡等機敏隱私資料，並透過背景網路通道傳送給攻擊者，常伴隨系統資源耗損或設定被竄改（如瀏覽器首頁被綁架）。

2. 釣魚軟體（Phishing）

• 定義：利用偽裝技術進行社交工程詐欺的威脅手段。狹義指用於釣魚攻擊的惡意應用程式（如偽冒的行動網銀 App、彈出式假登入視窗軟體）；廣義泛指配合釣魚信件或假網站，用以誘騙使用者輸入憑證之惡意載具。
• 行為特徵：高仿真仿冒合法網站或應用程式介面，誘騙使用者主動提供帳號、密碼、一次性驗證碼（OTP）或個人機敏資料。

3. 電腦防衛釣魚軟體的具體對策

• 部署終端防護與反釣魚工具：安裝防毒／EDR 軟體，並啟用瀏覽器內建的反釣魚防護技術（如 Google Safe Browsing、Microsoft SmartScreen），即時阻擋已知惡意網址與仿冒頁面。
• 啟用多因素驗證（MFA / 2FA）：對重要帳號全面啟用基於 FIDO2 / WebAuthn 或 Authenticator App 的雙因子驗證；即使密碼遭釣魚軟體竊取，攻擊者仍無法突破登入防線。
• 落實系統與軟體修補（Patching）：定期更新作業系統、瀏覽器及其擴充外掛，修補安全漏洞，防止釣魚連結觸發驅動式下載（Drive-by Download）。
• 郵件過濾與連結檢查機制：配置郵件伺服器的 SPF、DKIM、DMARC 認證技術，並教育使用者於點擊連結前務必仔細檢視網址（URL）之網域名稱與 TLS 憑證真偽，切勿點擊來源不明的附件與超連結。

(二) 手機網路傳輸速率計算

• 已知條件：

• 檔案大小 $S = 800\mathrm{KB}$
• 傳輸時間 $t = 20\text{ 秒}$
• 目標單位：$\mathrm{Kbps}$（Kilobits per second）

• 推導步驟：

步驟 1：位元轉換（Byte 至 bit） $1\text{ Byte} = 8\text{ bits} \implies 800\mathrm{KB} = 800 \times 8\mathrm{Kb} = 6400\mathrm{Kb}$

步驟 2：計算傳輸速率 依據傳輸速率公式：