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

核心觀念

1. 二進位加權位置表示法（Weighted Positional Notation）：

• 整數部分權重為 $2^i$（$i = 0, 1, 2, \dots$）。
• 小數部分權重為 $2^{-j}$（$j = 1, 2, 3, \dots$），即 $2^{-1} = 0.5$、$2^{-2} = 0.25$、$2^{-3} = 0.125$、$2^{-4} = 0.0625$。

2. 基底轉換（Radix Conversion）：將二進位基底（Base-2）展開為十進位基底（Base-10）。
3. 二進位算術運算：遵循四則運算規則，先乘除後加減。

解題方法

本題要求計算 $A \times B + C$ 並以十進位表示。最穩健且不易出錯的切入點為：先將各二進位數分別轉換為十進位數值，再進行十進位的乘法與加法運算；亦可在二進位下完成運算後再轉為十進位作為驗算。

步驟一：將二進位數轉換為十進位數

1. 轉換整數 $A$： $A = (1011)_2 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = 11$

2. 轉換整數 $B$： $B = (1111)_2 = 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 4 + 2 + 1 = 15$ (或利用補數特性快速求得：$2^4 - 1 = 16 - 1 = 15$)

3. 轉換含小數的數字 $C$： $C = (1011.1011)_2$ 可分為整數部分與小數部分分別展開：

• 整數部分： $(1011)_2 = 8 + 0 + 2 + 1 = 11$
• 小數部分： $(0.1011)_2 = 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} + 1 \times 2^{-4}$ $= \frac{1}{2} + 0 + \frac{1}{8} + \frac{1}{16} = \frac{8 + 0 + 2 + 1}{16} = \frac{11}{16} = 0.6875$
• 合併整數與小數：

核心觀念

本題評量作業系統（Operating System）中**行程管理（Process Management）**的核心機制——行程生命週期與五狀態模型（Five-State Process Model）（源自 Abraham Silberschatz 所著之經典教科書《Operating System Concepts》）。

核心觀念與定義包含：

1. 行程（Process）的定義：執行中的程式（A program in execution），包含程式碼（Text section）、程式計數器（PC）、堆疊（Stack）、資料區塊（Data section）及堆積（Heap）等資源。
2. 五狀態模型之角色定位：

• 新建（New）：行程剛被建立，尚未載入記憶體。
• 就緒（Ready）：行程已在記憶體中，準備就緒等待分配 CPU。
• 執行（Running）：行程正佔有 CPU 並執行指令。
• 等待（Waiting / Blocked）：行程因等待某事件（如 I/O、信號）而暫停，無法被 CPU 排程。
• 結束（Terminated）：行程執行完畢或被中止，等待資源回收。

3. 排程器（Schedulers）與轉換驅動事件：

• 長期排程器（Long-term Scheduler / Job Scheduler）：控制系統多工程度（Degree of multiprogramming），負責將行程從 New 帶入 Ready。
• 短期排程器（Short-term Scheduler / CPU Scheduler）：頻繁執行，負責從 Ready 隊列中挑選行程分派（Dispatch）給 CPU 執行。
• 中斷（Interrupt）與系統呼叫（System Call）：驅動 Running 與 Ready、Waiting 之間的切換。

解題方法

本題為標準的申論圖形說明題，採「先圖後文、層次條列」之切入策略：

1. 繪製標準狀態轉換圖：精確標示 5 個狀態節點，並用有向邊（箭頭）正確連接 6 種狀態轉換事件。
2. 定義 5 種狀態：依生命週期順序（New $\rightarrow$ Ready $\rightarrow$ Running $\rightarrow$ Waiting $\rightarrow$ Terminated）簡明界定各狀態之系統資源配置現況。
3. 解析 6 種狀態改變事件：精確點出引發轉換的具體事件（如排程分派、時間配額用盡中斷、I/O 請求系統呼叫、I/O 完成中斷等）。

選項分析

本題為申論問答題，無選擇題選項。

解題技巧

1. 單向與雙向判斷竅門：

• 起點與終點皆為單向：New → Ready（准入）、Running → Terminated（離開）。
• 運算與中斷為雙向：Ready ↔ Running（Dispatch 與 Timeout / Interrupt）。

2. 最常犯考場陷阱：

