109 年 國立清華大學資訊系統與應用研究所丙組《計算機概論》

此題考驗遞迴概念與對二進位轉換的理解。

核心觀念：將一個非負整數轉換為二進位，可以透過不斷除以 2 取餘數來達成。遞迴的應用在於將大問題分解為與原問題相似但規模較小的新問題。

(a) 遞迴完成程式碼：
要印出一個非負整數 N 的二進位表示，可以利用遞迴的特性。基本情況是當 N 為 0 或 1 時，直接印出 N。對於大於 1 的 N，我們可以先遞迴處理 N 除以 2 的結果（即 N/2），然後再印出 N 除以 2 的餘數（即 N%2）。這樣做可以保證較高位的二進位數字（來自 N/2 的遞迴呼叫）先被印出，而較低位的數字（N%2）後被印出，形成正確的二進位表示。

void D2B(int N) {
    if (N == 0 || N == 1) {
        print(N);
    } else {
        D2B(N / 2); // 遞迴處理 N 除以 2 的結果
        print(N % 2); // 印出 N 除以 2 的餘數
    }
}

此題考驗浮點數的二進位表示與誤差分析。

核心觀念：將十進位小數轉換為二進位小數，以及理解固定位元數的浮點數表示法（包含符號位、指數位、尾數位的結構、指數的偏差表示法）和截斷誤差。

(a) 十進位數 2.625 的二進位表示：
整數部分 2 的二進位是 10。
小數部分 0.625 的轉換方法是持續乘以 2，取整數部分：
0.625 * 2 = 1.25 (取 1)
0.25 * 2 = 0.5 (取 0)
0.5 * 2 = 1.0 (取 1)
所以，0.625 的二進位是 0.101。
將整數部分和小數部分合併，得到 2.625 的二進位表示為 10.101。
為了表示為科學記號形式（方便轉換成浮點數），我們將其寫成 $1.0101 \times 2^1$。

【答案】$10.101_2$ 或 $1.0101 \times 2^1$

(b) 8 位元浮點數表示法表示 2.625：
該表示法格式為：1 位元符號 (S)，4 位元指數 (E)，3 位元尾數 (M)。
總共 8 位元。
指數使用偏差 7 (bias 7)。

1. 符號位 (S)：2.625 是正數，所以符號位為 0。

2. 指數位 (E)：
   我們表示的數是 $1.0101 \times 2^1$。這裡的實際指數是 1。
   使用偏差 7 的表示法，實際指數 = 指數位的值 - 偏差。
   所以，指數位的值 = 實際指數 + 偏差 = 1 + 7 = 8。
   將 8 轉換為 4 位元的二進位：1000。

3. 尾數 (M)：
   標準化後的二進位科學記號是 $1.0101 \times 2^1$。
   尾數是指小數點後的位數。在這裡，是 0101。
   由於我們只有 3 位元來表示尾數，我們需要截斷或四捨五入。題目要求是「fixed-point number」，通常表示為小數點後固定位數。在 IEEE 754 標準中，隱含首位 1，但此處題目明確說「3 bits for mantissa」，且範例中沒有提到隱含 1，故我們直接取 0.101。
   若要表示 0.101，由於只有 3 位元，我們取前 3 位：010。

   將這三部分組合起來：
   S = 0
   E = 1000
   M = 010

核心觀念

本題考查：

• 真值表轉換為布林代數式
• 基本邏輯閘：AND、OR、NOT
• 布林函數的化簡與電路實作

設：

• $A$：Input1
• $B$：Input2
• $F$：Output

輸出為 $0$ 的情況只有：

$$A=0,\quad B=1$$

其餘三種輸入組合的輸出皆為 $1$。

解題方法

觀察輸出為 $1$ 的條件：

1. 當 $A=1$ 時，不論 $B$ 為何，輸出皆為 $1$。
2. 當 $B=0$ 時，不論 $A$ 為何，輸出皆為 $1$。

因此，輸出為 $1$ 的條件可表示為：

$$F=A+\overline{B}$$

其中：

• $+$ 表示 OR
• $\overline{B}$ 表示 NOT $B$

逐列驗證

$A$	$B$	$\overline{B}$	$F=A+\overline{B}$	題目輸出
0	0	1	$0+1=1$	1
0	1	0	$0+0=0$	0
1	0	1	$1+1=1$	1
1	1	0	$1+0=1$	1

完全符合題目給定的真值表。

電路設計

電路只需要兩個邏輯閘：

此題考驗對二分搜尋法 (Binary Search) 和循序搜尋法 (Sequential Search) 的比較與應用情境的理解。

