111 民航特考三等 航空通信 計算機概論 考古題詳解

（一）五位數的十進制與八進制最大值

核心觀念

在正整數的 $n$ 位數表示法中，若基底為 $b$，每一位可使用的最大數字為 $b-1$，因此最大值為：

$$b^n-1$$

解題方法

1. 五位數十進制

十進制的基底為 $10$，每位最大數字為 $9$：

$$10^5-1=100000-1=99999$$

所以五位數十進制的最大數為：

$$\boxed{99999}$$

2. 五位數八進制

八進制的基底為 $8$，每位最大數字為 $7$：

$$8^5-1=32768-1=32767$$

以八進制表示時，直接寫成五個最大位元：

$$\boxed{77777_8}$$

其十進制數值為：

$$77777_8=7(8^4)+7(8^3)+7(8^2)+7(8)+7=32767_{10}$$

解題技巧

判斷基底為 $b$、位數為 $n$ 時，直接套用：

$$\text{最大值}=b^n-1$$

八進制每一位只能使用 $0$ 至 $7$，不可出現數字 $8$ 或 $9$。

---

（二）十進制轉二進制

核心觀念

整數部分使用「除 $2$ 取餘數」法；小數部分使用「乘 $2$ 取整數位」法。

1. $17.1875$ 轉為二進制

整數部分

$$17\div 2=8\quad\text{餘 }1$$ $$8\div 2=4\quad\text{餘 }0$$ $$4\div 2=2\quad\text{餘 }0$$ $$2\div 2=1\quad\text{餘 }0$$ $$1\div 2=0\quad\text{餘 }1$$

由下往上讀取餘數：

$$17_{10}=10001_2$$

小數部分

$$0.1875\times2=0.375$$

取整數位 $0$。

$$0.375\times2=0.75$$

取整數位 $0$。

$$0.75\times2=1.5$$

取整數位 $1$。

$$0.5\times2=1.0$$

取整數位 $1$，小數部分歸零。

因此：

$$0.1875_{10}=0.0011_2$$

合併整數與小數部分：

$$\boxed{17.1875_{10}=10001.0011_2}$$

---

2. $49.40625$ 轉為二進制

整數部分

$$49\div2=24\quad\text{餘 }1$$ $$24\div2=12\quad\text{餘 }0$$ $$12\div2=6\quad\text{餘 }0$$ $$6\div2=3\quad\text{餘 }0$$ $$3\div2=1\quad\text{餘 }1$$ $$1\div2=0\quad\text{餘 }1$$

由下往上讀取：

$$49_{10}=110001_2$$

小數部分

$$0.40625\times2=0.8125$$

取整數位 $0$。

$$0.8125\times2=1.625$$

取整數位 $1$。

$$0.625\times2=1.25$$

取整數位 $1$。

$$0.25\times2=0.5$$

取整數位 $0$。

$$0.5\times2=1.0$$

取整數位 $1$。

因此：

$$0.40625_{10}=0.01101_2$$

合併後：

$$\boxed{49.40625_{10}=110001.01101_2}$$

解題技巧

小數部分可先換成分數：

$$0.1875=\frac{3}{16}=\frac{3}{2^4}=0.0011_2$$ $$0.40625=\frac{13}{32}=\frac{13}{2^5}=0.01101_2$$

驗算時可將二進制小數位依序乘上：

$$2^{-1},2^{-2},2^{-3},\ldots$$

例如：

$$0.01101_2 =0\cdot2^{-1}+1\cdot2^{-2}+1\cdot2^{-3}+0\cdot2^{-4}+1\cdot2^{-5}$$ $$=\frac14+\frac18+\frac1{32} =\frac{13}{32} =0.40625$$

---

（一）TCP/IP 各層資料單位

核心觀念

TCP/IP 協定套件在不同網路層級，資料單位名稱不同：

• 應用層：訊息（message）
• 傳輸層：區段（segment，TCP）或資料報（datagram，UDP）
• 網路層：封包（packet），亦可稱 IP 資料報（IP datagram）
• 資料鏈結層：訊框（frame）

解題方法

題目已知應用層資料單位為 message，只需依序判斷網路層與資料鏈結層的資料封裝名稱。

應用層的訊息向下傳遞時，經過網路層會封裝成 IP 封包；再向下經過資料鏈結層時，會加上資料鏈結層標頭與尾端資訊，形成訊框。

解題技巧

記憶順序可寫成：

