112 年專技高考高等考試電子工程技師考古題與詳解

Question 1

已知某一行程（Process）的分頁參考順序如下，請分別應用 FIFO，以及 LRU 演算法，解析不同演算法會產生的分頁置換（Page replacement）情形以及產生分頁錯誤的次數。

分頁參考順序： $1,\ 2,\ 1,\ 3,\ 5,\ 1,\ 0,\ 5,\ 2,\ 1,\ 5,\ 1$

Accepted Answer

核心觀念 本題考查分頁系統中的頁面置換演算法。參考的頁面不在記憶體中時，會發生一次分頁錯誤；若記憶體尚有空框，就載入該頁面，若已滿，則依演算法選出一頁置換。 - FIFO（先進先出）：置換最早載入記憶體的頁面。頁面命中時不改變其載入先後順序。 - LRU（最近最少使用）：置換最久未被參考的頁面。頁面命中時，該頁面更新為最近使用。 題目未註明頁框數；以下依常見設定，假設有 3 個頁框。初始載入空頁框也計為分頁錯誤。 解題方法 依參考順序逐步更新頁框內容。表中的「置換」欄記錄發生分頁錯誤時被移出的頁面；「—」表示尚有空頁框可用。 FIFO 演算 | 步驟 | 參考頁面 | 頁框 1 | 頁框 2 | 頁框 3 | 結果 | |---:|---:|---:|---:|---:|---| | 1 | 1 | 1 | — | — | 錯誤，載入 | | 2 | 2 | 1 | 2 | — | 錯誤，載入 | | 3 | 1 | 1 | 2 | — | 命中 | | 4 | 3 | 1 | 2 | 3 | 錯誤，載入 | | 5 | 5 | 5 | 2 | 3 | 錯誤，置換 1 | | 6 | 1 | 5 | 1 | 3 | 錯誤，置換 2 | | 7 | 0 | 5 | 1 | 0 | 錯誤，置換 3 | | 8 | 5 | 5 | 1 | 0 | 命中 | | 9 | 2 | 2 | 1 | 0 | 錯誤，置換 5 | | 10 | 1 | 2 | 1 | 0 | 命中 | | 11 | 5 | 2 | 5 | 0 | 錯誤，置換 1 |

Question 2

有一家公司使用 $192.192.78.0/24$ 作為該公司的網域，並需分割四個子網路給所屬部門，其中資訊部門需要 $80$ 個 IP、業務部門需要 $50$ 個 IP、製造部門與人資部門各需要 $20$ 個 IP，請提出分配給四個部門的網段、每個部門的網路遮罩、每個部門的廣播 IP 位址。

Accepted Answer

核心觀念 本題考查 VLSM（可變長度子網路遮罩）：依各部門所需的主機數，配置大小不同的子網路。每個子網路的位址數必須是 $2$ 的冪次方，且傳統 IPv4 子網路中，網路位址與廣播位址不能指派給主機，因此可用主機數為： $$ 2^h-2 $$ 其中 $h$ 是主機位元數；前綴長度則為 $32-h$。 解題方法 先由需求最大的部門開始分配，並將各部門需求換算為最小可用子網路： | 部門 | 需求 IP 數 | 主機位元數 $h$ | 子網路位址數 | 前綴長度 | 可用主機數 | |---|---:|---:|---:|---:|---:| | 資訊 | 80 | 7 | $2^7=128$ | /25 | 126 | | 業務 | 50 | 6 | $2^6=64$ | /26 | 62 | | 製造 | 20 | 5 | $2^5=32$ | /27 | 30 | | 人資 | 20 | 5 | $2^5=32$ | /27 | 30 | 例如資訊部門需至少 $80$ 個可用 IP，因此找最小的 $h$ 使 $2^h-2\geq80$。$h=6$ 時可用 $62$ 個，不足；$h=7$ 時可用 $126$ 個，所以配置 /25。 接著從公司網段 $192.192.78.0/24$ 的起點，依序配置並確保每個網段起點符合其區塊大小： 1. 資訊部門配置 $192.192.78.0/25$，涵蓋 $192.192.78.0$ 至 $192.192.78.127$。 網路遮罩為 $255.255.255.128$，廣播位址為 $192.192.78.127$。 2. 業務部門配置 $192.192.78.128/26$，涵蓋 $192.192.78.128$ 至 $192.192.78.191$。 網路遮罩為 $255.255.255.192$，廣播位址為 $192.192.78.191$。 3. 製造部門配置 $192.192.78.192/27$，涵蓋 $192.192.78.192$ 至 $192.192.78.223$。 網路遮罩為 $255.255.255.224$，廣播位址為 $192.192.78.223$。

Question 3

已知一組 Preorder 的序列為「ABDGHCE」，另一組 Postorder 的序列為「GHDBECA」，請問由這二組序列是否可以決定出一棵唯一的二元樹？

答案若為「是」，請畫出此唯一的二元樹。

答案若為「否」，請畫出至少二棵相異的二元樹，可同時符合上述的 Preorder 序列及 Postorder 序列。