核心觀念：二分搜尋法要求資料必須排序，其效率在於每次排除一半的搜尋空間；循序搜尋法不要求排序，但效率較低。

(a) 未排序序列，何時二分搜尋（需先排序）比循序搜尋快？
二分搜尋法要求資料必須是已排序的。因此，若要對未排序的序列使用二分搜尋，必須先進行排序。排序的過程本身就有時間成本。

• 排序成本：常見的排序演算法（如合併排序、快速排序）平均時間複雜度為 $O(N \log N)$。
• 搜尋成本：二分搜尋的時間複雜度為 $O(\log N)$。
• 循序搜尋成本：平均時間複雜度為 $O(N)$。

因此，在未排序序列上，若要使用二分搜尋，總時間成本約為 $O(N \log N) + O(\log N)$。
若使用循序搜尋，總時間成本約為 $O(N)$。

二分搜尋（加上排序）會比循序搜尋快，通常發生在：

1. 搜尋次數非常多：如果同一個序列需要進行大量的搜尋操作，那麼排序一次的成本（$O(N \log N)$）就被多次搜尋的 $O(\log N)$ 所攤銷。當搜尋次數 $k$ 夠大，使得 $O(N \log N) + k \times O(\log N) < k \times O(N)$ 時，二分搜尋就更具優勢。
2. 序列非常大：對於極大的序列，雖然排序成本高，但 $O(\log N)$ 的搜尋速度優勢會非常明顯，尤其是在多次搜尋的情況下。
3. 序列相對穩定，不常變動：如果序列的元素不會頻繁增減，那麼進行一次排序後，後續的多次搜尋都能快速進行。

總結情況：當一個未排序的序列需要進行「非常多次」的搜尋，並且序列的「大小 N 相當大」時，先排序後使用二分搜尋會比直接對未排序序列進行循序搜尋來得快，因為排序的成本可以被多次快速搜尋所攤銷。

核心觀念

本題考查「非管線化」與「管線化」CPU 的執行時間計算。

每條指令依序經過三個階段：

1. Phase 1
2. Phase 2
3. Phase 3

每個階段耗時皆為 $T$，因此單條指令完整執行所需時間為：

$$T+T+T=3T$$

管線化的核心是：不同指令可以同時處於不同階段，但同一條指令仍須依序完成 Phase 1、Phase 2、Phase 3。

---

解題方法

(a) 沒有管線化

沒有管線化時，CPU 必須等第 $i$ 條指令的三個階段全部完成後，才能開始執行第 $i+1$ 條指令。

每條指令需要：

$$3T$$

共有 $n$ 條指令，因此總執行時間為：

$$n \times 3T=3nT$$

所以：

$$\boxed{3nT}$$

---

(b) 使用管線化

使用三階段管線後，執行流程如下：

• 第 1 條指令：先經過三個階段，需要 $3T$。
• 從第 2 條指令開始，管線填滿後，每隔 $T$ 就能完成一條指令。
• 剩餘的 $n-1$ 條指令各增加 $T$。

因此總時間為：

$$3T+(n-1)T$$

整理得：

$$3T+nT-T=(n+2)T$$

所以：

此題考驗對 FTP 協定傳輸檔案時 TCP 連線建立與關閉次數的理解。

核心觀念：FTP 協定使用兩個 TCP 連線來進行檔案傳輸。一個是控制連線 (control connection)，另一個是資料連線 (data connection)。

FTP 的運作方式：

1. 建立控制連線：當 FTP 用戶端連接到 FTP 伺服器時，首先會建立一個 TCP 連線（通常在埠 21）用於傳送指令（如 USER, PASS, LIST, RETR 等）和接收伺服器的回應。這個控制連線在整個 FTP 工作階段期間通常保持開啟。
2. 建立資料連線：當需要傳輸資料（例如下載檔案 RETR 或上傳檔案 STOR）時，FTP 會為這次資料傳輸「額外」建立一個 TCP 連線（在主動模式或被動模式下，埠號不同，但都是 TCP 連線）。
   • 主動模式 (Active Mode)：伺服器從其資料埠（通常是 20）連接回用戶端指定的資料埠。

此題考驗對 TCP (Transmission Control Protocol) 和 UDP (User Datagram Protocol) 這兩種傳輸層協定的服務差異的理解。

核心觀念：TCP 是一個面向連線、可靠、有序的傳輸協定；UDP 是一個無連線、不可靠、盡力而為的傳輸協定。

TCP 提供的主要服務，而 UDP 不提供：

