112 年 國立臺灣大學圖書資訊系碩士班《電子計算機概論》

這題考驗對「演算法」(Algorithm) 基本定義的理解。演算法是解決問題的步驟描述，是電腦科學的基礎概念。

(A) 線性代數的方程式是數學的表達方式，不等於演算法。
(B) 演算法的標準定義就是解決問題的步驟描述，此選項完全符合。
(C) 流程圖的圖形選擇是演算法的一種視覺化表示工具，但本身不是演算法。
(D) 過濾軟體是演算法的應用，但演算法本身不只是過濾軟體。

這題考驗對「宣告式程式語言」(Declarative Programming Language) 的認知。宣告式程式語言著重於「是什麼」(what) 應達成，而非「如何」(how) 達成。

(A) C++ 是一種多範式程式語言，但主要被歸類為命令式 (Imperative) 程式語言，因為它描述了電腦執行的步驟。
(B) FORTRAN (Formula Translation) 是一種早期的高階程式語言，也屬於命令式程式語言。
(C) Pascal 是一種結構化程式語言，也是命令式程式語言。
(D) Prolog (Programming in Logic) 是一種邏輯程式語言，屬於宣告式程式語言的典型代表。它基於一階邏輯，使用者描述事實和規則，系統則透過邏輯推理來找出答案。

這題考驗對不同儲存媒體的存取方式（順序存取 Sequential Access vs. 隨機存取 Random Access）的理解。

(A) RAM (Random Access Memory) 顧名思義，是隨機存取記憶體，可以快速存取任何位置的資料。
(B) 光碟 (Optical Disk)，如 CD、DVD，是隨機存取媒體。讀寫頭可以移動到光碟上的任何軌道和扇區。
(C) 磁帶 (Tape) 是典型的順序存取媒體。要讀取磁帶上的某個資料，必須從頭開始按順序讀取，直到找到目標資料。
(D) 硬碟 (Hard Disk) 是隨機存取媒體。

核心觀念

本題測驗計算機結構中的**儲存階層（Memory/Storage Hierarchy）特性，特別是輔助儲存媒體（Secondary Storage / Tertiary Storage）在成本（Cost per Unit of Storage）與存取速度（Access Speed / Latency）**上的相對關係。

在計算機系統的儲存階層中，普遍遵循以下原則：

1. 速度越慢，每單位容量的成本越低（便宜）。
2. 速度越快，每單位容量的成本越高（昂貴）。

題目要求依照「成本由便宜到昂貴（from less expensive to more expensive）」且「速度由慢到快（from slower to faster）」排列下列四種儲存媒體：

• 磁帶（Magnetic Tape）：順序存取（Sequential Access），搜尋時間長、延遲最高（最慢），但單位容量儲存成本最低（最便宜），常用於大規模長期冷資料封存與備份。
• 軟碟（Floppy Disk）：早期的可移轉磁性儲存媒體，雖然具備直接存取（Direct/Random Access）能力，但由於主軸轉速極低（約 $300 \sim 360\text{ RPM}$）且磁頭尋道速度慢，其存取延遲高、頻寬極低。在容量效益上，其單位成本高於磁帶。
• 光碟（Compact Disc, CD）：光學儲存媒體，採用雷射聚焦讀取，轉速與存取速度快於軟碟機，但因光學讀取機構的機械定位時間，其隨機存取速度與傳輸速率仍顯著低於傳統硬碟。
• 傳統硬碟（Hard Disk Drive, HDD）：採用密封高速旋轉磁碟片（一般為 $5400 \sim 7200\text{ RPM}$ 甚至更高速）與高速音圈馬達（Voice Coil Actuator）磁頭臂，具備極佳的隨機存取能力與高傳輸頻寬，在四者中速度最快、機械構造最精密、每單位儲存成本最高。

解題方法

由題意可知，排列順序必須同時滿足兩個嚴格遞增的維度：
$\text{成本：最便宜 } \longrightarrow \text{ 最昂貴}$
$\text{速度：最慢 } \longrightarrow \text{ 最快}$

根據計算機概論中經典外部儲存媒體的階層比較：

