108 地方特考三等 電子工程 計算機概論 考古題詳解

核心觀念

1. $n$ 位元 2 的補數（Two's Complement）表示範圍：

• 符號位元（MSB）為 0 代表正數或零，為 1 代表負數。
• $n$ 個位元可表示的整數範圍公式為： $-2^{n-1} \sim +(2^{n-1} - 1)$

2. 2 的補數加法運算與解讀：

• 加法直接按一般二進位加法進行，若最高位產生進位（Carry out）則直接捨棄。
• 運算結果若最高位為 0，其值即為一般的二進位正整數；若最高位為 1，其十進位真值為其負權重與其餘位元權重之和，亦即值為 $-(\text{取反加 1})$。

3. 加法溢位（Overflow）判斷：

• 當兩同號數相加，結果符號與運算元不同時，即發生溢位（如：正數 $+$ 正數 $=$ 負數）。
• 發生溢位時，暫存器所得之數值將無法正確反映真實數學加總值。

---

解題方法

1. 求 4 位元可表示之整數範圍

代入 $n = 4$ 至 2 的補數整數範圍公式： $\text{最小值} = -2^{4-1} = -2^3 = -8 \quad (1000_2)$ $\text{最大值} = 2^{4-1} - 1 = 2^3 - 1 = +7 \quad (0111_2)$ 因此，可表示的整數範圍為 $-8 \sim +7$。

2. 計算 $0100 + 1101$ 之十進位值

• 各項對應十進位值分析：

• $0100_2$：最高位為 0，為正數，十進位值為 $+4$。
• $1101_2$：最高位為 1，為負數。 依 2 的補數求值：$1101_2 = -2^3 + 2^2 + 0 + 2^0 = -8 + 4 + 1 = -3$。

• 二進位加法計算：

& 0100_2 \\ + & 1101_2 \\ \hline (1) & 0001_2 \end{array}$$ * **結果解讀**： 最高位向外產生的進位 $(1)$ 依 2 的補數規則直接捨棄，4 位元暫存器內容為 $0001_2$。 - 符號位元為 0（正數），$0001_2$ 對應的十進位值為 **$+1$**。 - 驗算：$(+4) + (-3) = +1$，無溢位，結果正確。 ##### 3. 計算 $0100 + 0101$ 之十進位值 * **各項對應十進位值分析**： - $0100_2$：十進位值為 $+4$。 - $0101_2$：十進位值為 $+5$。 * **二進位加法計算**： $$\begin{array}{r@{\quad}l} & 0100_2 \\ + & 0101_2 \\ \hline & 1001_2 \end{array}$$ * **溢位與結果解讀**： - **數學真值**：$(+4) + (+5) = +9$。 - **溢位分析**：4 位元 2 的補數最大僅能表示至 $+7$，兩正數相加卻得到符號位為 1（負數）的結果 $1001_2$，故**發生算術溢位（Overflow）**。 - **硬體暫存器存儲之數值**：4 位元暫存器儲存之結果為 $1001_2$。若將此 4 位元暫存器內容依 2 的補數格式解讀，其十進位值為： $$-2^3 + 2^0 = -8 + 1 = -7$$ --- #### **解題技巧與常見陷阱** * **進位（Carry）與溢位（Overflow）之區分**： - 運算 $0100 + 1101$ 產生了最高位進位（Carry out = 1），但一正一負相加絕對不會溢位，進位捨棄後答案仍完全正確。 - 運算 $0100 + 0101$ 沒有產生最高位進位（Carry out = 0），但因兩正數相加變負數，產生了「算術溢位」。 * **作答策略**： 針對 $0100 + 0101$，閱卷標準可能採「實際計算之數學值（$+9$）」或「4 位元暫存器依 2 的補數解讀之值（$-7$）」，因此在作答時應同時說明「數學真實值為 $+9$，但因溢位，4 位元暫存器內的二進位碼 $1001_2$ 對應之十進位值為 $-7$」，方可確保取得滿分。 --- ### 第（二）小題 #### **核心觀念** 1. **位元相等比較**： - XOR（互斥或，$\oplus$）閘的特性為「兩輸入相同時輸出 0，不同時輸出 1」： $$A_i \oplus B_i = \begin{cases} 0, & \text{若 } A_i = B_i \\ 1, & \text{若 } A_i \neq B_i \end{cases}$$ 2. **多位元比較器邏輯合成**： - 兩個四位元向量 $A = A_3A_2A_1A_0$ 與 $B = B_3B_2B_1B_0$ 相等（$A=B$），充要條件為每一位元皆相等，即： $$A_3 = B_3 \text{ 且 } A_2 = B_2 \text{ 且 } A_1 = B_1 \text{ 且 } A_0 = B_0$$ - 換言之，只要有**任一位元不同**，$A$ 與 $B$ 即不相等。