1. 可靠性 (Reliability)：
   TCP 透過確認應答 (acknowledgement, ACK) 和重傳機制來確保資料的可靠傳輸。發送方會等待接收方的確認，如果沒有收到確認，會重傳資料。UDP 則不提供這種確認和重傳機制，資料包可能丟失而不會被發現。

2. 有序性 (Ordered Delivery)：
   TCP 會為每個資料包編號，並確保接收方按照發送順序接收資料。如果資料包順序錯亂，TCP 會暫時緩存，直到正確順序的資料包都到達，然後再按序提交給應用層。UDP 不保證資料包的順序，它們可能以任何順序到達。

3. 流量控制 (Flow Control)：
   TCP 使用滑動視窗 (sliding window) 機制來控制發送方發送資料的速度，以避免發送方過快地發送資料，導致接收方的緩衝區溢出。接收方會告知發送方自己還有多少可用緩衝區空間。

此題考驗對 TCP 擁塞控制機制中，發送方如何從網路行為中推斷網路擁塞的理解。

核心觀念：TCP 擁塞控制演算法（如 Reno, Cubic 等）依賴於觀察網路對資料包的反應，即使路由器不主動發送擁塞報告 (ECN - Explicit Congestion Notification)。

TCP 發送方可以透過以下三種資訊來推斷網路可能發生了擁塞：

1. 封包遺失 (Packet Loss)：
   這是 TCP 推斷擁塞最主要的方式。當網路發生擁塞時，路由器中的緩衝區會滿，導致新來的封包被丟棄 (packet drop)。TCP 發送方通過接收不到封包的確認應答 (ACK)，或者觸發重傳計時器 (retransmission timer) 超時，來判斷封包遺失。封包遺失通常被視為網路擁塞的信號。

2. 往返時間 (Round-Trip Time, RTT) 的增加：
   當網路發生擁塞時，封包在路由器隊列中等待的時間會增加，這導致封包從發送方傳輸到接收方再到發送方收到確認應答 (RTT) 的時間變長。TCP 發送方會持續監測 RTT，如果 RTT 持續穩定地增加，這也可能是一個網路擁塞的跡象。

此題考驗對作業系統中，任務管理相關佇列的理解，特別是 Job Queue 和 Process Queue 的差異。

核心觀念：作業系統使用佇列來管理不同狀態的任務。Job Queue 通常指待執行的工作，而 Process Queue 指的是已載入記憶體、準備或正在 CPU 上執行的進程。

Job Queue (作業佇列)：
Job Queue 通常指的是儲存所有待處理的「工作」(Jobs) 的地方。這些工作可能是：

1. 已提交的程式：在批次處理系統 (batch processing system) 中，所有已提交但尚未開始執行的程式。
2. 待載入記憶體的程式：在多道程式設計環境中，等待被載入主記憶體並準備開始執行的程式。
3. 所有在系統中的進程：有時也廣泛地指所有處於「新」(New) 或「準備」(Ready) 狀態的進程，是所有進程的集合，包括那些還未被 CPU 分配時間的。

總的來說，Job Queue 包含了那些「還未成為 CPU 上實際運行進程」的「任務」或「程式」。它們可能還在磁碟上等待載入，或者已經在記憶體中但等待 CPU 分配時間。

Process Queue (進程佇列)：
Process Queue 通常指的是儲存所有「進程」(Processes) 的地方，這些進程已經存在於主記憶體中，並且正在等待 CPU 的分配，或者正在 CPU 上執行。

核心觀念

依圖中定義，$H$ 代表樹的層數，根節點位於第 $1$ 層。第 $k$ 層最多有 $2^{k-1}$ 個頂點，因此高度為 $H$ 的二元樹最多有

$$1+2+2^2+\cdots+2^{H-1}=2^H-1$$

個頂點。

頂點依層序編號為 $1,2,\ldots,N$，所以所有權重總和為調和數：

$$W(N)=\sum_{i=1}^{N}\frac{1}{i}.$$

(a) 頂點數

僅知道高度 $H$，一般二元樹的頂點數不唯一。至少可形成一條長鏈，因此

$$H\leq N\leq 2^H-1.$$

圖中 $H=3$ 且有 $6$ 個頂點，正符合 $3\leq6\leq7$。

本題後半需使用同一高度下的最大權重總和，因此取最大頂點數：

$$\boxed{N_{\max}=2^H-1}.$$

(b) 最低高度

高度為 $h$ 時，為使權重總和最大，應取最多的 $2^h-1$ 個頂點：

$$W_{\max}(h)=\sum_{i=1}^{2^h-1}\frac{1}{i}.$$

調和數可用