Accepted Answer

核心觀念

Preorder（前序走訪）依序為「根、左子樹、右子樹」；Postorder（後序走訪）依序為「左子樹、右子樹、根」。

兩種走訪序列能確定根節點：Preorder 的第一個節點是根，Postorder 的最後一個節點也是根。不過，若某個節點只有一個子節點，序列無法分辨它是左子節點還是右子節點，因此一般二元樹的 Preorder 與 Postorder 不一定能唯一決定二元樹。

解題方法

Preorder 為 ABDGHCE，所以根節點是 A；Postorder 為 GHDBECA，最後一個節點也是 A，兩序列根節點一致。

再看根的下一層：Preorder 中 B 緊接在 A 之後，而 Postorder 中 B 出現在 A 之前。依走訪定義，B 可以是 A 的左子節點，也可以是 A 的右子節點；若 A 只有一個子節點，兩種安排都不會改變前序或後序的節點順序。

Question 4

使用二元搜尋樹（Binary Search Tree）儲存資料的操作過程，已知一組資料的輸入及刪除順序如下：

Input: $53,\ 82,\ 77,\ 37,\ 26,\ 45,\ 87,\ 18,\ 66,\ 12,\ 84,\ 79$

Delete: $12,\ 77$

Input: $58,\ 23,\ 51,\ 16,\ 95$

Delete: $53$

請畫出最終的 Binary Search Tree。

若被刪除的節點為雙子節點，則一律採選左子樹最大值取代的模式。

Accepted Answer

核心觀念

二元搜尋樹（Binary Search Tree, BST）中，每個節點都符合下列大小關係：

左子樹所有節點值小於該節點。
右子樹所有節點值大於該節點。
插入資料時，從根節點開始比較，依大小往左或往右，直到找到空位。
刪除雙子節點時，本題指定以「左子樹最大值」取代。這個值是該節點的中序前驅；取代後，還須從左子樹中刪除原前驅節點。

解題方法

依題目給定的操作順序，逐一插入或刪除節點。為減少反覆重畫，以下列出每次刪除時需要處理的結構，以及最後一批資料插入後的變化。

1. 插入第一批資料

依序插入 $53,82,77,37,26,45,87,18,66,12,84,79$ ，得到：

 53
 / \
 37 82
 / \ / \
 26 45 77 87
 / / \ /
 18 66 79 84
 /
 12

2. 刪除 $12$ 、 $77$

$12$ 是葉節點，直接刪除。
$77$ 有兩個子節點 $66$ 、 $79$ 。依題意，以左子樹最大值 $66$ 取代 $77$ ，再刪除原位置的 $66$ 。

此時右子樹為：

3. 插入第二批資料

依序插入 $58,23,51,16,95$ ：

Question 5

請說明快速記憶體（Cache memory）與主記憶體（Main memory）的對應（Mapping）方法有哪些，以及如何對應？

Accepted Answer

核心觀念

Cache 是容量較小、速度較快的記憶體，用來暫存主記憶體中近期或常被使用的資料。主記憶體分成固定大小的區塊（block），Cache 分成固定大小的列（cache line）；一個主記憶體區塊載入 Cache 時，會放入一個列。

本題考查的是：**主記憶體區塊如何指定到 Cache 的列，以及如何判斷 Cache 中的資料對應哪個主記憶體區塊。**常見方法有三種：直接對應、全相聯對應、組相聯對應。

設主記憶體區塊編號為 $j$ ，Cache 共有 $C$ 列。

解題方法

1. 直接對應（Direct Mapping）

每個主記憶體區塊只能放在 Cache 的唯一一列，對應關係為：

\text{Cache 列號}=j \bmod C

例如 Cache 有 $8$ 列，主記憶體區塊 $13$ 對應到第 $13\bmod 8=5$ 列。區塊 $5、13、21$ 等也都對應到第 $5$ 列，彼此會競爭同一列。

位址可分為：

\text{Tag}\mid\text{Index}\mid\text{Block offset}

其中，Index 指定 Cache 列，Tag 用來辨認該列目前存放的是哪個主記憶體區塊，Block offset 指出區塊內的位元組或字的位置。查找時，依 Index 取出列，再比較 Tag，且有效位元須為 1，才算命中。

2. 全相聯對應（Fully Associative Mapping）

任何主記憶體區塊都可以放入 Cache 的任一列，沒有固定的列號公式。位址可分為：

\text{Tag}\mid\text{Block offset}

Question 6

請寫出 $16$ 進位表示的二個數值 $4D9F$、$1FC9$ 之 $10$ 進位計算結果。

Accepted Answer

核心觀念 十六進位每一位的位值是 $16$ 的冪次，從最右位起依序為 $16^0、16^1、16^2、16^3$。十六進位數字 $A$ 至 $F$ 分別代表十進位的 $10$ 至 $15$。本題要將 $4D9F{16}$ 與 $1FC9{16}$ 各自轉換成十進位數值。 解題方法 依各位數字乘上對應位值，再將乘積相加。 對 $4D9F{16}$： $$ 4D9F{16} =4	imes16^3+13	imes16^2+9	imes16^1+15	imes16^0 $$ $$ =4	imes4096+13	imes256+9	imes16+15 =16384+3328+144+15 =19871{10} $$

