109 年 國立中正大學資訊管理學系碩士班乙組《計算機概論》

核心觀念

本題測驗計算機系統中二補數（2's Complement）系統下的減法運算。

在數位邏輯與計算機算術中：

1. 減法轉加法原則：二進位減法 $A - B$ 在硬體中通常以「加上減數的二補數（即負數表示）」來實現，即：
   $A - B = A + (-B) = A + [B \text{ 的二補數}]$
2. 取二補數的方法：
   • 傳統方式：將數值的所有位元反相（取一補數），最後在最低有效位（LSB）加 $1$。
   • 快速口訣：由右向左（由 LSB 往 MSB）尋找，在遇到「第一個 $1$」之前的所有 $0$ 與該「第一個 $1$」保持不變，其餘左邊的位元全部反轉（$0$ 變 $1$、$1$ 變 $0$）。
3. 固定位元寬度（Word Length）與進位捨棄：
   題目給定兩個 8-bit 的運算元，因此運算結果同樣限定為 8-bit。運算過程若最高位（MSB）產生額外的溢出進位（End-around Carry / Carry-out），在二補數加法中應直接捨棄（Truncate）。

---

解題方法

題目要求計算：
$00001111_2 - 10101010_2$

步驟一：求減數 $10101010_2$ 的二補數（$-B$）

• 減數 $B = 10101010_2$
• 取一補數（反相）：$01010101_2$
• 再加 $1$（求二補數）：
  $01010101_2 + 1 = 01010110_2$
• 故 $-B = 01010110_2$。

步驟二：執行加法運算 $A + (-B)$

將被減數 $A = 00001111_2$ 與 $-B = 01010110_2$ 進行逐位相加：

& 00001111_2 \\ + & 01010110_2 \\ \hline & 01100101_2 \end{array}$$ 逐位加法詳細過程（由右至左）： - 第 0 位：$1 + 0 = 1$（進位 0） - 第 1 位：$1 + 1 + 0 = 0$（進位 1） - 第 2 位：$1 + 1 + 1 = 1$（進位 1） - 第 3 位：$1 + 0 + 1 = 0$（進位 1） - 第 4 位：$0 + 1 + 1 = 0$（進位 1）

核心觀念

本題考查超文本（Hypertext）與超媒體（Hypermedia）的基本架構，源自全球資訊網（World Wide Web, WWW）發明人提姆·伯納斯-李（Tim Berners-Lee）提出的「筆記網絡（Web of Notes）」概念，亦為計算機概論經典教科書（如 Brookshear 的 Computer Science: An Overview）中的標準名詞定義。

在超文本／超媒體系統中：

1. 節點（Nodes）：系統中存放各項資訊內容的單元（包含文字、圖片、聲音或文件等）。
2. 連結（Links / Hyperlinks）：用來連接不同節點之間的參照或關係路徑。

---

解題方法

提姆·伯納斯-李在 1989 年於歐洲核子研究組織（CERN）提出全球資訊網的構想時，將分散在各主機上的文件與資料描述為一張由各項筆記相互關聯形成的「筆記網絡（Web of Notes）」。

由圖論（Graph Theory）與超文本架構可知：

• 題目詢問「被連結在一起的各項資訊本身（items of information linked together）」在名詞定義上為何者。
• 儲存資訊的實體／單元稱為 Nodes（節點）；而在節點之間建立關聯的連接線則稱為 Links（連結）。

因此，被連結在一起的資訊項目即為 Nodes。

---

選項分析

• (A) Trails（足跡／路徑）：錯誤。
  此名詞源自 1945 年范尼瓦·布希（Vannevar Bush）發表的 As We May Think 中所構想的微縮膠卷檢索系統「

核心觀念

本題測驗 TCP/IP 階層協定模型（TCP/IP Protocol Architecture） 的各層職責與運作機制。

在標準四層 TCP/IP 模型中，由上至下依序為：

1. 應用層（Application Layer）：負責為應用程式提供網路通訊服務（例如 HTTP、DNS、SMTP）。
2. 傳輸層（Transport Layer）：負責端對端（End-to-End）或行程對行程（Process-to-Process）的可靠或不可靠傳輸（例如 TCP、UDP）。
3. 網路層（Network Layer / Internet Layer）：負責主機對主機（Host-to-Host）的邏輯定址（IP Address）與路徑選擇（Routing）。
4. 鏈結層（Link Layer / Network Interface Layer / Network Access Layer）：負責在同一個實體網路或相鄰節點（Hop-to-Hop / Node-to-Node）之間，透過實體傳輸媒介（如雙絞線、光纖、無線電波）將資料以訊框（Frame）或位元訊號的形式**實際傳輸（actually transmits a message）**出去。