1. 最慢且單位成本最低：磁帶（Tape）。磁帶受限於實體卷帶倒帶與快進，尋道時間以「秒」甚至「分」計算，是典型的近線（Near-line）或離線（Off-line）儲存媒體，存取速度敬陪末座，但單位儲存成本極為低廉。
2. 次慢：軟碟（Floppy Disk）。軟碟轉速低、容量極小（常見為 $1.44\text{ MB}$），隨機存取延遲動輒數百毫秒，傳輸速率僅約數十至數百 $\text{KB/s}$。

這題考驗對電腦發展歷史中各個世代主要技術的記憶。

電腦的發展通常被劃分為幾個世代，每個世代的劃分主要基於其核心電子元件的技術演進。

• 第一代 (First Generation, 約 1940s-1950s)： 使用真空管 (Vacuum Tubes) 作為主要的電子元件。體積龐大、耗電量高、容易故障、速度較慢。例如 ENIAC。
• 第二代 (Second Generation, 約 1950s-1960s)： 使用電晶體 (Transistors) 取代真空管。體積縮小、耗電量降低、速度加快、可靠性提高。
• 第三代 (Third Generation, 約 1960s-1970s)： 使用積體電路 (Integrated Circuits, ICs)，將多個電晶體整合在一個矽晶片上。進一步縮小體積、提高速度和可靠性。

這題考驗對不同搜尋演算法的理解，以及它們適用於哪種資料結構（有序或無序列表）。

• 二元搜尋 (Binary Search)：要求列表必須是有序的。它通過不斷將搜尋範圍縮小一半來快速找到目標。
• 順序搜尋 (Sequential Search)：也稱為線性搜尋 (Linear Search)。它從列表的第一個元素開始，逐個檢查直到找到目標或檢查完所有元素。這個方法適用於無序或有序的列表。
• 遞迴搜尋 (Recursive Search)：這不是一個特定的搜尋演算法名稱，而是指使用遞迴方式實現的搜尋。遞迴搜尋可以應用於各種搜尋演算法，例如遞迴版本的二元搜尋。
• 插值搜尋 (Interpolation Search)：是一種改進型的搜尋演算法，它比二元搜尋更有效率，但同樣要求列表是有序的。它根據目標值在列表中的可能位置來估計搜尋點。

核心觀念

本題考查作業系統中的「行程狀態轉換」。

行程（process）常見狀態包括：

• Ready（就緒狀態）：行程已具備執行條件，正在等待 CPU。
• Running（執行狀態）：行程目前正在 CPU 上執行。
• Waiting／Blocked（等待／阻塞狀態）：行程正在等待 I/O 或其他事件完成。
• Terminated（終止狀態）：行程已完成執行。

行程從 Ready 狀態進入 Running 狀態，代表作業系統進行排程後，將 CPU 分配給該行程。此動作稱為 dispatch（派遣）。

解題方法

題幹指出行程原本處於 Ready 狀態。此時行程已在記憶體中，且只差取得 CPU 即可執行。

狀態轉換如下：

因此，關鍵判斷是：哪個選項描述「行程取得 CPU 使用權」？

選項分析

(A) it enters memory

行程進入主記憶體，通常是由 New 狀態轉為 Ready 狀態的過程：

題目已說明行程目前在 Ready 狀態，因此「進入記憶體」不是 Ready 轉為 Running 的原因。此選項錯誤。

(B) it requests I/O

這題考驗對常見排序演算法時間複雜度的比較，以判斷哪個在「一般情況下」(in general) 最快。

排序演算法的速度通常用其時間複雜度來衡量，尤其是在最壞情況 (Worst Case) 和平均情況 (Average Case) 下。

• Bubble Sort (氣泡排序)：
  • 平均情況：$O(n^2)$
  • 最壞情況：$O(n^2)$
  • 穩定排序。
• Selection Sort (選擇排序)：
  • 平均情況：$O(n^2)$
  • 最壞情況：$O(n^2)$
  • 不穩定排序。
• Insertion Sort (插入排序)：
  • 平均情況：$O(n^2)$
  • 最壞情況：$O(n^2)$
  • 在幾乎有序的列表上表現很好，可達 $O(n)$。
  • 穩定排序。
• Heap Sort (堆積排序)：
  • 平均情況：$O(n \log n)$
  • 最壞情況：$O(n \log n)$
  • 不穩定排序。