核心觀念

本題考查計算機網路 TCP/IP 體系中傳輸層（Transport Layer）​兩大核心協定——TCP（Transmission Control Protocol，傳輸控制協定）​與 UDP（User Datagram Protocol，用戶資料報協定）​的根本差異，以及 TCP 實現可靠資料傳輸（Reliable Data Transfer, RDT）​的底層協同設計機制。

可靠傳輸的核心定義在於：確保應用層所接收到的資料流具備無差錯（Error-Free）、不遺失（Loss-Free）、不重複（Duplicate-Free）​且依序到達（In-Order Delivery）​之保證。

---

解題方法

本題為申論題，切入點應先明確判定何者具備可靠傳輸能力，隨後將 TCP 實現可靠傳輸的設計機制依​「錯誤偵測 $\to$ 連線維護 $\to$ 序號與確認 $\to$ 遺失重傳 $\to$ 流量與壅塞協調」​之邏輯架構分項深入論述。

一、判定結論

在傳輸層的 TCP 與 UDP 中，TCP 可以提供可靠的傳輸；UDP 則屬於非連線導向（Connectionless）、無可靠性保證、僅提供「最佳努力傳送（Best-Effort Delivery）」之協定。

二、TCP 對應的可靠傳輸設計機制

TCP 透過下列六大機制的整合運作，保證在不可靠的 IP 網路環境上實現端對端的可靠傳輸：

1. 錯誤偵測（Checksum，檢驗和）

• 機制：TCP 標頭中包含 $16\text{-bit}$ 的檢驗和欄位，計算範圍涵蓋 TCP 偽標頭（Pseudo Header）、TCP 標頭及資料負載。
• 功用：接收端計算檢驗和以檢查封包在傳輸過程中是否發生位元錯誤（Bit Inversion）。若檢驗不符，接收端直接丟棄該損毀區段（Segment），依賴後續重傳機制修復。

2. 連線管理（Connection Management）

• 機制：採用三方交握（Three-Way Handshake）​建立連線，以及四方揮手（Four-Way Wavehandshake）​釋放連線。
• 功用：確保通訊雙方在資料傳輸前皆已分配好緩衝區資源，並同步雙方的初始序號（Initial Sequence Number, ISN），避免因網路延遲的舊連線封包造成傳輸錯亂。

3. 序號與累積確認應答（Sequence Number & Cumulative ACK）

• 序號（Sequence Number）：TCP 將傳輸的位元組（Byte）資料進行連續編號。接收端根據序號將亂序到達（Out-of-Order）的封包重新按正確順序組合，並自動過濾丟棄重複的封包。
• 累積確認（Cumulative Acknowledgment, ACK）：接收端回傳的確認號（Acknowledgment Number）代表「期望收到的下一個位元組序號」，表示該序號之前的所有資料均已正確無誤地接收。

4. 逾時重傳與快速重傳（Retransmission Mechanism / ARQ）

• 逾時重傳（Timeout Retransmission）：發送端送出區段後即啟動重傳計時器（Retransmission Timer）。若超過依據動態往返時間（RTT）計算出的逾時重傳時間（Retransmission Timeout, RTO）仍未收到 ACK，則判定該區段遺失並自動重傳。

核心觀念

本題評量「資訊安全與密碼學」之核心基礎，主要涵蓋以下定義與原理：