---

解題方法

本題的解題關鍵在於辨析各層協定是屬於「邏輯協調與處理」還是「實體訊號傳送」：

• 高層協定（應用層、傳輸層、網路層）所產生的訊息、區段（Segment）與封包（Packet），本質上皆為資料結構與邏輯控制資訊（標頭）。
• 任何網路訊息若要真正離開主機並在實體媒介上流動，必須一路向下封裝，最後由最底層的 鏈結層（Link Layer，亦涵蓋或對應至實體介面） 將位元轉為訊號並推送到通訊媒介上。
• 因此，在 TCP/IP 四層架構中，真正負責執行訊息實際傳輸動作的層級即為最底層的 Link Layer。

---

核心觀念

本題測驗 Java 程式語言中一維陣列的索引機制（Zero-based Indexing）以及標準輸出方法 print() 的行為特徵：

1. 陣列索引從 0 開始（0-indexed）：長度為 $N$ 的陣列，合法索引範圍為 $0 \sim N-1$。若陣列宣告初始化為 $\{v_0, v_1, v_2, \dots\}$，則第 $k$ 個元素對應的索引為 $k-1$（即 $A[0] = v_0, A[1] = v_1, \dots$）。
2. System.out.print() 的輸出特性：呼叫 System.out.print() 只會輸出指定內容，不會自動附加換行符號（Newline）。連續呼叫多次時，後續輸出的內容會緊接在前次輸出的末尾。

---

解題方法

1. 陣列元素與索引對照

程式碼第一行宣告並初始化一個整數陣列：

int[] numarray = { 10, 20, 30, 40, 50 };

陣列各元素之索引（Index）與對應數值如下表：

索引 (Index)	元素值 (Value)
numarray[0]	10
numarray[1]	20
numarray[2]	30
numarray[3]	40
numarray[4]	50

由此可知：

• numarray[2] 取出的是第 3 個元素，其值為 30。
• numarray[3] 取出的是第 4 個元素，其值為 40。

2. 輸出流程追蹤

• 執行 System.out.print(numarray[2]);：在螢幕上印出 30，游標停留在 30 之後（不換行）。
• 執行 System.out.print(numarray[3]);：緊接著印出 40。

核心觀念

本題測驗基礎資料結構中**堆疊（Stack）**的操作原理：

1. 後進先出（LIFO, Last-In-First-Out）特性：
   • 堆疊是一種僅允許在一端（稱為頂端，Top）進行插入與刪除的線性資料結構。
   • 最後被推入（Push / Insert）的資料元素，會最先被彈出（Pop / Remove）。
2. 方向性定義：
   • 題目明確指出堆疊初始狀態的順序為「由頂端到底端（from top to bottom）」。
   • 因此，移出（Remove/Pop）元素時，必從頂端（Top）開始移出；放入（Insert/Push）新元素時，新元素會成為新的頂端（Top）。

---

解題方法

依序追蹤堆疊狀態的變化步驟：

1. 初始狀態：

   • 題目給定堆疊由頂到底為：$\text{wa, xb, yc, zd}$
     $\text{Top} \rightarrow [\text{wa}, \text{xb}, \text{yc}, \text{zd}] \leftarrow \text{Bottom}$

2. 移出兩個元素（two entries were removed）：

   • 依據 LIFO 原則，從頂端連續執行兩次 Pop 操作：
     • 第 1 次移出頂端元素：$\text{wa}$（剩餘 $\text{xb}, \text{yc}, \text{zd}$）
     • 第 2 次移出頂端元素：$\text{xb}$（剩餘 $\text{yc}, \text{zd}$）
   • 此時堆疊由頂到底為：
     $\text{Top} \rightarrow [\text{yc}, \text{zd}] \leftarrow \text{Bottom}$

3. 插入新元素 $\text{re}$（entry re was inserted）：

   • 執行 Push 操作，將 $\text{re}$ 放入頂端：
   • 新元素 $\text{re}$ 成為新的 Top。

核心觀念

本題測驗關聯式資料庫（Relational Database）中的關聯代數（Relational Algebra）基本運算子概念。

在關聯式資料模型中，資料是以「關聯（Relation，即二維資料表 Table）」的形式組織。關聯代數運算主要可分為：

1. 單元運算（Unary Operations）：僅作用於單一關聯（例如：$\sigma$ 選擇運算、$\pi$ 投影運算）。
2. 二元運算（Binary Operations）：作用於兩個或多個關聯（例如：笛卡兒積 $\times$、結合運算 $\bowtie$、聯集 $\cup$、差集 $-$）。

