113 年 國立成功大學會計學研究所乙組《計算機概論》

核心觀念

• 路由器 (router)：工作於 OSI 第 3 層（網路層），負責不同子網路之間的封包轉遞。它本身不限制「可連接」的終端設備數量，限制因素主要在 IP 位址空間 與 硬體資源（CPU、記憶體、介面數）。
• IP 位址上限：
  • IPv4：$2^{32}=4,294,967,296$ 個位址（實務上受 NAT、子網路劃分限制）。
  • IPv6：$2^{128}$ 個位址，遠大於任何實際需求。
• 因此，從協定層面看，路由器理論上 不存在固定上限，只要有足夠的位址與硬體資源即可。

---

解題方法

1. 判斷題目問的是 「路由器可能能連接多少台有線/無線電腦與行動裝置」。
2. 先回顧路由器的功能：將不同端點的封包轉發，而非限制連接數。
3. 思考限制來源：
   • IP 位址：以 IPv4 為例，理論上最多可支援 $4$ 億多台設備；IPv6 更是無可比擬。
   • 硬體限制：實務上少數高階企業級路由器仍可能受 CPU、RAM、介面卡數量限制，但題目未給出硬體規格，因此不可以此作答依據。
4. 依上述分析，正確答案應為 「沒有固定上限」，即選項 d。

---

選項分析

選項	內容	為何錯誤
a. more than 200	主張上限在 200 台以上。	200 只是一個任意數值，並無協定或標準證明路由器只能容納此上限。實際上，即使是家用路由器也常支援 250–300 台同時連線，遠超過 200。因此此選項過於保守且缺乏理論依據。

本題考驗的是對無線通訊技術的認識，特別是哪些技術是利用無線電波來傳輸高速訊號。

• a. generations (世代)：這是一個廣泛的術語，用於描述無線通訊技術的演進，例如 1G、2G、3G、4G、5G。每一代技術都採用不同的無線電波頻段和調變技術來提供更快的速度和更多的功能。雖然「世代」本身不是一種無線電波，但它代表了使用無線電波傳輸訊號的技術進步。
• b. microwaves (微波)：微波是電磁波譜中的一部分，頻率範圍大約在 300 MHz 到 300 GHz 之間。微波因其高頻率和較大的頻寬，非常適合用於高速無線通訊，例如無線網路 (Wi-Fi)、行動通訊 (4G, 5G)、衛星通訊、雷達等。

本題考驗的是對常見記憶卡種類的認識。記憶卡是廣泛應用於數位相機、手機、遊戲機等電子設備的儲存介質。

• a. SDXC (Secure Digital eXtended Capacity)：這是 SD 記憶卡的一種標準，支援大容量（最高 2TB）和較快的傳輸速度。它是一種非常常見的記憶卡類型。
• b. Memory Stick PRO Duo：這是 Sony 公司開發的一種記憶卡格式，曾廣泛用於 Sony 的數位相機、PSP 遊戲機等設備。雖然目前市場上可能不如 SD 卡普及，但它確實是一種常見的記憶卡類型。

本題考驗的是對條碼 (bar code) 標準的認識，特別是零售和超市常用的條碼類型。條碼是一種將資訊編碼成可讀圖案的技術，方便商品識別和結帳。

• a. UPC (Universal Product Code)：UPC 是北美地區最常見的商品條碼標準，廣泛用於零售業，包括超市。它能識別商品及其製造商。

本題考驗的是對 CMOS (Complementary Metal-Oxide Semiconductor) 這個常見半導體技術術語的縮寫含義。CMOS 技術廣泛應用於積體電路，特別是微處理器、記憶體和感測器等，因其低功耗和高速度特性而備受青睞。

• a. cache memory on silicon：雖然快取記憶體 (cache memory) 確實常常使用矽 (silicon) 作為基底，但這不是 CMOS 的全稱。
• b. circuit method-off-synched：這看起來像是一個隨意組合的詞語，與半導體技術無關。

核心觀念

本題考的是二分搜尋法（binary search）的平均探查次數（mean number of probes）。

二分搜尋每次比較中間項目，若未命中，便將搜尋範圍縮小為原來的一半。因此搜尋深度與資料筆數 $N$ 的對數有關，時間複雜度為：

$$O(\log_2 N)$$

題目問的是「成功找到指定索引項目」時的平均探查次數，而非最壞情況或排序所需時間。

解題方法

假設索引共有 $N$ 個項目，且二分搜尋形成近似平衡的搜尋樹。

以最規則的情況 $N=2^k-1$ 為例：

• 第 $1$ 層有 $1$ 個項目，每個項目需探查 $1$ 次。
• 第 $2$ 層有 $2$ 個項目，每個項目需探查 $2$ 次。
• 第 $3$ 層有 $4$ 個項目，每個項目需探查 $3$ 次。
• 第 $k$ 層有 $2^{k-1}$ 個項目，每個項目需探查 $k$ 次。