$$\text{Message} \rightarrow \text{Segment} \rightarrow \text{Packet} \rightarrow \text{Frame}$$

本題未詢問傳輸層，因此只需回答：

• 網路層：封包（packet／IP datagram）
• 資料鏈結層：訊框（frame）

---

（二）固定分區配置與記憶體浪費

核心觀念

本題考固定分區（fixed partitioning）配置與內部碎裂（internal fragmentation）。

固定分區中，每個程式必須配置到一個完整分區。程式實際需要的記憶體小於分區大小時，剩餘空間無法再配置給其他程式，稱為內部碎裂，也就是浪費的記憶體。

解題方法

各程式的配置情形如下：

程式	所需記憶體	使用分區	分區大小	浪費記憶體
第一個	$17$ MB	第三分區	$18$ MB	$18-17=1$ MB
第二個	$8$ MB	第一分區	$10$ MB	$10-8=2$ MB
第三個	$11$ MB	第二分區	$12$ MB	$12-11=1$ MB
第四個	$20$ MB	第四分區	$20$ MB	$20-20=0$ MB
第五個	$39$ MB	第五分區	$40$ MB	$40-39=1$ MB

五個程式實際使用的記憶體總量為：

$$17+8+11+20+39=95\text{ MB}$$

五個分區總容量為：

$$10+12+18+20+40=100\text{ MB}$$

因此，內部浪費的記憶體為：

$$100-95=5\text{ MB}$$

浪費記憶體百分比以總可用記憶體 $100$ MB 為分母：

$$\frac{5}{100}\times 100\%=5\%$$

解題技巧

每個分區的浪費量直接使用：

$$\text{浪費量}=\text{分區大小}-\text{程式需求量}$$

快速驗算：

$$1+2+1+0+1=5\text{ MB}$$

由於所有分區均已配置，總分區容量為 $100$ MB；程式實際需求總量為 $95$ MB，兩者差額即為浪費量。

---

（三）死鎖的必要條件

核心觀念

死鎖（deadlock）成立必須同時具備四個必要條件：

1. Mutual exclusion（互斥）
2. Resource holding／Hold and wait（持有並等待）
3. No preemption（不可剝奪）
4. Circular wait（循環等待）

題目要求說明前兩項。

1. Mutual exclusion（互斥）

第三題（一）

核心觀念

本小題考查雙層 for 迴圈的執行順序，以及變數 y 在迴圈中的累加變化。

外層迴圈控制 $i=1$ 到 $4$；內層迴圈執行條件為 $j<i$，因此每一列會執行 $i-1$ 次。

解題方法

逐次列出各次外層迴圈：

$i$	內層迴圈執行次數	輸出內容	執行後的 $y$
1	0	空白列	2
2	1	2	3
3	2	34	5
4	3	567	8

內層迴圈每執行一次便印出目前的 y，再執行 y++。每次外層迴圈結束後，printf("\n") 換行。

解題技巧

第一列內層迴圈完全不執行，因此輸出結果的第一行是空白行。數字不以空格分隔，必須按照連續字元判讀。

【答案】

2
34
567

---

第三題（二）

核心觀念

儲存類別指示器（storage-class specifiers）用來描述變數或函式的儲存期間、連結性及作用範圍。

依照命題當年（民國 111 年）C 程式設計常用分類，除了 auto 外，另外三個是：

1. register
2. static
3. extern

解題方法

• auto：區域變數的預設儲存類別，儲存期間通常為所在區塊執行期間。
• register：建議編譯器將變數配置於暫存器中，以提升存取效率；不能對其使用取址運算子 &。
• static：使變數具有靜態儲存期間。區域 static 變數離開函式後仍保留其值；檔案層級的 static 則限制連結範圍於該原始檔案。
• extern：宣告變數或函式定義在其他位置，主要用於跨檔案共用外部名稱。

解題技巧

題目明確要求「除了 auto 外的三個」，依傳統 C 課本與考試分類直接回答：

$$\boxed{\texttt{register、static、extern}}$$

【答案】

register、static、extern。

---

第三題（三）

核心觀念

本小題考查遞迴函式。函式 f1(x,y) 的定義為：

$$f1(x,y)= \begin{cases} x, & y=2\\ x+f1(x,y-1), & y\ne 2 \end{cases}$$

當 $y$ 大於 $2$ 時，每一層遞迴都加上一次 $x$，直到 $y=2$ 才停止。

