113 專技高考高等考試 電子工程技師 電子計算機原理 考古題詳解

核心觀念

本題考查 DMA 如何減少 CPU 介入輸入／輸出（I/O）資料傳輸，以及 DMA 與 CPU 共用記憶體所造成的馮紐曼瓶頸。

DMA 控制器可在 CPU 設定傳輸參數後，直接在周邊設備與主記憶體之間搬移資料。傳統由 CPU 負責搬移時，CPU 必須反覆讀取周邊資料，再將資料寫入記憶體；DMA 則讓 CPU 不必逐筆執行這些搬移指令。

馮紐曼架構中，CPU 與 DMA 控制器通常共用主記憶體及其通道。當 DMA 傳輸時會占用記憶體頻寬，CPU 存取記憶體可能因此延遲，形成處理器與記憶體間的頻寬瓶頸。

解題方法

分別從「CPU 工作量」與「記憶體通道競爭」兩個角度作答：

1. 說明 DMA 如何將大量資料搬移工作交由控制器處理，讓 CPU 能同時執行其他工作。
2. 說明 DMA 傳輸仍須使用主記憶體通道；DMA 與 CPU 同時存取記憶體時會競爭頻寬，造成 CPU 等待。

DMA 為何提升電腦效能

• **減少 CPU 介入與指令負擔：**若由 CPU 搬移一大批資料，CPU 必須反覆執行讀取、寫入及控制迴圈。DMA 可依設定自行傳送整個區塊，減少 CPU 用於 I/O 搬移的時間。
• **支援 CPU 與 I/O 重疊運作：**DMA 傳輸期間，CPU 可執行其他不需使用同一記憶體通道的工作。傳輸完成後，DMA 控制器再以中斷通知 CPU，CPU 無須逐筆監看資料。
• **提高大量資料傳輸效率：**對磁碟、網路卡等需要傳送大量資料的設備，DMA 避免 CPU 對每個資料單位都親自處理，讓系統整體吞吐量提高。

核心觀念

本題考查共享媒介存取協定的差異，以及無線媒介的特性如何影響碰撞處理方式。

• CSMA/CD（載波感測多重存取／碰撞偵測）：傳送前先感測媒介；媒介空閒時開始傳送，並在傳送期間持續偵測碰撞。若發生碰撞，便停止傳送、等待隨機退避，再重新嘗試。
• CSMA/CA（載波感測多重存取／碰撞避免）：傳送前感測媒介，並透過隨機退避、等待間隔等程序降低同時傳送而碰撞的機率；無線區域網路可搭配 RTS/CTS 交換，緩解隱藏節點造成的碰撞。

兩者的關鍵差別是：CSMA/CD 側重「傳送中偵測碰撞並處理」；CSMA/CA 側重「傳送前降低碰撞發生機率」。

解題方法

可從碰撞偵測的可行性、碰撞發生後的效率、無線網路的節點拓樸三方面比較。核心理由是無線裝置在傳送時不易可靠地同時接收並判斷媒介狀態，因此無線網路較適合在傳送前降低碰撞機率。

詳細分析

一、技術可行性：無線裝置難以可靠地邊傳送、邊偵測碰撞

在有線乙太網路中，網路介面可在傳送訊號時監測媒介上的電氣狀態，將傳送訊號與媒介訊號比較；若偵測到不一致，即可判定發生碰撞。這使 CSMA/CD 能在碰撞後及早停止傳送，減少無效占用媒介的時間。

無線裝置則以天線發射訊號，傳送訊號通常遠強於接收端可能收到的其他裝置訊號。自身發射訊號容易掩蓋微弱的碰撞訊號，讓裝置難以在傳送期間可靠地判斷是否有其他節點同時傳送。此外，無線環境的訊號強弱會受距離、遮蔽物、干擾與衰減影響，單靠接收端的載波感測，也不一定能反映接收端實際是否會收到干擾。