題幹所詢問的是「能夠將**多個關聯（more than one relation）**的資料合併在一起」的運算。

---

解題方法

題目關鍵字為 "combines data from more than one relation"（合併來自多個關聯的資料）：

1. 檢視各選項中屬於「運算（Operation）」的項目。
2. 區分運算作用的對象是「單一關聯（單元運算）」還是「跨關聯（二元運算）」。
3. 在關聯代數中，用來依據特定關聯條件（例如外來鍵與主鍵的對應）將兩個關聯的元組（Tuples/Rows）水平拼接成一個新關聯的運算即為 JOIN（符號記為 $\bowtie$）。因此 (B) 為正確解答。

---

選項分析

• (A) SELECT（選擇運算，符號記為 $\sigma$）：錯誤。
  • 屬於單元運算（Unary Operation），作用於單一關聯。

核心觀念

本題測驗資料探勘（Data Mining）與機器學習任務的核心分類及其應用情境：

1. 非監督式學習（Unsupervised Learning）之分群（Clustering）：
   • 定義：在缺乏預先標記類別標籤（Unlabeled data）的情況下，依據樣本間的特徵相似度（Similarity）或距離（Distance），將資料自動劃分為若干個群集（Clusters）。
   • 特性：目標是達到「群內同質性高（High intra-cluster similarity）、群間異質性高（High inter-cluster heterogeneity）」。當題幹提及發掘資料內在未知的「異質性（Heterogeneity）」或「自然分組（Natural groupings）」時，即為分群技術的典型目標。
2. 監督式學習（Supervised Learning）與描述性特徵化（Characterization / Discrimination）：
   • 包含分類（Classification）、類別特徵描述（Class description）與類別區別比對（Class discrimination），皆建立在目標類別（Class labels）已事先明確定義的基礎上。
3. 關聯分析（Association Analysis）：
   • 探討資料項目之間的共現關係（Co-occurrence）或因果關聯規則（如 $A \rightarrow B$），而非對樣本個體進行群體結構劃分。

---

解題方法

1. 關鍵字定位：
   • 題幹核心目標為 "identify any underlying heterogeneity within borrowers' patterns"（識別銀行借款人行為模式中潛在的異質性）。
2. 分析與推論：
   • 銀行事先並未對借款人的特定行為模式給定預設標籤，而是希望透過演算法在「未標記資料」中，找出借款人之間客觀存在的不同群組結構（即異質性）。
   • 將異質的母體依其特徵區隔為若干內部同質、彼此互異的子群體，所採用的標準技術即為分群分析（Cluster analysis）（例如：客戶分群、風險特徵分組）。

---

核心觀念

本題測驗「數位色彩表示法（RGB Color Model）」與「基礎組合計數原理（乘法原理）」。

1. RGB 色彩模型：
   彩色顯示器通常由紅（Red, R）、綠（Green, Green, G）、藍（Blue, B）三原色光混合產生不同顏色。在真彩色（True Color，即 24-bit 顏色深度）系統中，每種原色（Color Channel）使用 8 個位元（1 byte）表示，因此各有 $2^8 = 256$ 種強度等級（數值範圍通常為 0 至 255）。

2. 獨立組合的乘法原理：
   由於紅、綠、藍三原色的數值是相互獨立選取的，若三者各自有 $N_R$、$N_G$、$N_B$ 種可能取值，則由這三原色所能組合出的總顏色數為：

   $$\text{總顏色數} = N_R \times N_G \times N_B$$

---

解題方法

依題意，三原色各自有 256 種可能數值：

• 紅色（R）：$N_R = 256 = 2^8$
• 綠色（G）：$N_G = 256 = 2^8$
• 藍色（B）：$N_B = 256 = 2^8$

由乘法原理，計算系統所能呈現的所有可能顏色總數：

$$\text{Total Colors} = 256 \times 256 \times 256$$

以 2 的次方化簡計算：

$$256^3 = (2^8)^3 = 2^{24}$$

進一步展開 $2^{24}$：

$$2^{24} = 2^4 \times 2^{20} = 16 \times 1,048,576 = 16,777,216$$

因此，在 RGB 色彩系統中，可表示的顏色總數為 16,777,216 種。

---

選項分析

核心觀念

本題測驗「演算法複雜度」中**問題複雜度（Complexity of a Problem）與搜尋演算法（Searching Algorithms）**的基本定義：

1. 未排序串列搜尋（Unsorted List Search）：
   在一般的串列（List）中，若未特別指明「已排序（Sorted）」，預設皆為無序狀態。在最差與平均情況下，尋找特定元素必須透過循序搜尋（Sequential / Linear Search）逐一比對。
