109 關務特考三等 電機工程 計算機概論 考古題詳解

核心觀念

記憶體階層（memory hierarchy）​是依照存取速度、容量、每位元成本與揮發性等特性，將多種記憶體組成由快至慢、由小至大的層次結構。典型順序如下：

層級愈靠近處理器，存取速度愈快、容量通常愈小、每位元成本愈高；愈遠離處理器，速度愈慢、容量通常愈大、每位元成本愈低。暫存器、快取與主記憶體多屬揮發性記憶體；輔助儲存則可在斷電後保留資料。

運作流程

處理器要讀取資料或指令時，系統由最靠近處理器的層級開始查找：

1. 先查暫存器或快取：若所需資料已在目前層級，稱為命中（hit），即可快速提供資料。
2. 未命中則往下一層查找：例如快取未命中時，向主記憶體取得資料；主記憶體也沒有時，再由輔助儲存載入。
3. 將資料帶回較高層級：取得資料後，通常會將該資料及相鄰資料或同一區塊一併載入較快的上層，以供近期可能發生的存取使用。
4. 寫入時依政策更新：資料修改後，系統依寫入策略更新上層與下層。常見策略包括同步更新下層的 write-through，以及先更新上層、待適當時機再寫回下層的 write-back。

未命中需要到較慢層級取資料，故會增加存取時間。快取的命中率愈高，處理器平均等待時間通常愈低。常用的平均記憶體存取時間表示式為：

其中未命中率為 $1-\text{命中率}$。

優點

核心觀念

TCP/IP 協定組依功能可分為四層：

本題要依各項工作的功能判斷其所屬層級。題目未涉及法條。

解題方法

判斷時可由「工作對象」切入：

1. 涉及封包如何跨越不同網路、選擇傳送路徑，屬於網際網路層。
2. 涉及實際連接電纜、無線媒介或區域網路鏈路，屬於網路存取層。
3. 涉及讓使用者或應用程式使用網路服務，屬於應用層。

（一）各項工作所屬層級

1. 決定路徑（route determination）：網際網路層 網際網路層依目的 IP 位址進行封包轉送與路由選擇，使封包能經由適當路徑抵達目的網路。

核心觀念

最小成本展開樹（minimum-cost spanning tree，MCST）是連通加權圖的一棵展開樹：它包含圖中所有頂點、沒有環路，且總邊權重最小。若圖有 $n$ 個頂點，展開樹必須有 $n-1$ 條邊。

後序追蹤（post-order traversal）的順序是：左子樹、右子樹、根節點。

（一）最小成本展開樹的定義

MCST 是連通加權圖中，涵蓋所有頂點且不形成環路的邊集合，其邊權重總和在所有展開樹中最小。對有 $n$ 個頂點的圖，MCST 恰有 $n-1$ 條邊。

（二）Figure-1 的 MCST 總距離

可用 Kruskal 演算法：依邊的距離由小到大選邊，若加入該邊會形成環路就略過，直到選滿 $6-1=5$ 條邊。

圖中各邊依距離排序如下：

依序選取：

1. 選 $BF$，距離為 $1$。
2. 選 $AB$，距離為 $2$。
3. 選 $AE$，距離為 $2$。
4. 選 $CE$，距離為 $3$。

核心觀念

counter 每次執行內層迴圈的第 9 行就增加 $1$。因此，最後的 counter 等於內層迴圈總共執行的次數。

外層變數 $i$ 從 $0$ 遞增至 $n-1$。固定某個 $i$ 時，內層變數 $j$ 從 $i$ 遞增至 $n-1$，共有 $n-i$ 次。

解題方法

將每一輪外層迴圈的執行次數加總：

例如 $i=0$ 時，內層執行 $n$ 次；$i=1$ 時執行 $n-1$ 次；最後 $i=n-1$ 時執行 $1$ 次。

解題技巧

固定外層迴圈的變數，數出內層迴圈從起始值到終止值的次數，再加總即可。注意 j < n 不包含 $n$，所以每輪次數是 $n-i$，不是 $n-i+1$。

【答案】 最後 counter 的值為 $\boxed{\frac{n(n+1)}{2}}$。

（二）整數轉二進位輸出