因此，無線網路採用傳送前感測與退避，並在需要時使用 RTS/CTS 等機制來降低碰撞機率，比依賴傳送期間偵測碰撞更實際。

二、網路效能：碰撞後重傳成本較高，宜先減少碰撞

碰撞發生時，多個節點所傳送的資料可能無法正確接收，造成媒介時間浪費；各節點還須等待退避時間後重傳。無線網路的傳輸速率與鏈路品質可能隨環境變動，重傳也會消耗有限的無線頻道資源與裝置電力。

核心觀念

本題比較兩個泡泡排序版本的正確性、比較次數、時間複雜度與提前終止機制。泡泡排序每次由左至右比較相鄰元素；若前者大於後者便交換。每一趟結束時，該趟所比較範圍內的最大值會移至最右端。

兩個版本皆以 arr[j] > arr[j + 1] 作為交換條件，因此相等元素不會互換，具有穩定性。兩者皆在原陣列內直接交換，額外空間複雜度為 $O(1)$。

解題方法

令陣列長度為 $n$。

版本一：每趟都掃描全陣列

bubble_sort_v1 的外層執行 $n$ 趟，內層每趟固定執行 $n-1$ 次比較，因此總比較次數為

時間複雜度在最好、平均及最壞情況下皆為 $O(n^2)$。即使陣列已經排序完成，程式仍會執行所有比較，沒有提前結束機制。

版本一每趟都比較至陣列尾端，雖然每完成一趟，尾端已有一個元素到達正確位置，但程式沒有利用這項性質縮小下一趟的掃描範圍。因此它仍可正確排序，但做了多餘的比較。

版本二：縮小掃描範圍並可提前結束

bubble_sort_v2 的內層範圍是 range(n - i - 1)。第 $i$ 趟完成後，右端已有 $i+1$ 個元素依序到位，下一趟只需比較尚未排序的前段。

此外，每趟開始時令 swapped = False；發生交換時改為 True。若一整趟都沒有交換，表示所有相鄰元素皆符合遞增順序，陣列已排序，外層迴圈便可提前結束。

• 最好情況：輸入陣列已排序，只需第一趟的 $n-1$ 次比較，時間複雜度為 $O(n)$。
• 平均及最壞情況：仍須進行數量級為 $n^2$ 的比較與交換，時間複雜度為 $O(n^2)$。
• 額外空間：$O(1)$。

比較與評論

核心觀念

本題考查二進位與十六進位的位元分組，以及遮罩（mask）和位移運算。每 4 個二進位位元可表示一個十六進位數字，因此可由整數的最高位元開始，每次擷取 4 位元（即一個 nibble），再轉成對應的十六進位字元。

解題方法

程式以 sizeof(int) * 8 計算 int 的位元數，並以每 4 位元一組處理。設 int 有 $W$ 個位元，則迴圈執行 $W/4$ 次，逐組處理從最高位到最低位的位元。

1. 初始化遮罩與位移量

unsigned int mask = 0xF0000000;
int shift_amount = (sizeof(int) * 8) - 4;

在常見的 32 位元 int 環境中，mask 為 1111 0000 ... 0000，先對準最高的 4 個位元；shift_amount 初值為 28，使擷取出的位元右移到最低 4 位。

2. 逐組擷取十六進位數字

int hex_digit = (num & mask) >> shift_amount;

num & mask 保留目前遮罩所對應的 4 個位元，其餘位元清為 0；再右移 shift_amount 位，取得介於 0 至 15 的數值。

例如某組位元為 1010，擷取結果就是二進位的 1010，也就是十進位 10。

3. 略過前導零，輸出有效位數

if (hex_digit != 0 || leading_zero_found) {
leading_zero_found = 1;
printf("%c", toHexDigit(hex_digit));
}

在遇到第一個非零位數前，不輸出零；遇到第一個非零位數後，後續每組都輸出，包含中間或末尾的零。如此可省略前導零，但保留十六進位數值所需的零。