這題考驗對網路模型（OSI 或 TCP/IP）中各層協議的認知，特別是傳輸層 (Transport Layer) 的協議。

OSI 模型將網路通訊劃分為七層，TCP/IP 模型則通常劃分為四層或五層。傳輸層在 OSI 模型中是第四層，在 TCP/IP 模型中是第三層（或稱為網路介面層之上）。傳輸層的主要功能是提供端到端 (end-to-end) 的通訊服務，例如可靠的資料傳輸、流量控制、壅塞控制等。

• TCP (Transmission Control Protocol)：是傳輸層最核心的協議之一。它提供可靠的、面向連接的 (connection-oriented) 資料傳輸服務。
• UDP (User Datagram Protocol)：是傳輸層另一個重要的協議。它提供不可靠的、無連接的 (connectionless) 資料傳輸服務，速度較快，但需要應用層來處理可靠性。
• SCTP (Stream Control Transmission Protocol)：也是一種傳輸層協議，它結合了 TCP 的可靠性和 UDP 的某些優點，提供更強大的功能，如多重傳輸 (multi-homing) 和多重串流 (multi-streaming)。

這題考驗對 OSI (Open Systems Interconnection) 參考模型的標準結構的記憶。

OSI 模型是一個概念模型，由國際標準化組織 (ISO) 制定，用於描述網路通訊系統的標準化方式。它將網路通訊的功能劃分為七個不同的層次，每一層都負責特定的任務，並與其上下層進行互動。

這七個層次，從上到下依序為：

1. 應用層 (Application Layer)：提供應用程式直接使用的網路服務。
2. 表示層 (Presentation Layer)：負責資料的格式轉換、加密解密、壓縮解壓縮。
3. 會話層 (Session Layer)：負責建立、管理和終止應用程式之間的會話（對話）。

這題考驗將十進位負數轉換為特定位元數的二進位表示法，包括符號位元與值 (Sign and Magnitude)、一補數 (One's Complement) 和二補數 (Two's Complement) 三種方式。

基本概念：

1. 位元寬度 (Bit Width)：題目指定為 16 bits。這表示我們將使用 16 個位元來表示這個數字。最高位元 (bit 15) 通常用作符號位元。
2. 十進位轉二進位：首先將絕對值 $|-123| = 123$ 轉換為二進位。
   $123 \div 2 = 61$ 餘 $1$
   $61 \div 2 = 30$ 餘 $1$
   $30 \div 2 = 15$ 餘 $0$
   $15 \div 2 = 7$ 餘 $1$
   $7 \div 2 = 3$ 餘 $1$
   $3 \div 2 = 1$ 餘 $1$
   $1 \div 2 = 0$ 餘 $1$
   從下往上讀取餘數，得到 $123_{10} = 1111011_2$。
3. 補足位元：由於要用 16 bits 表示，我們需要在前面補足零，使其成為 16 bits 的二進位數。$1111011_2$ 共有 7 bits。所以，16 bits 的表示是 $00000001111011_2$。

轉換方法：

(a) Sign and Magnitude (符號位元與值)
- 最高位元 (bit 15) 表示符號：0 表示正數，1 表示負數。
- 其餘位元 (bit 14 到 bit 0) 表示數字的絕對值。
- 數字 -123：
- 符號位元 (bit 15) 為 1 (負數)。
- 絕對值 $123$ 的 15 bits 二進位表示為 $0000001111011_2$ (因為 $123$ 是 7 bits，所以前面補 $15-7=8$ 個零)。
- 組合起來：$1 \ 0000001111011_2$
- 填入表格：
bit sequence 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
sign and magnitude: 1 0 0 0 0 0 0 1 1 1 1 0 1 1

(b) One's Complement (一補數)
- 對於正數，其一補數表示與 Sign and Magnitude 的絕對值部分相同。
- 對於負數，其一補數表示為將該數的絕對值二進位表示，逐位取反 (0 變 1，1 變 0)。
- 數字 -123：
- 先取絕對值 123 的 16 bits 二進位表示：$00000001111011_2$
- 將每一位取反：
$00000001111011_2 \rightarrow 11111110000100_2$
- 組合起來：$11111110000100_2$
- 填入表格：

這題考驗對 CPU 基本運作概念的理解：機器週期（指令週期）。