2. 問題的漸近複雜度記號 $\Theta$（Tight Bound）：
   • 上界（Upper Bound）：以循序搜尋（Linear Search）走訪長度為 $n$ 的串列，最差需比較 $n$ 次，時間複雜度為 $O(n)$。
   • 下界（Lower Bound）：對於任意未排序且以「比較（Comparison）」為基礎的搜尋演算法，若要確認某個目標元素是否存在，在對手論證（Adversary Argument）的最差情況下，任何演算法都至少需要檢查 $n$ 個元素，故其複雜度下界為 $\Omega(n)$。
   • 由於問題的上界與下界皆為線性時間，此問題的時間複雜度界定為 $\Theta(n)$。

---

解題方法

1. 確認前提假設：
   題目敘述為「searching for a particular entry in a list」，未提及該串列具有排序（Sorted）特性或任何前置索引結構（如 Hash Table 或 Binary Search Tree）。因此，必須視為一般性的未排序串列搜尋問題。
2. 分析搜尋過程：
   • 最差情況（Worst-case）：欲尋找之元素位於串列最後一個位置，或者該元素根本不存在於串列中，必須完整檢查所有 $n$ 個元素，比較次數為 $n$ 次。

核心觀念

1. 比較排序法（Comparison-based Sorting）的下界理論（Lower Bound）：
   • 任何基於元素間「兩兩比較」的排序演算法，其行為皆可用一棵「決策樹（Decision Tree）」來表示。
   • 對於包含 $n$ 個相異元素的序列，所有可能的排列共有 $n!$ 種，故決策樹至少必須具備 $n!$ 個葉節點（Leaf Nodes）。
   • 設決策樹之高度為 $h$（代表最壞情況下的比較次數），二元樹至多有 $2^h$ 個葉節點，因此滿足不等式： $$2^h \ge n!$$
   • 兩邊取對數並利用斯特靈公式（Stirling's Approximation, $\ln(n!) \approx n\ln n - n$）可得： $$h \ge \log_2(n!) = \Omega(n \log n)$$
   • 結論：在最壞情況（Worst Case）下，任何基於比較的排序演算法，其時間複雜度的理論下限皆為 $\Omega(n \log n)$。若一個排序演算法在最壞情況下的時間複雜度達到 $O(n \log n)$，即稱為達到理論最佳解（Optimal）。

---

解題方法

• 切入點：本題旨在詢問選項中何者為一般情況/最壞情況下時間複雜度的「最佳演算法（Optimal Solution）」。
• 評估標準：檢視各排序演算法在最壞情況（Worst Case）與平均情況（Average Case）下的時間複雜度。凡最壞情況時間複雜度可達到比較排序下限 $O(n \log n)$ 者，即符合「時間複雜度觀點下的最佳解」。

各演算法時間複雜度對照如下表：

排序演算法	最壞時間複雜度	平均時間複雜度	最佳時間複雜度	是否達到理論最優
Insertion Sort	$O(n^2)$	$O(n^2)$	$O(n)$	否
Bubble Sort	$O(n^2)$	$O(n^2)$	$O(n)$	否
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	否
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	是

核心觀念

本題評量重點為控制結構中的 do-while 迴圈運作機制、累加運算（等差級數）以及迴圈終止條件的精準判斷。

1. do-while 迴圈特性：屬於「後測試迴圈（Post-test loop）」，迴圈主體至少會被執行一次，執行完畢後才檢驗 while 後方條件式；若條件為真（true）則繼續下一輪迭代，若為假（false）則終止跳出。
2. 數值狀態轉換：
   • 變數 $s$ 初值為 $1$，每輪迭代將累加當前的 $n$ 值。
   • 變數 $n$ 初值為 $1$，每輪累加後遞增 $1$（n++）。
   • 第 $k$ 次迭代結束時：
     $n = k + 1$
     $s = 1 + \sum_{i=1}^{k} i = 1 + \frac{k(k+1)}{2}$
3. 終止條件：迴圈持續執行的條件為 $s < 10 \times n$。反之，當 $s \ge 10 \times n$ 時跳出迴圈。

---

解題方法

步驟一：建立數學不等式分析跳出時機

設迴圈共執行了 $k$ 次迭代：

• 迭代結束時：$n = k + 1$
• 迭代結束時：$s = 1 + \frac{k(k + 1)}{2}$

迴圈欲終止跳出，條件式 $s < 10 \times n$ 必須不成立（即 $s \ge 10 \times n$）：
$1 + \frac{k(k+1)}{2} \ge 10(k+1)$

將式子同乘 $2$ 並整理：
$2 + k(k+1) \ge 20(k+1)$
$k^2 - 19k - 18 \ge 0$