• 陷阱：Waiting 狀態完成後直接跳回 Running？ 絕對錯誤！ 當 I/O 完成或等待事件發生時，行程只能轉入 Ready（就緒） 狀態重新排隊，絕對不可直接搶佔 CPU 進入 Running 狀態。
• 陷阱：Ready 狀態可以直接轉到 Waiting 狀態？ 不可能！ 行程必須在 Running 狀態下發出 I/O 請求或等待事件，才會進入 Waiting；Ready 狀態下的行程尚未取得 CPU，無法主動發出 I/O 呼叫。

【答案】

一、行程狀態轉換圖（State Transition Diagram）

核心觀念

1. IPv4 位址結構與表示法：

• IPv4（Internet Protocol Version 4）位址長度為 32 個位元（bits），邏輯上劃分為 4 個位元組（Octets / Bytes），每個位元組由 8 個位元組成。
• 點分十進位表示法（Dotted-Decimal Notation）：將 4 個位元組分別轉換為 0～255 的無號十進位整數，各組間以英文句點「.」相隔。
• 十六進位表示法（Hexadecimal Notation）：在封包側錄軟體（如 Wireshark、tcpdump）中，封包標頭（Packet Header）常以十六進位位元組形式呈現。每 4 個二進位位元（Nibble）對應 1 個十六進位數值（$0\sim 9$、$A\sim F$），每個位元組以 2 位十六進位數表示。

2. 子網路遮罩與網路劃分：

• IPv4 位址由**網路編號（Network ID）與主機編號（Host ID）**組成。
• 子網路遮罩（Subnet Mask）：由一串連續的「$1$」緊接著一串連續的「$0$」組成，長度同樣為 32 位元。其中為「$1$」的位元遮蔽出 Network ID 的長度（即 CIDR 前綴長度 Prefix Length），為「$0$」的位元則對應 Host ID。
• 子網路廣播位址（Subnet Broadcast Address）：用來向該子網路內的所有主機發送廣播封包的特定保留位址。其規則為「保留 Network ID 不變，將該子網路內的所有 Host ID 位元全部設為 $1$」。

解題方法與推導過程

題目給定 32 位元二進位位址： $10100011\ 00011001\ 00010001\ 00011110$

（一）十進位位址表示推導

將 32 個位元分為 4 個位元組，依二進位權重值（$128, 64, 32, 16, 8, 4, 2, 1$）分別轉為十進位：

1. 第 1 位元組：$10100011_2$ $1 \times 2^7 + 0 \times 2^6 + 1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 128 + 32 + 2 + 1 = 163$
2. 第 2 位元組：$00011001_2$ $0 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 16 + 8 + 1 = 25$
3. 第 3 位元組：$00010001_2$ $0 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 16 + 1 = 17$
4. 第 4 位元組：$00011110_2$ $0 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 16 + 8 + 4 + 2 = 30$

將各區段以句點連接，得到點分十進位位址為 $163.25.17.30$。

（二）封包側錄軟體上的十六進位表示推導

封包側錄軟體（如 Wireshark Hex Dump 視窗）會將每個位元組拆解為高 4 位元與低 4 位元轉為十六進位符號：

1. 第 1 位元組：$1010\ 0011_2$

• 高 4 位元：$1010_2 = 10_{10} = \text{A}_{16}$
• 低 4 位元：$0011_2 = 3_{10} = 3_{16}$
• 組合：$\text{A3}_{16}$

2. 第 2 位元組：$0001\ 1001_2$

• 高 4 位元：$0001_2 = 1_{10} = 1_{16}$
• 低 4 位元：$1001_2 = 9_{10} = 9_{16}$
• 組合：$19_{16}$

3. 第 3 位元組：$0001\ 0001_2$

• 高 4 位元：$0001_2 = 1_{10} = 1_{16}$
• 低 4 位元：$0001_2 = 1_{10} = 1_{16}$
• 組合：$11_{16}$

核心觀念

本題評量二元樹（Binary Tree）的遞迴走訪（Recursive Traversal）與結構性質，涵蓋下列關鍵知識點：

1. 二元樹的遞迴定義與分治法（Divide and Conquer）：