總探查次數為：

$$1\cdot 1+2\cdot 2+4\cdot 3+\cdots+2^{k-1}\cdot k$$

其平均值為：

$$\frac{\displaystyle\sum_{i=1}^{k}i2^{i-1}}{2^k-1}$$

利用公式：

$$\sum_{i=1}^{k}i2^{i-1}=(k-1)2^k+1$$

因此平均探查次數為：

$$\frac{(k-1)2^k+1}{2^k-1}$$

當 $N$ 很大時，$2^k$ 遠大於 $1$，上式可近似為：

$$k-1$$

核心觀念

本題考查遞迴函數的執行流程，以及遞迴終止條件。

函數定義如下：

• 當 $X=1$ 時，$F(X)=0$。
• 當 $X\ne 1$ 時：

$$F(X)=X\cdot F(X-1)+X^2$$

計算時，必須先取得 $F(X-1)$，再代回目前這一層的公式。

解題方法

由基底條件開始逐層向上計算：

$$F(1)=0$$ $$F(2)=2\cdot F(1)+2^2 =2\cdot 0+4 =4$$ $$F(3)=3\cdot F(2)+3^2 =3\cdot 4+9 =21$$ $$F(4)=4\cdot F(3)+4^2 =4\cdot 21+16 =100$$

因此：

$$F(4)=100$$

選項分析

(a) $F(4)$ is 100

正確。由遞迴計算得：

$$F(4)=100$$

(b) $F(1)$ is 1

錯誤。當 $X=1$ 時，直接執行基底條件：

$$F(1)=0$$

不是 $1$。

(c) $F(0)$ is 1

本題考驗的是對軟體設計測試方法和工具的認識。題目問的是「測試軟體設計 (testing the design)」，而不是測試已實現的程式碼。

• a. Entity-relationship diagram (ERD)：ERD 是一種用於表示資料庫結構的圖，它描述了實體 (entity) 及其之間的關係 (relationship)。ERD 主要用於資料庫設計，雖然它與軟體系統相關，但它本身不是一種「測試軟體設計」的方法，而是描述設計的一種工具。
• b. Class diagram：Class diagram 是統一塑模語言 (UML) 的一部分，用於描述物件導向軟體系統的靜態結構，包括類別、屬性、方法以及它們之間的關係。Class diagram 是軟體設計的重要成果，但它本身是設計的表現，而不是測試設計的方法。

核心觀念

本題考查多重積體電路（MSI, Medium-Scale Integration）中，4 位元二進位加法器的腳位估算。

一個 4-bit adder 必須處理：

• 兩組 4 位元輸入：$A_3A_2A_1A_0$、$B_3B_2B_1B_0$
• 1 個最低位的輸入進位：$C_{in}$
• 4 位元和：$S_3S_2S_1S_0$
• 1 個最高位的輸出進位：$C_{out}$

此外，實際 MSI 晶片還需要：

• $V_{CC}$：電源腳
• GND：接地腳

解題方法

先計算邏輯輸入與輸出腳位：

1. 輸入腳位

兩組 4 位元數字各需要 4 個腳位：

$$4+4=8$$

再加上輸入進位 $C_{in}$：

$$8+1=9$$

因此，輸入端共需要 9 個腳位。

2. 輸出腳位

4 位元加法結果需要 4 個和輸出：

$$S_3,S_2,S_1,S_0$$

再加上輸出進位 $C_{out}$：

$$4+1=5$$

因此，輸出端共需要 5 個腳位。

3. 加上電源與接地腳

邏輯訊號腳位總數為：

$$9+5=14$$

核心觀念

• 後置式 (Postfix) / 逆波蘭記號：運算子出現在其操作元之後。計算時以堆疊 (stack) 為基礎，依序讀取每個 token，若為數字則 push，若為運算子則 pop 兩個或一個（根據運算子需求）再 push 計算結果。
• 常用運算子：
  • + , - , * , / 為二元運算子，分別執行加、減、乘、除。
  • ** 為次方運算子，計算 底數 ** 指數（a ** b = a^b）。

解題方法

1. 切分 token
   給出的後置式為

   6-2+1.2 7.5 1.5 / ** 
   

   依照空白分割，可得到四個 token：

   • 6-2+1.2 （這是一個算術子表達式，先算出其值）
   • 7.5
   • 1.5
   • /
   • **

2. 先算子表達式 6-2+1.2
   依照左至右的普通中置算式規則：

$6-2+1.2 = (6-2)+1.2 = 4+1.2 = 5.2$