機器週期 (Machine Cycle) / 指令週期 (Instruction Cycle)

機器週期，又稱為指令週期，是中央處理單元 (CPU) 執行一條機器指令所需的時間。這個過程可以分解為一系列更小的、連續的步驟，這些步驟是 CPU 執行指令的基本操作單元。一個機器週期通常由數個時脈週期 (Clock Cycles) 組成，時脈週期是 CPU 內部時脈訊號的最小時間單位。

指令週期的主要階段：

1. 擷取 (Fetch)：

   • CPU 從記憶體 (或快取) 中讀取下一條要執行的指令。
   • 指令位址由程式計數器 (Program Counter, PC) 指定。
   • CPU 將 PC 的內容傳送給記憶體位址暫存器 (Memory Address Register, MAR)。
   • CPU 發出記憶體讀取指令。
   • 記憶體將指令內容傳送回資料暫存器 (Memory Data Register, MDR)。
   • MDR 的內容被複製到指令暫存器 (Instruction Register, IR)。
   • PC 的值會遞增，指向下一條指令。

2. 解碼 (Decode)：

   • CPU 的控制單元 (Control Unit) 解析指令暫存器 (IR) 中的指令。
   • 識別指令的操作碼 (Opcode)，以確定要執行的操作。

這題考驗對軟體開發生命週期 (SDLC) 中測試階段的理解，以及測試的不同方式。

軟體測試 (Software Testing)

軟體測試是軟體開發生命週期 (SDLC) 中一個至關重要的階段，其主要目的是評估軟體產品的品質，發現並修正其中的缺陷 (bugs)，確保軟體能夠滿足預期的需求和規格，並提供預期的用戶體驗。測試的目標是找出軟體中潛在的問題，而不是證明軟體沒有錯誤（這是不可能的），而是提高軟體的可信度和穩定性。

測試的各種方式：

軟體測試可以從不同的角度進行分類，以下是幾種常見的分類方式和具體的測試類型：

一、根據測試對象的層次分類：

1. 單元測試 (Unit Testing)：

   • 目的：測試軟體中最小的可測試單元，通常是函數 (function)、方法 (method) 或類別 (class)。
   • 執行者：通常由開發人員執行。
   • 優點：能夠在早期發現問題，成本較低，易於隔離和修復。

2. 整合測試 (Integration Testing)：

   • 目的：測試不同單元或模組組合在一起時的相互作用和介面。
   • 執行者：開發人員或專門的測試人員。
   • 方法：
     • 大爆炸整合 (Big Bang Integration)：將所有模組一次性整合測試。
     • 由上而下整合 (Top-Down Integration)：從頂層模組開始，逐步向下整合。
     • 由下而上整合 (Bottom-Up Integration)：從底層模組開始，逐步向上整合。
     • 三明治整合 (Sandwich Integration)：結合由上而下和由下而上方法。
   • 優點：能發現模組間的介面問題。

3. 系統測試 (System Testing)：

   • 目的：將整個軟體系統作為一個整體進行測試，驗證系統是否符合所有功能和非功能需求。
   • 執行者：通常由獨立的測試團隊執行。
   • 範圍：涵蓋功能性、效能、安全性、可靠性、可用性等方面。

4. 驗收測試 (Acceptance Testing)：

   • 目的：由最終用戶或客戶來驗證軟體是否滿足其業務需求和期望。
   • 執行者：最終用戶、客戶或其代表。
   • 類型：
     • 用戶驗收測試 (User Acceptance Testing, UAT)：由實際用戶執行。
     • 商業驗收測試 (Business Acceptance Testing, BAT)：驗證軟體是否符合商業目標。
     • 操作驗收測試 (Operational Acceptance Testing, OAT)：驗證軟體在實際操作環境中的可靠性和可維護性。

二、根據測試的目的和知識分類：

1. 黑箱測試 (Black-Box Testing)：
   • 方法：測試人員不關心軟體的內部結構和程式碼，僅根據軟體的規格和需求來設計測試案例。
   • 關注點：輸入與輸出之間的關係。

這題考驗對網際網路核心協議之一 IP (Internet Protocol) 的理解，包括其特性和功能。

IP (Internet Protocol) 的特性與功能