$$\sum_{i=1}^{n}\frac{1}{i}\approx \ln n+\gamma, \qquad \gamma\approx0.5772$$

估算，因此

(a) 前序運算式轉後序運算式

核心觀念

1. 前序運算式（Prefix Expression / 波蘭表示法）：運算子置於兩運算元之前，格式為 [運算子] [運算元1] [運算元2]。
2. 後序運算式（Postfix Expression / 逆波蘭表示法）：運算子置於兩運算元之後，格式為 [運算元1] [運算元2] [運算子]。
3. 前序轉後序的核心規則：
   • 處理前序運算式時，通常由**右至左（Right-to-Left）**掃描運算元與運算子。
   • 遇到運算元即推入堆疊（Stack）；遇到二元運算子時，從堆疊頂端依序彈出兩個運算元 $Op_1$ 與 $Op_2$，組合成後序格式 $Op_1Op_2[運算子]$ 後再推回堆疊。

解題方法

給定前序運算式：+ x a + b c d（共 8 個符號，含運算子 +、x、+ 與運算元 a、b、c、d）。

採用「由右向左掃描 + 堆疊」逐步轉換：

1. 讀取 d（運算元）：推入堆疊。
   • 堆疊狀態：[d]
2. 讀取 c（運算元）：推入堆疊。
   • 堆疊狀態：[d, c]
3. 讀取 b（運算元）：推入堆疊。
   • 堆疊狀態：[d, c, b]
4. 讀取 +（運算子）：彈出頂端兩個運算元 $Op_1 = \text{b}$, $Op_2 = \text{c}$，結合為後序式 bc+ 並推回堆疊。
   • 堆疊狀態：[d, bc+]
5. 讀取 a（運算元）：推入堆疊。
   • 堆疊狀態：[d, bc+, a]
6. 讀取 x（乘法運算子）：彈出頂端兩個運算元 $Op_1 = \text{a}$, $Op_2 = \text{bc+}$，結合為後序式 abc+x 並推回堆疊。
   • 堆疊狀態：[d, abc+x]
7. 讀取 +（加法運算子）：彈出頂端兩個運算元 $Op_1 = \text{abc+x}$, $Op_2 = \text{d}$，結合為後序式 abc+xd+ 並推回堆疊。
   • 堆疊狀態：[abc+xd+]

掃描完畢，堆疊頂端即為最終的後序運算式。

解題技巧

• 加括號還原為中序驗算：
  • 前序式：+ x a + b c d
  • 識別子運算式：+ b c 為 $(b + c)$。
  • 前序式變為：+ x a (b + c) d
  • 識別 x a (b + c) 為 $(a \times (b + c))$。
  • 前序式變為：+ (a * (b + c)) d
  • 識別最外層加法：$((a \times (b + c)) + d)$。
  • 將中序式轉為後序式：
    • $(b + c) \to b c +$
    • $a \times (b + c) \to a b c + \times$

核心觀念

本題考查「單向鏈結串列反轉」以及指標重新連結。

每個節點包含：

• data：儲存資料。
• link：指向下一個節點。
• 最後一個節點的 link 為 NULL。
• first：指向串列第一個節點。

反轉時，必須逐一將每個節點的指向改為前一個節點：

$$x_1 \rightarrow x_2 \rightarrow \cdots \rightarrow x_n \rightarrow NULL$$

反轉為：

$$NULL \leftarrow x_1 \leftarrow x_2 \leftarrow \cdots \leftarrow x_n$$

最後再令 first 指向原本的最後一個節點。

解題方法

使用三個指標：

• next：尚未反轉部分的第一個節點。
• current：目前正在處理的節點。
• previous：已完成反轉部分的第一個節點。

初始狀態為：

next = first;
current = NULL;
previous = NULL;

因此：

1. 取出目前節點

將 next 指向的節點交給 current：

current = next;

所以：

$$B = next$$

2. 保存尚未處理的串列

反轉 current->link 前，必須先保存原本的下一個節點，否則後續串列會遺失：

next = current->link;

所以：

$$C = current->link$$

3. 將目前節點反向連接

使目前節點指向已反轉部分：

current->link = previous;

所以：

$$D = previous$$

4. 移動 previous

下一輪迴圈開始前，應讓 previous 往前移至目前節點：

previous = current;

題目將此行留在空格 A 的初始化與迴圈結構中，因此初始值必須為：

previous = NULL;

所以：

$$A = NULL$$

迴圈結束時，所有節點都已反轉，previous 正好指向反轉後的第一個節點：

first = previous;

所以：

$$E = previous$$

完整程式碼