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

核心觀念

系統匯流排負責連接 CPU、記憶體及 I/O 設備，通常包含：

• 資料匯流排：傳送資料。
• 位址匯流排：指定資料來源或目的地。
• 控制匯流排：傳送讀取、寫入、中斷等控制訊號。

CPU 與記憶體的運作速度通常高於 I/O 設備。若各種速度不同的設備直接共用匯流排，便需要協調傳輸時機，也須處理不同設備的電氣特性、資料格式與控制方式。

解題方法與說明

I/O 設備可以直接連接到系統匯流排，但實際系統通常由 I/O 控制器或介面模組作為設備與匯流排之間的橋接介面。控制器負責：

1. 配合匯流排協定，傳送位址、資料與控制訊號。
2. 緩衝資料，調節 CPU、記憶體與慢速 I/O 設備之間的速度差異。
3. 將設備特有的控制方式轉換成系統可辨識的操作。
4. 必要時處理中斷或直接記憶體存取（DMA）。

因此，回答「能否直接連接」時，須區分匯流排架構上可連接與實際上通常透過控制器連接。若將 I/O 設備直接掛上匯流排而沒有適當介面，可能造成協定不相容、速度無法配合或控制困難。

解題技巧

答題時先明確表態「可以」，再補充實務上通常透過 I/O 控制器或介面模組連接，並說明其協調速度、格式與控制訊號的功能，即可完整涵蓋題意。

（二）二補數的優點與 8 位元整數範圍

核心觀念

二補數（2’s complement）以固定 $n$ 位元表示有號整數。最高位元作為符號權重：正數的最高位元為 $0$；負數以其二補數編碼表示。其範圍為：

二補數的優點

核心觀念

網路採分層架構，每一層負責不同範圍的資料傳輸：

• 點對點（Point-to-Point）傳輸：相鄰網路節點之間的傳輸。資料在前往目的地的途中，會經過多段鏈路；每一段由該鏈路兩端的節點負責傳送與接收。例如，主機將封包交給家用路由器，路由器再經由下一條鏈路轉送。
• 端對端（End-to-End）傳輸：來源主機上的應用或傳輸端點，與目的主機上的對應端點之間的邏輯通訊。中間的路由器通常只負責轉送，不處理應用程式的完整資料內容。

解題方法

判別兩者時，先看通訊的範圍：

1. 若只描述相鄰節點間的一段鏈路，屬於點對點傳輸。資料鏈結層常處理這一段的成框、媒介存取與錯誤偵測；實際鏈路技術可使用乙太網路、Wi-Fi 或 PPP。
2. 若描述來源到目的端的整體通訊，屬於端對端傳輸。傳輸層的 TCP 或 UDP 提供主機間程序通訊所需的服務；應用層協定則處理電子郵件、網頁等應用需求。

解題技巧

「點對點」看一跳、一段鏈路；「端對端」看完整來源與目的端。封包從來源到目的地通常會經過多段點對點傳輸，而這些鏈路共同承載端對端通訊。兩者傳送的對象與範圍不同，不可混為一談。

（二）Adam 傳送電子郵件給 Bambi 的流程

核心觀念

電子郵件流程涉及使用者端郵件軟體、郵件伺服器、DNS、網路路由設備，以及 SMTP、POP3 或 IMAP 等協定。須分清楚：

• SMTP：用於郵件提交與郵件伺服器間的轉送。
• POP3／IMAP：收件者從郵件伺服器讀取郵件時常用的協定。
• DNS：查詢收件網域的郵件伺服器，通常利用 MX 記錄。

解題方法與完整流程

1. 撰寫與提交郵件 Adam 在臺南使用電腦或手機，透過郵件用戶端（MUA，例如郵件 App 或網頁郵件介面）撰寫郵件，填入 Bambi 的電子郵件地址與工作近況，並按下傳送。

核心觀念

本題考查兩個觀念：

1. 以陣列表示二元樹時，利用節點索引直接計算父節點與子節點位置。
2. 判斷二元搜尋樹（Binary Search Tree, BST）的條件。

採用從索引 $0$ 開始的陣列表示法時，索引為 $i$ 的節點，其：

• 左子節點索引：$2i+1$
• 右子節點索引：$2i+2$
• 父節點索引：$\left\lfloor \dfrac{i-1}{2} \right\rfloor$

空白元素代表該位置沒有節點。

（一）以陣列儲存二元樹的優點

1. 不需額外儲存指標

鏈結式二元樹必須為每個節點儲存左右子節點指標；陣列表示法只需依照索引計算子節點位置，可節省指標欄位所占的記憶體。

2. 子節點位置容易計算

對於索引 $i$ 的節點，可以直接透過下式找到子節點：

不需逐一追蹤指標。

3. 父節點位置容易取得

子節點也可以直接利用索引取得父節點：

因此適合進行向上或向下的樹結構操作。

4. 記憶體配置連續

陣列元素通常配置在連續記憶體位置，具有較佳的快取（Cache）區域性，存取速度通常比分散配置的鏈結節點更有效率。

5. 適合完整二元樹

對完整二元樹或接近完整二元樹而言，節點大多集中在陣列前段，空間浪費少，且不必使用空白指標。

6. 適合實作堆積

二元堆積（Binary Heap）通常以陣列儲存。最大堆積、最小堆積的插入、刪除與調整操作，都能利用索引快速找到父子節點。

7. 遍歷實作簡單

前序、中序、後序及層序走訪都可利用索引與遞迴方式實作，結構清楚。

8. 易於進行層次管理

索引位置直接反映節點所在層次，特別適合需要依層次處理節點的演算法，例如堆積與廣度優先走訪。

補充而言，若二元樹非常稀疏，陣列中會產生許多空白位置，空間效率反而不如鏈結式表示法。

（二）重建二元樹

解題方法

依照陣列表示二元樹的索引規則，從根節點索引 $0$ 開始：

• 若 $Arr[i]$ 為空，表示此處沒有節點。
• 若 $Arr[i]$ 有鍵值，建立一個節點。
• 再遞迴建立其索引為 $2i+1$ 與 $2i+2$ 的左右子樹。

演算法

Build(i):
 若 i > 14 或 Arr[i] 為空：
 回傳 NULL

 建立節點 Node，Node.key = Arr[i]
 Node.left = Build(2i + 1)
 Node.right = Build(2i + 2)

 回傳 Node

（一）C 程式：巢狀迴圈計數

核心觀念

本題考查巢狀 for 迴圈的執行次數。變數 order 初值為 $0$，每當內層迴圈執行一次，就加 $1$。

解題方法

輸入 $n=10$。外層迴圈條件為 $i<n-1$，所以 $i$ 依序為 $0,1,\ldots,8$。固定每個 $i$ 後，內層迴圈從 $j=i$ 開始，直到 $j=8$，因此執行次數為 $9-i$。

因此，

解題技巧

固定外層變數 $i$，先算內層迴圈執行次數，再將各次數相加。此程式的總執行次數也可寫成三角數公式 $\frac{(n-1)n}{2}$；代入 $n=10$ 得 $45$。

（二）Python 程式：遞迴計算累加和

核心觀念

函式 aloha(k) 使用遞迴計算從 $1$ 累加至 $k$ 的總和。當 $k\leq 0$ 時，遞迴終止並回傳 $0$；當 $k>0$ 時，回傳 $k+\text{aloha}(k-1)$。程式接著將 $k=0$ 至 $n$ 的函式結果依序存入串列 a。

解題方法