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

（一）CPU 執行程式的步驟

核心觀念

本題考查 CPU 如何透過「取指、解碼、執行」的指令週期逐一處理程式指令。CPU 主要使用程式計數器（Program Counter, PC）追蹤下一個要執行的指令位址，並透過控制單元、暫存器、算術邏輯單元（ALU）及主記憶體完成指令。

解題方法：依指令週期說明

1. 取指（Fetch）：PC 內存放下一個指令的位址。CPU 將該位址送至記憶體，讀取指令並放入指令暫存器（Instruction Register, IR）。
2. 更新 PC：PC 通常遞增至下一個指令位址；若指令是跳躍或分支指令，後續則依執行結果改寫 PC。
3. 解碼（Decode）：控制單元解讀 IR 中的操作碼，判斷指令要做的操作，以及所需運算元的來源與位置。
4. 取得運算元（Operand Fetch）：若運算元在暫存器或記憶體中，CPU 依指令指定的位置取出；若為立即值，則直接使用指令中的數值。
5. 執行（Execute）：控制單元發出控制訊號，指揮 ALU 或其他功能單元執行運算、資料搬移、輸入輸出或分支判斷等工作。
6. 寫回結果（Write Back）：將運算或資料處理結果寫入指定的暫存器或記憶體，並更新相關狀態旗標，例如零旗標或進位旗標。
7. 檢查中斷並進入下一週期：CPU 依架構處理待服務的中斷；

（一）網路層的任務與路由

核心觀念

網際網路採用分層架構。網路層（Network Layer）負責讓封包從來源主機跨越一個或多個網路，抵達目的主機，主要任務包括：

• 邏輯定址：以 IP 位址識別來源與目的主機。
• 路由選擇：根據目的位址選擇封包應經過的路徑。
• 封包轉送：路由器依據轉送表，將封包送往下一個網路或下一個路由器。
• 跨網路傳輸：處理不同網路之間的封包傳遞；必要時也涉及封包分段等功能。

網路層最常用的兩個協定是 IP（Internet Protocol） 與 ICMP（Internet Control Message Protocol）。IP 負責位址與封包傳送；ICMP 用來回報網路層的錯誤或提供診斷資訊，例如 ping 使用的回應訊息。路由協定（例如 OSPF、BGP）則用來交換路由資訊、建立路由表，與 IP、ICMP 的用途不同。

解題方法

判斷各層的工作，可先看它處理的位址與傳輸範圍：

• 網路層以 IP 位址為依據，處理跨網路的封包傳送。
• 資料鏈結層以 MAC 位址為依據，處理同一鏈結或區域網路內的訊框傳送。
• 傳輸層以 連接埠號碼識別應用程序，負責端點間的傳輸服務。

因此，題目問路由能否在傳輸層或資料鏈結層完成，應區分「IP 層的路由」與其他層可能具有的轉送功能。

路由是否能在其他層完成

標準網際網路架構中的 IP 路由屬於網路層工作。路由器檢視 IP 封包的目的 IP 位址，查詢路由表後決定下一跳；每一跳實際送出時，再由資料鏈結層封裝成該鏈結所需的訊框。

• 傳輸層不能取代網路層路由：TCP、UDP 主要依連接埠號碼提供端點到端點的傳輸服務。它們不負責在多個 IP 網路之間選路與轉送封包。
• 資料鏈結層不能取代 IP 路由：資料鏈結層的 MAC 位址與訊框傳送範圍通常限於單一鏈結或區域網路。它會承載 IP 封包並把訊框送到下一跳，但不能單靠一般資料鏈結層機制完成跨多個網路的 IP 路由。

核心觀念

本題考查堆疊的後進先出特性，以及巢狀迴圈的執行次數與時間複雜度。

堆疊（Stack）是一種線性資料結構，資料的插入與刪除都在同一端進行，該端稱為「頂端」（Top）。堆疊遵守後進先出（Last In, First Out, LIFO）：最後放入的資料會最先取出。常見操作包括：

• push(x)：將資料 $x$ 放入堆疊頂端。
• pop：移除並取出頂端資料。
• peek：查看頂端資料但不移除。
• 空堆疊執行 pop 會發生下溢（underflow）；容量有限的堆疊放入超過容量的資料會發生上溢（overflow）。

（一）以堆疊將十進制正整數轉換為二進制

解題方法

十進制整數反覆除以 $2$，每次記錄餘數；餘數依產生順序是由低位元到高位元排列。二進制表示則需由高位元讀到低位元，因此將餘數依序推入堆疊，再逐一彈出，即可得到正確順序。

演算法步驟

1. 設輸入正整數為 $N$。
2. 當 $N>0$ 時，計算餘數 $r=N\bmod 2$，並將 $r$ 推入堆疊。
3. 更新 $N=\lfloor N/2\rfloor$。
4. 重複至 $N=0$，再逐一彈出堆疊中的餘數；彈出順序即為二進制表示。

輸入 N
建立空堆疊 S

while N > 0:
 r = N mod 2
 push(S, r)
 N = N // 2

while S 非空:
 輸出 pop(S)

例如 $N=13$：

餘數依序推入為 $1,0,1,1$，彈出後得到 $1101_2$，所以 $13_{10}=1101_2$。

（二）第 07 行的執行次數與時間複雜度

解題方法

外層迴圈每次使 $k$ 加 $1$，內層迴圈的步進值為 $2^k$。固定一個 $k$，內層的 j 值為 $1,1+2^k,1+2\cdot2^k,\ldots$，且必須小於 $n$。

外層 range(1, n//2) 使 $i$ 取 $1$ 到 $n//2-1$，因此執行 $m=\lfloor n/2\rfloor-1$ 次；

（一）類別、方法與物件

核心觀念

物件導向程式設計以「物件」組織程式。物件將資料與操作資料的程式碼結合，並透過類別描述物件的共同結構與行為。

• 類別（Class）：建立物件的藍圖或模板，定義該類物件具有哪些資料屬性，以及可執行哪些方法。
• 方法（Method）：定義在類別中的函數，描述該類物件能執行的操作；方法通常可讀取或修改物件的屬性。
• 物件（Object）：依類別建立出來的實體，也稱為類別的實例（instance）。每個物件具有類別所定義的屬性與方法，並可保存自己的資料狀態。

解題方法與關係

類別、方法與物件的關係可整理如下：

1. 類別描述共同規格：先在類別中定義屬性和方法。
2. 物件依類別建立：建立物件時，各物件取得類別所描述的結構，並可持有各自的屬性值。
3. 方法由物件呼叫：物件透過方法執行操作；方法可使用該物件的屬性來完成工作。

以「銀行帳戶」為例，BankAccount 是類別，可定義 balance（餘額）屬性，以及 deposit（存款）方法。依此類別建立的 account1、account2 是兩個物件，各自保存不同的餘額；呼叫 account1.deposit(500)，會透過 deposit 方法增加 account1 的餘額，不會改變 account2 的餘額。

解題技巧

記憶時可用「類別是藍圖、物件是實例、方法是物件可執行的操作」掌握三者差異。回答時要指出方法屬於類別所定義的行為，並說明不同物件可有不同的資料狀態。

（二）遞迴程式功能與疊代改寫

核心觀念

程式中的函數符合費波那契數列的遞迴定義：