3. 堆疊操作

   步驟	讀入 token	堆疊內容 (自左至右)	備註
   1	5.2	5.2	把 6-2+1.2 的結果推入堆疊
   2	7.5	5.2 , 7.5	推入

核心觀念

本題考查兩種參數傳遞方式：

1. Call by value（傳值呼叫）
   呼叫函式時，將實際參數的值複製一份給形式參數。函式內修改形式參數，不會影響原本的變數。

2. Call by address（傳址呼叫）
   將實際參數的記憶體位址傳入函式。形式參數相當於原變數的別名，修改形式參數會直接改變原變數。

題目中的函式可整理為：

$$Y \leftarrow Z$$ $$F \leftarrow X+Z$$

因此，函式先將 $Z$ 的值指定給 $Y$，再計算 $X+Z$ 並回傳。

呼叫方式為：

$$A=F(B,B,B+C)$$

初始值為：

$$B=1.0,\qquad C=2.0$$

所以第三個實際參數的初始值為：

$$B+C=1.0+2.0=3.0$$

---

解題方法

關鍵在於觀察前兩個實際參數都是 $B$：

$$X\leftarrow B,\qquad Y\leftarrow B$$

在傳值呼叫中，$X$ 與 $Y$ 是兩份獨立副本；在傳址呼叫中，$X$ 與 $Y$ 會指向同一個變數 $B$。

---

（a）Call by value

傳入函式時，各形式參數取得實際參數的值：

$$X=1.0,\qquad Y=1.0,\qquad Z=3.0$$

執行第一行：

$$Y\leftarrow Z=3.0$$

此時只有函式內的 $Y$ 被修改，原本的 $B$ 仍為 $1.0$。

接著計算：

核心觀念

本題評量硬碟儲存容量（Disk Storage Capacity）與磁軌資料傳輸率（Data Transfer Rate / Track Capacity）之間的物理與幾何關係。

1. 磁軌容量（Track Capacity）與資料傳輸率之關係：
   硬碟旋轉一整圈時，讀寫頭剛好掃過該磁軌的一整周。若忽略區段間隙（gaps）與格式化開銷，讀寫頭在「一圈旋轉時間（Rotational Latency of one revolution）」內能讀取／寫入的位元數，即為該磁軌的資料容量（Bits per track）： $$\text{Track Capacity (bits)} = \text{Data Transfer Rate (bps)} \times \text{Time per Revolution (seconds)}$$
2. 硬碟總儲存容量（Total Disk Capacity）：
   在單面磁碟（Single-surface disk）且無磁軌密度變化假設下，總位元容量等於總磁軌數乘以單一磁軌容量；再將位元轉換為位元組（Byte）： $$\text{Total Capacity (Bytes)} = \frac{\text{Number of Tracks} \times \text{Track Capacity (bits)}}{8\text{ bits/byte}}$$

---

解題方法

步驟一：計算磁碟旋轉一圈所需的時間（秒）

已知旋轉速度為 $300\text{ RPM}$（Revolutions Per Minute）：

$$\text{每秒轉數} = \frac{300}{60} = 5\text{ rev/sec}$$

因此，硬碟旋轉一圈（One revolution）所需時間 $T$ 為：

$$T = \frac{1}{5} = 0.2\text{ 秒}$$

步驟二：計算單一磁軌的容量（Bits per track）

在不考慮區段間隙或特殊格式化的條件下，磁頭每秒傳輸 $250{,}000\text{ bits}$，旋轉一圈（$0.2\text{ 秒}$）即掃過一條磁軌的完整資料：

$$\text{Bits per track} = 250{,}000\text{ bits/s} \times 0.2\text{ s} = 50{,}000\text{ bits}$$

步驟三：計算整顆磁碟的名義總儲存容量（Bytes）

該單面磁碟共有 $35$ 條磁軌：

$$\text{總位元數} = 35\text{ tracks} \times 50{,}000\text{ bits/track} = 1{,}750{,}000\text{ bits}$$

核心觀念

• 二分搜尋（Binary Search）：在已排序的陣列中，每一次比較都將搜尋區間減半。
• 比較次數（Comparisons）：指在搜尋過程中與目標值做相等或大小比較的次數。
• 最壞情況（Maximum comparisons）：搜尋必須遍歷的最大深度，即最深的遞迴或迭代層數。
• 平均情況（Average comparisons）：在所有可能的成功與失敗搜尋（各佔 50% 機率）之下，期望的比較次數。

---

(a) 最大比較次數

二分搜尋的比較次數與搜尋深度相同。對於長度為 $n$ 的已排序列表，搜尋區間每次減半，直到只剩下一個元素。
若 $n = 2^{k}$（完整的二的冪），最後一次比較會在第 $k+1$ 次才結束；若 $n$ 不是二的冪，則需要的比較次數等於 $\lceil \log_{2} n \rceil + 1$（多一次比較用於確認失敗）。

