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

核心觀念

**插入排序法（Insertion Sort）**將數列分成「已排序區」與「尚未排序區」，每次取尚未排序區的第一個數，插入已排序區的正確位置。此題由左至右處理，第一個數視為初始的已排序區。

**二元搜尋法（Binary Search）**適用於已排序數列。每次取搜尋範圍中間位置的值與目標比較，再依比較結果縮小至左半或右半範圍，直到找到目標。

本題以陣列位置 從 1 開始編號；二元搜尋每次令

其中 first、last 分別是目前搜尋範圍的首、末位置。

解題方法

（一）插入排序

原數列為 $21, 7, 56, 81, 73, 99, 11, 35$。第一個數 $21$ 作為初始已排序區，依序將後續各數插入合適位置：

核心觀念

本題考查快取記憶體的用途，以及記憶體位址數量與位址位元數的換算。

快取記憶體（Cache）是容量較小、速度較快的記憶體，設在 CPU 與主記憶體之間，用來暫存 CPU 近期或常用的資料與指令。其設計利用程式執行時的時間區域性（近期使用過的資料較可能再次使用）與空間區域性（某位置附近的資料較可能很快被使用），以降低 CPU 存取主記憶體的平均時間。

記憶體位址所需位元數取決於要區分多少個可定址單位。若每個字組為一個定址單位，且共有 $N$ 個字組，則位址位元數 $n$ 須滿足 $2^n \geq N$。

（一）CPU 使用快取記憶體的目的

CPU 的運算速度通常高於主記憶體的存取速度。若 CPU 每次需要資料都直接等待主記憶體，便會耗費較多時間。快取記憶體以較快的速度提供近期或常用的資料與指令，降低 CPU 等待主記憶體的時間，提升整體系統效能。

當 CPU 要讀取資料時，先查詢快取：

• 快取命中（hit）：所需資料已在快取中，可快速取得。
• 快取未命中（miss）：資料不在快取中，須向主記憶體取得，並通常將資料載入快取供後續使用。

因此，快取的目的不是增加主記憶體容量，而是縮短平均記憶體存取時間，減少 CPU 與主記憶體之間的速度落差。

（二）定址每一個字組所需位元數

核心觀念

二元樹的三種深度優先走訪順序為：

• 前序走訪（Preorder）：根、左子樹、右子樹。
• 中序走訪（Inorder）：左子樹、根、右子樹。
• 後序走訪（Postorder）：左子樹、右子樹、根。

因此，後序走訪序列的最後一個節點是根；前序走訪序列的第一個節點是根。若已知中序與前序序列，則可先由前序找根，再利用中序序列中根的位置，切分左右子樹並逐層重建。

解題方法

（一）由後序走訪找根

後序走訪的順序是「左、右、根」，所以序列最後一個節點為根。

$\text{fcbdg} \quad\Rightarrow\quad \text{根為 } g$

（二）由前序走訪找根

前序走訪的順序是「根、左、右」，所以序列第一個節點為根。

$\text{IBCDFMN} \quad\Rightarrow\quad \text{根為 } I$

（三）由中序與前序重建二元樹

中序序列為「abcedfjgih」，前序序列為「jcbadefigh」。

1. 前序序列第一個節點是根，因此根為 $j$。在中序序列中，以 $j$ 分開左右子樹：

• 左子樹中序：abcedf
• 右子樹中序：gih

核心觀念

本題考查 TCP/IP 協定組各層的分工。常見的四層架構由下而上為：

不同教材可能採五層模型，將網路存取層再分為資料鏈結層與實體層；本題所列工作依四層 TCP/IP 模型判斷即可。

解題方法

依題目中的關鍵動詞辨認各層職責：

• 「決定路徑」涉及路由，屬網際網路層。
• 「連至傳輸媒介」涉及網路介面與媒介存取，屬網路存取層。
• 「提供終端使用者服務」屬應用層。
• 「產生使用者資料包」指建立承載應用程式資料的傳輸層資料單位，屬傳輸層。

各小題解析

（一）決定路徑：網際網路層

核心觀念

本題考 C 語言的迴圈執行次數，尤其是：

• while 會先檢查條件；條件成立才執行迴圈本體。
• for 每一輪依序執行「條件檢查 → 迴圈本體 → 更新式」。若迴圈本體也修改控制變數，該修改會與更新式一併影響下一輪條件判斷。
• 題目所問的「執行多少行敘述」，以下按每次實際執行的敘述計數；迴圈條件檢查本身不計入敘述行數。

解題方法

逐輪記錄控制變數的值，並計算迴圈本體中各敘述執行的次數。

(一) while 迴圈

B=5;
while (B<8) {
 statement;
 B=B-2;
}

B=5 先執行一次。接著逐輪追蹤：

每輪結束後，B 都減少 2，仍小於 8，因此條件永遠成立，迴圈不會終止。statement; 與 B=B-2; 會持續執行，執行次數均為無限次；加上迴圈前的 B=5;，總執行敘述行數也是無限次。

(二) for 迴圈

for (int i=5; i<20; i++) {
 statement;
 i=i+1;
}

核心觀念

本題考查兩組密碼學分類：

• 對稱式金鑰密碼：加密與解密使用相同金鑰，或使用可由彼此直接推導的金鑰；傳訊雙方須事先安全共享金鑰。
• 非對稱式金鑰密碼：每位使用者持有一組數學上相關的公鑰與私鑰，通常以其中一把加密、另一把解密。
• 單字母替代密碼：每一個明文字母都固定替換成一個密文字母。
• 多字母替代密碼：同一個明文字母會依位置或密鑰等條件，替換成不同密文字母。

解題方法

（一）判斷金鑰密碼類型

題目指出甲、乙「共享一個非常大的數值」，而且該數值作為雙向的加密及解密金鑰。判斷重點是加密與解密是否使用同一把共享金鑰，不是金鑰數值有多大。

因此，這是對稱式金鑰密碼：甲、乙使用共享的同一把金鑰進行加密與解密。非對稱式密碼則以公鑰、私鑰成對運作，不是雙方共享同一把雙向金鑰。

（二）判斷替代密碼類型