Question 7

已知有一文檔，內文出現的字元及次數如下表，請應用 Huffman 編碼演算法，產出 Huffman tree 以及每個字元對應的 Huffman code。

說明：建立 Huffman tree 的過程，不失一般性，數值排列順序一律由左至右、由大到小；當有新產出的數值時，會插入到序列中，相同數值的最左邊。

Character	Frequency	Huffman Codes
Space	7
A	3
E	4
F	4
H	1
L	2
M	2
P	5
Q	6
S	3
T	2
X	1

🖼️ 本題原卷含圖表。基於試題來源之版權考量，本站不轉載原卷影像；題目文字已完整轉錄，圖表請自行參閱考選部公告之試題原檔。

Accepted Answer

核心觀念 Huffman 編碼以字元出現次數作為權重，反覆取出權重最小的兩個節點合併成新節點，直到形成一棵樹。從根節點到字元葉節點的路徑就是該字元的編碼；本題採「左枝為 0、右枝為 1」。 依題目規則，初始同頻字元沿用表格順序；新節點插入同頻數值最左邊。本解答合併時依序列由左至右排列左右子節點。 解題方法 每一步取目前序列中最右側的兩個節點合併，再依權重由大到小排列。以下以 Sp 表示 Space，合併節點用括號中的字元或節點標示： | 步驟 | 合併的兩個節點 | 新節點權重 | |---:|---|---:| | 1 | H(1) + X(1) | HX(2) | | 2 | M(2) + T(2) | MT(4) | | 3 | HX(2) + L(2) | HXL(4) | | 4 | A(3) + S(3) | AS(6) | | 5 | E(4) + F(4) | EF(8) | | 6 | HXL(4) + MT(4) | HXLMT(8) | | 7 | Q(6) + P(5) | QP(11) | | 8 | Sp(7) + AS(6) | SpAS(13) | | 9 | HXLMT(8) + EF(8) | HXLMTEF(16) | | 10 | SpAS(13) + QP(11) | SpASQP(24) | | 11 | SpASQP(24) + HXLMTEF(16) | 根節點(40) | Huffman tree

Question 8

請完成以下矩陣相乘函式的指令。 Void MatrixMultiplication(A, B, C, m, p, n){ for (i=0; i<m; i++){ for (j=0; j<p; j++){ ① for(k = 0; k < n; k++){ C[i][j] = ② + ③ ; } printf("%d ", C[i][j]); } printf("
"); } }

Accepted Answer

核心觀念 矩陣乘法 $C=A	imes B$ 的每個元素，都是 $A$ 的第 $i$ 列與 $B$ 的第 $j$ 欄對應元素相乘後加總： $$ C[i][j]=\sum{k=0}^{n-1} A[i][k]B[k][j] $$ 其中 $A$ 的維度為 $m	imes n$，$B$ 的維度為 $n	imes p$，因此乘積矩陣 $C$ 的維度為 $m	imes p$。內層迴圈每次累加一個乘積，累加前須先將 $C[i][j]$ 歸零。 解題方法 外層迴圈以 $i$ 選取 $C$ 的列，中層迴圈以 $j$ 選取 $C$ 的欄。每開始計算一個 $C[i][j]$，先將其設為 $0$；接著內層迴圈令 $k$ 從 $0$ 到 $n-1$，依序累加 $A[i][k]B[k][j]$。 因此三個空格依序填入：

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

第一題10 分

第二題20 分

核心觀念

解題方法

第三題10 分

核心觀念

解題方法

第四題10 分

核心觀念

解題方法

1. 插入第一批資料

2. 刪除 $12$ 、 $77$

3. 插入第二批資料

第五題15 分

核心觀念

解題方法

1. 直接對應（Direct Mapping）

2. 全相聯對應（Fully Associative Mapping）

第六題5 分

第七題20 分

第八題10 分

核心觀念

解題方法

其他考古題

112 年電子工程技師的其他科目

電子工程技師《電子計算機原理》其他年度

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

第 一 題10 分

第 二 題20 分

核心觀念

解題方法

第 三 題10 分

核心觀念

解題方法

第 四 題10 分

核心觀念

解題方法

1. 插入第一批資料

2. 刪除 121212、777777

3. 插入第二批資料

第 五 題15 分

核心觀念

解題方法

1. 直接對應（Direct Mapping）

2. 全相聯對應（Fully Associative Mapping）

第 六 題5 分

第 七 題20 分

第 八 題10 分

核心觀念

解題方法

其他考古題

112 年電子工程技師的其他科目

電子工程技師《電子計算機原理》其他年度

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

第一題10 分

第二題20 分

第三題10 分

第四題10 分

2. 刪除 $12$ 、 $77$

第五題15 分

第六題5 分

第七題20 分

第八題10 分