IP 是網際網路的核心協議，它工作在網路層 (Network Layer)，負責在不同的網路之間傳遞資料封包 (datagram)。IP 的設計哲學是「盡力而為」(best-effort)，這意味著它不保證封包的送達、順序或完整性，這些可靠性功能通常由上層協議（如 TCP）來實現。

IP 的主要特性：

1. 無連接 (Connectionless)：

   • IP 協議在傳送資料封包前，不需要像 TCP 那樣建立一個邏輯連接。每個 IP 封包都是獨立傳輸的，不依賴於先前或後續的封包。
   • 這使得 IP 具有高度的靈活性和效率，但也意味著 IP 本身不保證資料的可靠傳輸。

2. 不可靠 (Unreliable)：

   • IP 協議不提供資料傳輸的可靠性保證。這意味著 IP 協議本身不負責：
     • 封包遺失檢測與重傳：封包在傳輸過程中可能因網路擁塞、設備故障等原因丟失，IP 不會自動重傳。
     • 封包順序保證：封包可能因為網路路徑不同而以不同的順序到達目的地，IP 不會負責重新排序。
     • 重複封包檢測：IP 可能會因網路重傳機制而產生重複的封包，IP 不會自動剔除。
   • 這些可靠性機制通常由上層的 TCP 協議來實現。

3. 盡力而為 (Best-Effort)：

   • IP 協議會盡力將封包從源端傳送到目標端，但無法保證一定能成功送達。這類似於寄信，你把信寄出去，但無法保證對方一定能收到。

4. 位址分配 (Addressing)：

   • IP 使用 IP 位址 (IP Address) 來唯一標識網路上的每個裝置。
   • IP 位址是邏輯位址，可以在不同網路之間路由。
   • 目前主要有 IPv4 (32 位元) 和 IPv6 (128 位元) 兩種版本。

5. 路由選擇 (Routing)：

   • IP 協議負責將封包從源主機傳送到目標主機，即使它們位於不同的網路。
   • 路由器 (Routers) 根據 IP 位址和路由表 (Routing Table) 來決定封包的最佳傳輸路徑。

這題考驗對資料庫交易處理 (Transaction Processing) 中 ACID 特性之一「All-or-Nothing」的理解。

交易處理 (Transaction Processing) 與 All-or-Nothing 特性

在資料庫管理系統 (DBMS) 中，交易 (Transaction) 是指一個或一組相關的資料庫操作，這些操作必須被視為一個單一的、不可分割的工作單元。交易處理的目的是確保資料庫的一致性 (Consistency) 和完整性 (Integrity)。

All-or-Nothing 特性 (原子性 Atomicity)

「All-or-Nothing」是交易處理的四個 ACID 特性之一，其中 A 代表 Atomicity (原子性)。
原子性意味著一個交易中的所有操作都必須成功執行，或者所有操作都必須失敗（回滾），而不能出現部分成功、部分失敗的情況。交易要么完整地完成（All），要么完全不執行（Nothing）。

• 如果交易中的所有操作都成功執行：則稱該交易被「提交」(Commit)，其所做的所有更改都會被永久地寫入資料庫。
• 如果交易中的任何一個操作失敗（例如，由於資料約束違反、系統崩潰、硬體故障、網路中斷等原因）：則整個交易會被「中止」(Abort) 或「回滾」(Rollback)。所有在該交易過程中對資料庫所做的更改都會被撤銷，使資料庫恢復到交易開始之前的狀態，就好像這個交易從未發生過一樣。

目的：
原子性確保了資料庫操作的完整性，防止了資料庫處於一個不一致的、部分更新的狀態。這對於維護資料的準確性和可靠性至關重要。

舉例說明：

假設有一個銀行帳戶轉帳的操作，從帳戶 A 轉帳 1000 元到帳戶 B。這個轉帳操作通常包含兩個基本步驟，必須作為一個單一交易來處理：

1. 步驟 1 (扣款)：從帳戶 A 的餘額中減去 1000 元。
2. 步驟 2 (存款)：向帳戶 B 的餘額中增加 1000 元。

現在我們看看 All-or-Nothing 如何應用於這個場景：

• 情況一：交易成功 (All)
  • 步驟 1：帳戶 A 的餘額成功減少 1000 元。
  • 步驟 2：帳戶 B 的餘額成功增加 1000 元。