$\boxed{\text{最大比較次數}= \left\lceil \log_{2} n \right\rceil + 1}$

此式兼顧成功與失敗兩種情形：

• 成功：最壞情況出現在目標位於樹的最深葉節點，需比較 $\lceil\log_{2} n\rceil$ 次。
• 失敗：當搜尋值不在列表中，最終會將區間縮至空集合，仍需多做一次比較以確定失敗，故多加 $1$。

---

(b) 平均比較次數

搜尋分為成功搜尋與失敗搜尋，兩者機率皆為 $0.5$。

1. 成功搜尋的期望比較次數

成功搜尋的比較次數等同於在一棵「完全二元搜尋樹」中，目標鍵所在節點的深度（根層為第 $1$ 層）。對於 $n$ 個鍵，若把它們均勻分佈在樹的各層，期望深度為

$E_{\text{succ}} = \frac{1}{n}\sum_{i=1}^{n} d_i$

其中 $d_i$ 為第 $i$ 個鍵的深度。已知二分搜尋樹的平均深度近似

$E_{\text{succ}} \approx \log_{2} n - \frac{1}{2} \quad (\text{對大 } n\text{ 成立})$

更嚴謹的表達式（不近似）為

$$E_{\text{succ}} = \frac{1}{n}\Bigl[\, (2^{\lfloor\log_{2}n\rfloor+1}-n-1)\cdot(\lfloor\log_{2}n\rfloor+2) + (2n-2^{\lfloor\log_{2}n\rfloor+1}+1)\cdot(\lfloor\log_{2}n\rfloor+1) \Bigr]$$

此式可簡化為

核心觀念

本題考查布林代數的化簡，主要使用以下定律：

• 交換律：$AB=BA$
• 冪等律：$A+A=A$
• 吸收律：$A+AB=A$
• 恆等律：$A+1=1$

其中，吸收律表示：只要某一項 $A$ 已經存在，任何包含 $A$ 的乘積項 $AB$ 都會被 $A$ 吸收。

---

解題方法

原式為

$$X+XYZ+YZX+WX+WX+XY$$

先利用交換律整理乘積項：

$$YZX=XYZ$$

因此原式可寫成

$$X+XYZ+XYZ+WX+WX+XY$$

利用冪等律：

$$XYZ+XYZ=XYZ$$ $$WX+WX=WX$$

原式變為

$$X+XYZ+WX+XY$$

接著觀察其餘各項：

$$XYZ=X(YZ)$$ $$WX=XW$$ $$XY=XY$$

核心觀念

• 三對角矩陣 (tridiagonal matrix)：只有主對角線、上對角線與下對角線可能有非零元素，其他位置皆為 0。
• 矩陣元素計數：對於 $n \times n$ 的矩陣，主對角線有 $n$ 個元素；上、下對角線各有 $n-1$ 個元素（首尾各缺一個）。
• 記憶體線性化：若僅儲存這三條對角線，且以列序 (row‑major) 的方式依序寫入，則在一維陣列 $A$ 中的索引必須由 $(i,j)$ 轉換為線性位址 $addr(i,j)$。

---

解題方法 (a) – 最大非零元素個數

1. 主對角線：每一行 $i$ 都有元素 $ARR[i,i]$，共 $n$ 個。
2. 上對角線：僅在 $i=1,\dots ,n-1$ 時 $ARR[i,i+1]$ 可能非零，故有 $n-1$ 個。
3. 下對角線：僅在 $i=2,\dots ,n$ 時 $ARR[i,i-1]$ 可能非零，同樣 $n-1$ 個。
4. 所有可能非零位置不會重疊（因為對角線彼此平行），故最大非零元素數目為

$N_{\text{max}} = n + (n-1) + (n-1) = 3n-2 .$

---

解題方法 (b) – 行序儲存的位址公式
假設三條對角線依下列順序依列寫入一維陣列 $A[\,0\,..\,3n-3\,]$（共 $3n-2$ 個元素）：

列 $i$	儲存順序	元素說明
$i=1$	$ARR[1,1]$, $ARR[1,2]$	主、上
$i=2\sim n-1$	$ARR[i,i-1]$, $ARR[i,i]$, $ARR[i,i+1]$	下、主、上
$i=n$	$ARR[n,n-1]$, $ARR[n,n]$	下、主

寫成通式，先計算在第 $i$ 列之前已寫入的元素個數 $offset(i)$，再根據 $j$ 的相對位置加上偏移。

1. 列前已寫入元素數

$$offset(i)= \begin{cases} 0, & i=1,\\[4pt] 2 + 3\,(i-2), & 2\le i\le n-1,\\[4pt] 2 + 3\,(n-2), & i=n . \end{cases}$$

化簡得到