• 二元樹為空樹（NULL），或由一個根節點（Root）加上左子樹（Left Subtree）與右子樹（Right Subtree）所構成。
• 計算整棵樹的節點數時，基本情況（Base Case）為空樹（節點數為 $0$）；遞迴情況（Recursive Case）為「當前節點（計為 $1$）$+$ 左子樹節點數 $+$ 右子樹節點數」。

2. 二元樹的空指標定理（Null Pointer Property）：

• 含有 $n$ 個節點的二元樹，每個節點皆有 2 個子節點指標（left 與 right），共有 $2n$ 個指標欄位。
• 除根節點外，每個節點皆恰有一條來自父節點的邊指向它，故非空指標數為 $n - 1$。
• 空指標（NULL）的總數恆為 $2n - (n - 1) = n + 1$。

解題方法

（一）程式片段填空分析

• 程式片段（a）：

• 條件為 if (ptr == NULL)，代表當前指標指向空子樹（Base Case）。
• 空子樹中沒有任何節點，應回傳節點數 $0$。
• 故（a）填入：0。

• 程式片段（b）：

• 當 ptr != NULL 時，當前節點本身計為 $1$ 個節點，並須遞迴計算左子樹與右子樹的節點總數。
• 呼叫 size(ptr->left) 取得左子樹節點數，呼叫 size(ptr->right) 取得右子樹節點數。
• 兩子樹之節點數相加後再加上當前節點 $1$：1 + size(ptr->left) + size(ptr->right)（或 size(ptr->left) + size(ptr->right) + 1）。
• 故（b）填入：1 + size(ptr->left) + size(ptr->right)。

（二）函式 size 總呼叫次數

若二元樹共有 $n$ 個節點（$n \ge 0$），函式 size 總共會被呼叫 $2n + 1$ 次。

（三）呼叫次數推導與計算說明

計算函式被呼叫的總次數，可由以下兩種嚴謹方法推導：

方法一：指標與節點分類計算法（幾何/圖論法）

函式 size(ptr) 的每一次呼叫，依傳入的指標是否為空，可分為兩大類：

1. 有效節點的呼叫（ptr != NULL）：

• 包含主程式傳入根節點的第 1 次呼叫，以及遞迴走訪到二元樹中其餘 $n - 1$ 個節點的呼叫。
• 樹中每個真實存在的節點都會作為參數傳入函式 size 恰好 1 次，因此非空呼叫次數共為 $n$ 次。

2. 空節點的呼叫（ptr == NULL，觸發 Base Case）：

• 樹中每個節點皆配置 2 個指標欄位（left 與 right），$n$ 個節點總計有 $2n$ 個指標欄位。
• 二元樹中除了根節點之外，其餘 $n - 1$ 個節點皆由某個節點的指標所指向，即非空指標有 $n - 1$ 個。
• 其餘未指向任何實體節點的空指標（NULL）數量為： $2n - (n - 1) = n + 1$
• 每個空指標在進入遞迴時，皆會觸發 1 次 size(NULL) 呼叫（隨即因條件成立回傳 $0$），因此空指標引發的呼叫次數共為 $n + 1$ 次。

將上述兩者相加，可得總呼叫次數： $\text{總呼叫次數} = n + (n + 1) = 2n + 1$

核心觀念

• 二元搜尋樹（binary search tree, BST）的每個節點，其左子樹資料小於節點資料，右子樹資料大於節點資料。
• 後序走訪（post-order）依「左子樹、右子樹、根節點」的順序走訪。
• 中序走訪（in-order）依「左子樹、根節點、右子樹」的順序走訪。
• 插入新資料時，從根節點開始比較，依 BST 的大小規則往左或往右，直到找到空位置。

解題方法與推導

原樹如下：

 25
 / \
 7 32
 / \ / \
 2 19 26 56

（一）後序走訪

先走訪根節點 25 的左子樹：先走訪 7 的左子節點 2，再走訪右子節點 19，最後走訪 7，得到 $2, 19, 7$。

再走訪右子樹：先走訪 32 的左子節點 26，再走訪右子節點 56，最後走訪 32，得到 $26, 56, 32$。

最後走訪根節點 25，故後序順序為：

（二）依序插入 15、17

插入 15：$15<25$，往左至 7；$15>7$，往右至 19；$15<19$，因此插入 19 的左子節點。

插入 17：從根節點依序比較，$17<25$、$17>7$、$17<19$、$17>15$，因此插入 15 的右子節點。