109 鐵路特考高員三級 電力工程 計算機概論 考古題詳解
第 一 題25 分
LZW（Lempel-Ziv-Welch）編碼法是一種無損資料壓縮演算法。編碼是將資料的個別單一字元先建立成一個具有編號之字串編碼表。在隨後的編碼與解碼過程，字串編碼表會隨著逐漸擴大。
若一開始的字串編碼表如下所示：
碼 字串
1 A
2 B
3 C
使用 LZW 編碼法對下列訊息進行編碼，試問編碼後的結果為何？（25 分）
ABCABCABC
登入後即可作答並保存紀錄。
核心觀念
LZW 編碼會從初始字典中的字元開始，逐步把「字典中已存在的字串」延伸一個字元，加入新字典項目。
編碼時，每次找出目前尚未輸出的最長字典字串 ，輸出它的碼；若後面還有字元 ，就把 加入字典，再從 開始處理剩餘訊息。題目初始字典為：
| 碼 | 字串 |
|---|---|
| 1 | A |
| 2 | B |
| 3 | C |
因此新字串從碼 開始編號。
解題方法
依序掃描訊息 ABCABCABC，每次輸出目前最長的字典字串，並將該字串與下一個字元組合後加入字典：
| 步驟 | 尚未處理的訊息 | 輸出字串與碼 | 新增字典項目 |
|---|---|---|---|
| 1 | ABCABCABC | A → 1 | AB → 4 |
| 2 | BCABCABC | B → 2 | BC → 5 |
| 3 | CABCABC | C → 3 | CA → 6 |
| 4 | ABCABC | AB → 4 | ABC → 7 |
| 5 | CABC | CA → 6 | CAB → 8 |
| 6 | C | C → 3 | — |
逐步說明：
第 二 題25 分
在現行國際網路協定裡，軟體的部分可以被歸類到 4 個抽象的層中。這 4 個階層為應用層（application layer）、傳輸層（transport layer）、網路層（network layer）和鏈結層（link layer）。請回答下列問題。（每小題 5 分，共 25 分）
(一) TCP（transmission control protocol）是屬於哪一層的協定？
(二) TCP 提供流量控制（flow control）的服務，試論述此流量控制的功能為何？
(三) 安全殼協定（secure shell protocol）是屬於哪一層的協定？
(四) 載波偵聽多路存取（CSMA）是屬於哪一層的協定？
(五) 埠號（port number）存在於哪一層的協定？
登入後即可作答並保存紀錄。
核心觀念
本題考查網路協定的分層架構，以及各協定與功能所屬的層級。網路分層的重點是：應用程式透過應用層協定提供網路服務；傳輸層負責端點間的資料傳送；網路層負責跨網路的封包傳遞；鏈結層則處理同一鏈結上的傳送及媒體存取。
解題方法
判斷時先看協定負責的工作，再對應層級：
- 應用層：提供使用者或應用程式直接使用的網路服務。
- 傳輸層：提供端點到端點的傳輸服務，例如可靠傳輸、流量控制及埠號。
- 網路層：負責網路間的封包傳遞與路由。
- 鏈結層：處理相鄰節點間的傳送，以及共享媒體的存取方式。
各小題解析
（一）TCP 屬於傳輸層。
TCP（Transmission Control Protocol，傳輸控制協定）提供端點間的可靠資料傳輸，並處理排序、重傳、流量控制等工作，因此屬於傳輸層。
（二）TCP 流量控制的功能
流量控制用來協調傳送端與接收端的資料傳送速率，避免傳送端送出的資料超過接收端的處理能力或緩衝區容量，造成接收端緩衝區溢位或資料遺失。
TCP 主要利用接收視窗進行流量控制：接收端告知傳送端目前可接收的資料量，傳送端據此限制尚未獲確認的資料量。接收端可隨緩衝區使用情形調整視窗大小，使資料傳送速率配合接收能力。
（三）安全殼協定 SSH 屬於應用層。
第 三 題25 分
請詳細解釋下列 C 語言程式的執行過程， 執行後將會印出什麼訊息？（25 分）
#include<stdio.h>
int f(int *a1, int *a2){ return *a1=*a1**a2; }
int main(){ int x1=3, x2=2, x3=1; x3=f(&x1,&x2); printf("%d", (x2-x1)*x1/5); return 0; }
登入後即可作答並保存紀錄。
核心觀念
本題考查 C 語言的指標與間接取值、賦值運算式的回傳值、整數運算，以及運算子優先順序。
在函式中，a1、a2 是指標；*a1、*a2 分別代表指標所指向的整數。賦值運算式本身會回傳被指定的值，因此：
return *a1=*a1**a2;
依 C 語言運算子優先順序，可讀作：
return (*a1) = ((*a1) * (*a2));
其中相鄰的 ** 並不是單一運算子，而是兩個一元解參考運算子 *，中間再以乘法運算子 * 相乘。
解題方法
先追蹤函式呼叫對 x1、x2 的影響，再把函式回傳值指定給 x3，最後代入 printf 的算式。
初始狀態為：
呼叫：
x3=f(&x1,&x2);
傳入的是 x1、x2 的位址，因此函式內的 a1 指向 x1，a2 指向 x2。函式計算：
第 四 題25 分
下列 8 筆英文字母資料依讀入順序為：P、A、N、D、E、M、I、C。請回答下列問題：
(一)創建並畫出對應之二元搜尋樹（binary search tree）。（10 分）
(二)對所造出之樹進行中序遍歷（in-order traversal），所拜訪的節點依序為何？（10 分）
(三)在此樹尋找特定的字母時，最糟的情況需要幾次的搜尋動作？（5 分）
登入後即可作答並保存紀錄。
核心觀念
二元搜尋樹（binary search tree, BST）是一種二元樹，對每個節點而言：
- 左子樹中所有節點的值都小於該節點。
- 右子樹中所有節點的值都大於該節點。
本題按資料讀入順序逐一插入，依英文字母的字典順序比較大小。中序遍歷的順序為「左子樹、根節點、右子樹」；對 BST 進行中序遍歷，結果會按值由小到大排列。
解題方法
依序插入 P、A、N、D、E、M、I、C：
- P 為第一筆資料，設為根節點。
- A 小於 P，放在 P 的左子節點。
- N 小於 P、但大於 A，放在 A 的右子節點。
- D 小於 P、大於 A、小於 N，放在 N 的左子節點。
- E 小於 P、大於 A、小於 N、但大於 D，放在 D 的右子節點。
- M 小於 P、大於 A、大於 N，放在 N 的右子節點。
- I 小於 P、大於 A、小於 N、大於 D、大於 E，放在 E 的右子節點。
- C 小於 P、大於 A、小於 N、小於 D，放在 D 的左子節點。
因此，所建立的 BST 為：
P
/
A
\
N
/ \
D M
/ \
C E
\
I
中序遍歷
按照「左子樹 → 根節點 → 右子樹」依序拜訪：