求對應二次方程式 $k^2 - 19k - 18 = 0$ 的正根：
$k = \frac{19 + \sqrt{19^2 - 4(1)(-18)}}{2} = \frac{19 + \sqrt{361 + 72}}{2} = \frac{19 + \sqrt{433}}{2}$

因為 $20^2 = 400$ 且 $21^2 = 441$，可知 $\sqrt{433} \approx 20.8$：
$k \approx \frac{19 + 20.8}{2} = 19.9$

由於 $k$ 必須為正整數，故當 $k = 20$ 時不等式首次成立，迴圈終止。

---

步驟二：關鍵迭代逐步追蹤驗證

• 第 $18$ 次迭代結束：

  • $n = 19$
  • $s = 1 + \frac{18 \times 19}{2} = 1 + 171 = 172$
  • 條件檢查：$s < 10 \times n \implies 172 < 190$（條件為 true，繼續執行）

• 第 $19$ 次迭代結束：

  • $n = 20$
  • $s = 1 + \frac{19 \times 20}{2} = 1 + 190 = 191$
  • 條件檢查：$s < 10 \times n \implies 191 < 200$（條件為 true，繼續執行）

核心觀念

本題考查電子郵件安全協定（S/MIME, Secure/Multipurpose Internet Mail Extensions）之密碼演算法規範等級，出自網路安全經典教材（如 William Stallings 的《Cryptography and Network Security》）。

S/MIME 為確保不同廠商與用戶端之間的互通性（Interoperability），定義了各類密碼演算法（如對稱加密、數位簽章、雜湊函數、金鑰交換等），並引用網際網路標準（RFC 2119）以特定關鍵字來規範實作的「需求等級（Requirement Levels）」：

1. MUST（必須支援）：所有符合 S/MIME 規範的實作絕對必須支援該演算法，以確保所有用戶端之間具備最基本的跨平台互通能力（例如過往標準中的 SHA-1、Triple-DES，或現代標準中的 SHA-256、AES-128 CBC）。
2. SHOULD（建議支援）：所有實作強烈建議支援該演算法，除非有極特殊考量（如法規限制或硬體極端受限），否則應盡量實作以提高互通性與相容性。

---

解題方法

在 S/MIME 標準文件（如 RFC 3851、RFC 5751、RFC 8551）以及標準教材的章節敘述中，明確指出：

「S/MIME cryptographic algorithms use SHOULD and MUST to specify the requirement level.」

因此解題切入點在於識別 RFC 規範標準與資安教材中用來標註演算法相容性最低底線與推薦層級的正式關鍵字：

• MUST 代表最低實作底線（強制要求）。

核心觀念

本題測驗「無線區域網路（WLAN）」的標準組織、通訊協定與商業認證商標：

1. IEEE 802.11 家族：由 IEEE 制定之無線區域網路標準，其中 IEEE 802.11b 於 1999 年推出，運作於 $2.4\text{ GHz}$ ISM 頻段，最高傳輸速率可達 $11\text{ Mbps}$。
2. Wi-Fi 聯盟（Wi-Fi Alliance）：由業界廠商組成的非營利組織（前身為 WECA, Wireless Ethernet Compatibility Alliance），專門針對符合 IEEE 802.11 標準的產品進行互通性測試與認證，通過認證的商品即冠上 Wi-Fi（Wireless Fidelity）商標。最初正是針對 802.11b 產品推行此項認證商標。

---

解題方法

題目詢問「用於代表通過認證之 802.11b 產品的術語」。

• IEEE 負責制定的是「底層技術與通訊協定規範」（802.11、802.11b、802.11a、802.11g 等）。
• 然而，不同廠商生產的 802.11b 設備可能存在相容性問題，因此 Wi-Fi 聯盟建立了認證制度，凡通過互通性相容測試的 802.11b 產品，即可標上 Wi-Fi Certified 標籤。
• 題幹明確指稱「certified 802.11b products」，切入點為識別代表該認證商標的名詞，即為 Wi-Fi。

---

選項分析

• (A) WAP（錯誤）
  • Wireless Application Protocol（無線應用協定）：用於早期的行動裝置（如 2G/2.5G 手機）存取網際網路之應

核心觀念

本題考查 IEEE 802 參考模型（IEEE 802 Reference Model） 與 OSI 七層模型（OSI 7-Layer Model） 之對應架構與各層職責：