1. 對稱加密法（Symmetric Encryption）：又稱「秘密金鑰加密（Secret-Key Cryptography）」。通訊雙方使用同一把秘密金鑰進行加密與解密。設明文為 $M$、密文為 $C$、金鑰為 $K$： $C = E_K(M), \quad M = D_K(C)$ 若有 $n$ 位通訊者彼此需建立安全通道，系統總共需要的金鑰數量為組合數： $C^n_2 = \frac{n(n-1)}{2}$
2. 非對稱加密法（Asymmetric Encryption）：又稱「公開金鑰加密（Public-Key Cryptography）」。以數論單向陷門函數（Trapdoor One-way Function）為數學基礎，每位使用者擁有一對數學相關的成對金鑰：公開金鑰（Public Key, $PK$）與私密金鑰（Private Key, $SK$）。若有 $n$ 位使用者，全系統僅需 $2n$ 把金鑰。
3. 資訊安全三大要素（CIA）與不可否認性（Non-repudiation）：對稱加密主要提供機密性（Confidentiality）；非對稱加密除機密性外，搭配私鑰簽名亦能提供身分鑑別（Authentication）、完整性（Integrity）與不可否認性。

---

解題方法

本題為國家考試三等申論題，作答應採取「定義原理 $\to$ 運作架構 $\to$ 優缺點 $\to$ 代表演算法 $\to$ 兩者對照與混合應用」之層次展開：

1. 結構切入：分別詳述對稱與非對稱加密的運作原理與金鑰機制，並給出數學表示式。
2. 對比分析：以表格綜合比較「金鑰數量」、「計算效能」、「金鑰配送（Key Distribution）」與「安全服務功能」。
3. 實務延伸：補充現代網路通訊協定（如 SSL/TLS、HTTPS）如何結合兩者長處之「混合加密法（Hybrid Encryption）」，展現高分應考實力。

---

選項分析

本題為申論申述題，非選擇題，無選項可逐一分析。評分標準之重點檢核指標如下：

1. 對稱加密論述：是否清楚說明「加解密同金鑰」、運算速度快、金鑰數量為 $O(n^2)$、存在金鑰配送安全瓶頸，並列舉 AES、DES 等標準。
2. 非對稱加密論述：是否釐清「公鑰公開、私鑰保密」、區分「公鑰加密（保密）」與「私鑰加密（簽章）」兩種模式，並列舉 RSA、ECC 等演算法。
3. 優劣比較與整合：是否指出非對稱加密解決了金鑰分發問題，但運算複雜耗時，因此實務上多採混合式架構。

---

解題技巧

1. 記憶口訣：

• 「對稱同把快，配送是阻礙」：加解密同一把，運算快適合大檔，但兩兩傳輸需 $\frac{n(n-1)}{2}$ 把金鑰，安全傳送金鑰極為困難。
• 「非對稱配對慢，公加私解防偷看，私加公解做簽章」：金鑰成對，數學計算複雜耗能，公鑰加密保證機密性，私鑰加密（簽章）保證不可否認性。

2. 常見陷阱與扣分點：

• 混淆公私鑰用途：切勿寫出「傳送方用自己的公鑰加密給對方」等錯誤觀念。傳送機密訊息時，必須使用「接收方的公鑰」加密，接收方才能用自己的「私鑰」解密。
• 忽略金鑰數量複雜度：提及 $n$ 位使用者時，務必精準列出 $\frac{n(n-1)}{2}$ 與 $2n$，此為閱卷老師核定給分關鍵。

---

【答案】

一、對稱加密法（Symmetric Encryption）

1. 運作原理： 對稱加密法又稱為「傳統加密法」或「私鑰加密法」。資料傳送方與接收方在通訊前必須事先約定並共享同一把秘密金鑰（Secret Key, $K$）。傳送方使用該金鑰將明文（Plaintext, $M$）透過加密演算法轉為密文（Ciphertext, $C$），接收方收到密文後，利用完全相同的金鑰與解密演算法還原出明文： $C = E_K(M), \quad M = D_K(C)$
2. 特點與優缺點：

• 優點：演算法架構多採用代換（Substitution）與置換（Permutation）等算術邏輯運算，加解密速度快、硬體實現成本低、運算資源消耗少，非常適合大量資料（Bulk Data）的即時加密。

核心觀念

本題評量資料結構中「堆疊」（Stack）的陣列實作與 C 語言指標／結構（struct）之基礎語法操作。核心要點如下：