解題方法

輸入：

$$x=87,\qquad y=6$$

依函式定義展開：

（一）用一個陣列實現兩個堆疊

核心觀念

堆疊（stack）遵守後進先出（LIFO, Last In First Out）。利用同一個長度為 $n$ 的陣列，可讓兩個堆疊分別由陣列兩端向中央成長，以共享未使用的空間。

解題方法

設陣列為 $A[0 \dots n-1]$：

• 堆疊一（Stack 1）由左向右成長。
• 堆疊二（Stack 2）由右向左成長。
• 設 top1 = -1，表示 Stack 1 為空。
• 設 top2 = n，表示 Stack 2 為空。

配置方式如下：

$$\text{Stack 1} \quad \longrightarrow \quad [\text{未使用空間}] \quad \longleftarrow \quad \text{Stack 2}$$

基本操作：

• Stack 1 push：先令 top1 = top1 + 1，再將資料存入 $A[top1]$。
• Stack 1 pop：取出 $A[top1]$，再令 `top1 = top1 - 1$。
• Stack 2 push：先令 `top2 = top2 - 1$，再將資料存入$A[top2]$。
• Stack 2 pop：取出 $A[top2]$，再令 `top2 = top2 + 1$。

兩個堆疊共用陣列，因此陣列滿載的條件為：

$$top1+1=top2$$

此時兩個堆疊之間已無剩餘空間。

解題技巧

此方法的優點是兩個堆疊可彈性分享空間。若兩個堆疊各自固定分配半數陣列，容易造成一邊已滿、另一邊仍有大量空間的浪費。

【答案】

使用同一陣列，讓 Stack 1 從索引 $0$ 向右成長，Stack 2 從索引 $n-1$ 向左成長；當 $top1+1=top2$ 時表示陣列已滿。

---

（二）由中序與前序追蹤畫出二元樹

核心觀念

二元樹追蹤規則如下：

• 前序（preorder）：根、左子樹、右子樹，即 Root-Left-Right。
• 中序（inorder）：左子樹、根、右子樹，即 Left-Root-Right。

前序追蹤的第一個節點必定是整棵樹的根。

題目給定：

中序：

$$(a+(b*c))+(((d*e)+f)*g)$$

前序：

$$+ \quad + \quad a \quad * \quad b \quad c \quad * \quad + \quad * \quad d \quad e \quad f \quad g$$

解題方法

前序第一個符號為 $+$，因此整棵樹根節點為 $+$。

中序中，根節點 $+$ 將樹分成：

• 左子樹：$(a+(b*c))$
• 右子樹：$(((d*e)+f)*g)$

左子樹的前序為：

$$+ \quad a \quad * \quad b \quad c$$

因此左子樹根為 $+$，其左子節點為 $a$，右子樹為 $b*c$。

右子樹的前序為：

$$* \quad + \quad * \quad d \quad e \quad f \quad g$$

因此右子樹根為 $*$，其左子樹為 $(d*e)+f$，右子節點為 $g$。

二元樹如下：

 +
 / \
 + *
 / \ / \
 a * + g
 / \ / \
 b c * f
 / \
 d e

解題技巧

處理前序與中序時，先找前序第一個節點作為根，再到中序中定位該根，根的左邊即左子樹，右邊即右子樹。運算式中的括號也可用來快速確認子樹範圍。

【答案】

所求二元樹為：

 +
 / \
 + *
 / \ / \
 a * + g
 / \ / \
 b c * f
 / \
 d e

---

（三）建立二元搜尋樹

核心觀念

二元搜尋樹（Binary Search Tree, BST）符合：

• 左子樹所有節點值小於根節點。
• 右子樹所有節點值大於根節點。
• 插入資料時，從根節點開始逐層比較，直到找到空的位置。

題目插入順序為：

$$3,1,4,6,9,2,5,7$$

解題方法

依序插入：

1. $3$：成為根節點。
2. $1<3$：放在 $3$ 的左邊。
3. $4>3$：放在 $3$ 的右邊。
4. $6>3$ 且 $6>4$：放在 $4$ 的右邊。
5. $9>3,9>4,9>6$：放在 $6$ 的右邊。
6. $2<3$，但 $2>1$：放在 $1$ 的右邊。
7. $5>3,5>4$，但 $5<6$：放在 $6$ 的左邊。
8. $7>3,7>4,7>6$，但 $7<9$：放在 $9