1. IEEE 802 與 OSI 模型的對應關係：
   • OSI 實體層（Physical Layer）$\Leftrightarrow$ IEEE 802 實體層（Physical Layer）。
   • OSI 資料鏈結層（Data Link Layer, DLL）在 IEEE 802 模型中被進一步細分為兩個子層：
     • 邏輯鏈結控制子層（Logical Link Control, LLC）：對應 IEEE 802.2，處理流量控制、錯誤偵測與向網路層的介面服務。
     • 介質存取控制子層（Medium Access Control, MAC）：對應 IEEE 802.3（以太網路）、802.11（Wi-Fi）等，負責實體定址（MAC 位址）、訊框封裝/拆封與共用傳輸媒介的存取控制（如 CSMA/CD、CSMA/CA）。
2. 實體層（Physical Layer）的核心職責：
   • 負責在傳輸媒介上進行「原始位元串流（Raw Bit Stream）」的傳輸與接收（Bit transmission and reception）。
   • 負責訊號的編碼與解碼（Encoding and Decoding of signals，例如曼徹斯特編碼、4B/5B、NRZ 等）。
   • 規範電氣特性、機械介面、光學規格及位元同步（Bit synchronization）。

---

解題方法

題幹關鍵字為：

• encoding and decoding of signals（訊號之編碼與解碼）
• bit transmission and reception（位元的傳輸與接收）

在網路通訊模型中，資料是以「訊框（Frame）」存在於資料鏈結層（包含 LLC 與 MAC），只有進入最底層的**實體層（Physical Layer）**時，才會將訊框轉化為「位元（Bit）」並透過編碼機

核心觀念

本題考核**進位制轉換（Radix Conversion）**中帶有小數點的數值轉換：

1. 二進位轉十進位（Binary to Decimal）：採用加權展開法（Positional Weight Expansion）。對於基底為 $2$ 的數值，小數點左側權重依序為 $2^0, 2^1, 2^2, \dots$；小數點右側權重依序為 $2^{-1}, 2^{-2}, 2^{-3}, \dots$。
2. 十進位小數轉二進位（Decimal Fraction to Binary）：採用乘二取整法（Successive Multiplication by 2）。將純小數部分連續乘 $2$，每次取得的整數部分即為二進位小數依序排列的位元（從高位 $2^{-1}$ 往低位排列），直到小數部分為 $0$ 或出現循環為止。

---

解題方法與詳細步驟

(a) 將二進位數 $(10.011)_2$ 轉換為十進位

解題切入點：直接以基底 $2$ 的位值加權展開，分別計算整數與小數部分後相加。

展開式如下：

$$(10.011)_2 = 1 \times 2^1 + 0 \times 2^0 + 0 \times 2^{-1} + 1 \times 2^{-2} + 1 \times 2^{-3}$$

分項計算：

• 整數部分： $$1 \times 2^1 + 0 \times 2^0 = 2 + 0 = 2$$
• 小數部分： $$0 \times \frac{1}{2} + 1 \times \frac{1}{4} + 1 \times \frac{1}{8} = 0 + 0.25 + 0.125 = 0.375$$

相加合併：

$$2 + 0.375 = 2.375$$

---

(b) 將十進位數 $(0.01)_{10}$ 轉換為二進位

解題切入點：使用「乘二取整法」，依序提取整數部分。

計算過程如下：

1. $0.01 \times 2 = 0.02 \rightarrow$ 整數為 0，剩餘小數 $0.02$
2. $0.02 \times 2 = 0.04 \rightarrow$ 整數為 0，剩餘小數 $0.04$
3. $0.04 \times 2 = 0.08 \rightarrow$ 整數為 0，剩餘小數 $0.08$
4. $0.08 \times 2 = 0.16 \rightarrow$ 整數為 0，剩餘小數 $0.16$
5. $0.16 \times 2 = 0.32 \rightarrow$ 整數為 0，剩餘小數 $0.32$
6. $0.32 \times 2 = 0.64 \rightarrow$ 整數為 0，剩餘小數 $0.64$
7. $0.64 \times 2 = 1.28 \rightarrow$ 整數為 1，剩餘小數 $0.28$
8. $0.28 \times 2 = 0.56 \rightarrow$ 整數為 0，剩餘小數 $0.56$
9. $0.56 \times 2 = 1.12 \rightarrow$ 整數為 1，剩餘小數 $0.12$
10. $0.12 \times 2 = 0.24 \rightarrow$ 整數為 0，剩餘小數 $0.24$
11. $0.24 \times 2 = 0.48 \rightarrow$ 整數為 0，剩餘小數 $0.48$

核心觀念

本題考查兩種無失真資料壓縮方法適用的資料型態：

• Run-length encoding（游程編碼）：把連續重複的資料值，改記成「資料值＋重複次數」。
• Relative encoding（相對編碼／差分編碼）：不直接記錄每筆資料的完整值，而記錄它與前一筆資料的差值；解碼時由前一筆值逐步還原。