1. 堆疊運作原則： 堆疊為具有「後進先出」（LIFO, Last-In-First-Out）特性的線性資料結構。所有插入（push）與刪除（pop）操作皆限制於頂端（Top）進行。
2. 頂端索引（top）的語意慣例：

• 慣例 A（指向頂端元素）：空堆疊時 $\text{top} = -1$；push 先移動指標再存資料；pop 先取資料再移動指標。
• 慣例 B（指向下一個可用空位／即堆疊內元素個數）：空堆疊時 $\text{top} = 0$；push 先存資料再移動指標；pop 先移動指標再取資料。 本題題幹於 create_stack 中設定 stack->top = 0，且嚴格規定 push 與 pop 之操作先後順序，即採慣例 B。

3. C 語言傳址呼叫（Call by Pointer）：

• 堆疊物件以指標傳入（STACK_TYPE *stack），存取成員須使用箭頭運算子 ->。
• pop 函式透過輸出參數（Output Parameter）ITEM_TYPE *old_item 將彈出的資料傳回呼叫端，指派時必須使用反參考運算子（Dereference Operator）*old_item。

---

解題方法

題目已明確指出「在不考慮堆疊滿（Full）及空（Empty）的條件下」，因此程式碼無需撰寫陣列溢位（Overflow）或不足額（Underflow）的邊界檢查（if 條件式），直截了當地依照題目規定的步驟撰寫即可：

1. push 函式邏輯

題目要求：「先輸入新資料後，再移動指標」

• 步驟一（輸入新資料）：將 new_item 寫入目前 top 所指的位置，即 stack->items[stack->top] = new_item;。
• 步驟二（移動指標）：將頂端索引向後推進 1 格，即 stack->top++;。 (亦可合併寫為 stack->items[stack->top++] = new_item;，但分開撰寫邏輯最為分明，不易被扣分)

2. pop 函式邏輯

題目要求：「先移動指標後，再取出資料」

• 步驟一（移動指標）：將頂端索引往前倒退 1 格，即 stack->top--;。

核心觀念

1. 二元搜尋樹（Binary Search Tree, BST）之定義與性質： 對於樹中任意節點 $N$，其左子樹（Left Subtree）中所有節點的資料值均小於 $N$ 的資料值；其右子樹（Right Subtree）中所有節點的資料值均大於 $N$ 的資料值，且其左、右子樹各自亦為一棵二元搜尋樹。
2. 中序走訪（Inorder Traversal）： 走訪二元樹的順序為「走訪左子樹 $\to$ 處理根節點 $\to$ 走訪右子樹」（Left-Root-Right, LDR）。由於 BST 左小右大的幾何特性，對 BST 進行中序走訪所輸出的鍵值序列，恰好為嚴格由小至大的遞增序列（Ascending Order）。
3. 遞迴演算法（Recursion）結構： 樹狀結構具有自相似性，走訪通常採用遞迴實作。必須具備基準條件（Base Case，即節點指標為 NULL 時返回）以及遞迴推進步驟（走訪左子節點、輸出當前節點資料、走訪右子節點）。

---

解題方法

一、依序建立二元搜尋樹之步驟

依給定數列逐筆將數值插入樹中（小於當前節點往左、大於當前節點往右）：

1. 插入 40：樹為空，40 作為根節點（Root）。
2. 插入 25：$25 < 40$，置於 40 的左子節點。
3. 插入 35：$35 < 40$（往左）；$35 > 25$（往右），置於 25 的右子節點。
4. 插入 60：$60 > 40$，置於 40 的右子節點。
5. 插入 63：$63 > 40$（往右）；$63 > 60$（往右），置於 60 的右子節點。
6. 插入 55：$55 > 40$（往右）；$55 < 60$（往左），置於 60 的左子節點。
7. 插入 18：$18 < 40$（往左）；$18 < 25$（往左），置於 25 的左子節點。
8. 插入 76：$76 > 40$（往右）；$76 > 60$（往右）；$76 > 63$（往右），置於 63 的右子節點。

二、由小至大排序的方法說明

利用中序走訪（Inorder Traversal）​依序拜訪該二元搜尋樹的所有節點：