判斷哪種方法有效，重點是觀察資料中是否存在大量連續重複值，或相鄰資料值之間的差異是否很小。

解題方法與分析

(a) Run-length encoding

**最有效的條件：**資料中有許多長串的連續相同值。

例如，原始資料：

$$\text{AAAAAAABBBBCC}$$

可表示為：

$$\text{A}7,\ \text{B}4,\ \text{C}2$$

原資料需要記錄 13 個字元；游程編碼則只需記錄各字元及其連續次數。像是大片單色區域的點陣圖，常有連續相同的像素值，因此適合使用游程編碼。

核心觀念

本題測驗計算機系統中軟體的分類架構（Software Categories）。
軟體（Software）是一組指示電腦硬體執行特定任務的程式、程序與文件集合。在計算機概論的標準分類體系中，依據軟體與硬體的接近程度以及所服務的對象，主要可分為三大類別：

1. 系統軟體（System Software）：負責管理、協調底層硬體資源，並為其他軟體提供執行平台。
2. 應用軟體（Application Software）：直接協助使用者解決特定問題或完成特定工作任務。
3. 公用程式／系統工具（Utility Software / System Utilities） 或 程式開發軟體（Development Software / Programming Software）：
   • 傳統分類常將公用程式視為系統軟體的子類，而將「程式開發軟體」獨立為第三大類（系統軟體、應用軟體、開發軟體）。
   • 當代計概教科書（如 Peter Norton 等）亦常將「系統軟體、應用軟體、公用程式（Utility Software）」三者並列為三大主要分類。
   • 考場標準解法建議採「系統軟體（System Software）、應用軟體（Application Software）、公用程式（Utility Software）」或「系統軟體、應用軟體、程式開發軟體（Development Software）」架構作答，本解採最普遍通用的「系統軟體、應用軟體、公用程式」架構，並輔以開發工具補充。

---

解題方法

回答本申論題時，應採「定義 $\rightarrow$ 核心功能與特徵 $\rightarrow$ 具體實例（Specific Example）」三層結構逐一論述，論述層次分明且中英專有名詞對照，以展現答題專業度：

1. 系統軟體（System Software）

   • 定義與說明：系統軟體是直接與電腦硬體溝通的程式集合，負責控制硬體運作、管理系統資源（CPU 排程、記憶體管理、檔案系統、I/O 裝置驅動），並提供中介抽象層（Abstraction Layer）以支援上層應用軟體運作。
   • 核心特徵：通常隨開機載入，具有高執行權限（Kernel mode / 核心態），使用者通常不直接與其核心互動。
   • 具體實例：
     • 作業系統（Operating System）：例如 Microsoft Windows 11、Ubuntu Linux、macOS。
     • 裝置驅動程式（Device Drivers）：例如 NVIDIA 顯示卡驅動程式。

2. 應用軟體（Application Software）

   • 定義與說明：直接面向終端使用者（End-user），專為協助使用者處理特定事務、提高生產力或提供娛樂而設計的軟體。
   • 核心特徵：依賴系統軟體提供的環境執行於使用者模式（User mode），直接滿足業務、學術、個人娛樂等特定需求。
   • 具體實例：
     • 生產力工具（Productivity Tools）：例如 Microsoft Office Word、Excel。
     • 網頁瀏覽器（Web Browser）：例如 Google Chrome。

核心觀念

本題測驗 HTML（HyperText Markup Language，超文件標示語言）的基本文件結構與核心標籤語法。

1. HTML 文件的基本骨架：
   • 典型的 HTML 文件由根元素 <html>...</html> 包裹，內部主要分為兩個區段：
     • <head>...</head>：存放文件的元資料（Metadata），如編碼設定、網頁標題（<title>）、樣式表引用等，不會直接渲染在瀏覽器的可視畫面中。
     • <body>...</body>：包含所有要直接呈現在瀏覽器視窗畫面中的內容（如文字、圖片、表格、超連結等）。
2. 標籤成對性（Opening Tag 與 Closing Tag）：
   • 大多數 HTML 元素為成對出現的標籤，起始標籤（Opening tag）形式為 <tag>，結束標籤（Closing tag）形式為 </tag>，斜線 / 代表該元素的結束。
3. 常用內容標籤：
   • <p>...</p>：段落標籤（Paragraph），定義一個文字段落。
   • <a>...</a>：錨點標籤（Anchor），透過 href 屬性建立指向其他網頁或資源的超連結。

---

解題方法與小題分析

題目要求寫出達成指定功能的 HTML 標籤（HTML tag），請特別注意各小題指名的是起始標籤（Begins / Marks the beginning）還是結束標籤（Marks the end）。

(a) Begins the part that describes what will appear on the computer screen

• 功能說明：標示「即將呈現在電腦螢幕上的內容」的起始部分。
• 標籤對應：在 HTML 架構中，所有在瀏覽器視窗（網頁畫布）上視覺化呈現的元素，皆必須置於 <body> 與 </body> 之間。因此，定義此顯示區段開頭的起始標籤為 <body>。

核心觀念

本題測驗關聯式代數（Relational Algebra）中的兩大基本運算子：

1. 條件連接（Theta Join，$\bowtie_\theta$）：
   定義為先進行卡氏積（Cartesian Product，$\times$），再依指定條件 $\theta$ 進行選取（Selection，$\sigma_\theta$）： $$R \bowtie_\theta S = \sigma_\theta(R \times S)$$ 本題條件為 $X.A > Y.D$。
2. 投影（Projection，$\pi$）：
   自關聯表中選取指定的屬性（欄位），並在純關聯式代數（集合語意，Set Semantics）下自動濾除重複的元組（Tuples）： $$\pi_{A_1, A_2, \dots, A_k}(R)$$ 本題投影屬性為 $X.B$ 與 $Y.C$。

---

解題方法

步驟一：計算條件連接（Temp）

將關聯 $X$ 的每一筆元組與關聯 $Y$ 的每一筆元組進行配對，並檢驗條件 $X.A > Y.D$：

• 當 $X$ 的元組為 $(2, s)$ 時：
  • 配對 $Y$ 的 $(t, 1)$：$X.A = 2 > Y.D = 1$（成立，保留）
  • 配對 $Y$ 的 $(r, 3)$：$X.A = 2 > Y.D = 3$（不成立，捨棄）
  • 配對 $Y$ 的 $(w, 2)$：$X.A = 2 > Y.D = 2$（不成立，捨棄）
• 當 $X$ 的元組為 $(5, z)$ 時：
  • 配對 $Y$ 的 $(t, 1)$：$X.A = 5 > Y.D = 1$（成立，保留）
  • 配對 $Y$ 的 $(r, 3)$：$X.A = 5 > Y.D = 3$（成立，保留）
  • 配對 $Y$ 的 $(w, 2)$：$X.A = 5 > Y.D = 2$（成立，保留）

合併符合條件的元組，得到中間結果 Temp：

$A$	$B$	$C$	$D$
2	$s$	$t$	1
5	$z$	$t$	1

核心觀念

本題考查作業系統（Operating System）中 CPU 排程（CPU Scheduling） 與 循環分配法（Round-Robin Scheduling, RR） 的基礎概念：

1. 時間配額／時間片段（Time Slice / Time Quantum）：系統分配給單一行程連續使用 CPU 的最大時間長度。
2. 上下文交換時間（Context Switch Overhead）：從一個行程切換至另一個行程時作業系統儲存與回復狀態的時間。題目設定此時間可忽略不計（$0\text{ ms}$），代表時間片段切換之間無任何額外耗損。
3. 單位換算： $$1\text{ 秒 (s)} = 1000\text{ 毫秒 (ms)}$$
4. 行程提前放棄 CPU（Yield / I/O Blocking）：當行程在時間片段結束前因 I/O 等待或主動放棄 CPU 時，系統會立即排程下一個行程，其剩餘的時間片段會直接釋放給後續行程使用。

---

解題方法與推導

(a) 一秒內最多可有多少個行程取得時間片段？

• 切入點：在最一般的情況下，每個行程都用滿系統分配的時間片段（$10\text{ ms}$）。
• 計算步驟：
  已知總時間為 $1\text{ 秒} = 1000\text{ ms}$，每個時間片段長度為 $10\text{ ms}$，且上下文交換時間為 $0$： $$\text{可取得時間片段的行程數} = \frac{1000\text{ ms}}{10\text{ ms/process}} = 100\text{ 個行程}$$

(b) 若有一半的行程僅使用其時間片段的一半，一秒內可有多少個行程取得時間片段？

• 切入點：
  將取得時間片段的行程分為兩組：
  1. 第一組（佔一半）：用滿完整的時間片段，每個行程耗時 $10\text{ ms}$。
  2. 第二組（佔另一半）：僅使用時間片段的一半，每個行程耗時： $$\frac{10\text{ ms}}{2} = 5\text{ ms}$$
• 計算推導：
  設一秒內總共獲得時間片段的行程數為 $N$。
  • 用滿 $10\text{ ms}$ 的行程數量為 $\frac{N}{2}$。
  • 僅使用 $5\text{ ms}$ 的行程數量為 $\frac{N}{2}$。