108 年 國立政治大學數位內容碩士學位學程資訊技術組《計算機概論與程式設計》

第 1 大題：單選題詳解（共 6 小題）

---

(1) Which of the following statements is wrong?

• 核心觀念：
  計算機系統的可靠度（Reliability）與可用度（Availability）度量指標。

  • MTTF（Mean Time To Failure，平均無故障時間）：系統或組件從正常運作到發生故障的平均時間。
  • MTTR（Mean Time To Repair，平均修復時間）：發生故障後至修復完成回到正常運作的平均時間。
  • MTBF（Mean Time Between Failures，平均故障間隔時間）：$MTBF = MTTF + MTTR$。
  • 可用度（Availability）：系統處於可用運作狀態的時間比例，定義公式為： $$Availability = \frac{MTTF}{MTTF + MTTR}$$

• 選項分析：

  • (a) 正確：單一元件損壞（Component failure）若系統具有容錯（Fault tolerance）或冗餘備援（Redundancy，例如 RAID、雙電源供應），不一定會導致整個系統癱瘓（System failure）。
  • (b) 正確：MTTR 即代表 Mean Time To Repair（平均修復時間）。
  • (c) 錯誤：由可用度公式可知，欲提高可用度（Availability），必須增加 MTTF（拉長正常運作時間）或減少 MTTR（縮短維修時間）。選項敘述「reduce MTTF or increase MTTR」與正確方向完全相反。
  • (d) 正確：根據可靠度工程定義，提升 MTTF 的三大關鍵手段包含：故障避免（Fault avoidance）、容錯設計（Fault tolerance）以及故障預測（Fault forecasting）。

• 解題技巧：
  可用度即「可用時間佔總時間的比例」。想讓系統常常可用，直觀上必須「故障修得快（MTTR 越小越好）」且「撐得久不壞（MTTF 越大越好）」。

• 【答案】：(c)

---

(2) Which of the following statement is true?

• 核心觀念：
  計算機組織中的管線化（Pipelining）架構特性、效能衡量指標與冒險（Hazards）處理。

  • 管線化利用指令重疊執行來提升指令吞吐量（Instruction Throughput），但對單一指令的執行延遲（Latency / Execution time）並不會減少，甚至可能因為管線暫存器延遲而略微增加。
  • 管線深度（Pipeline Depth）增加，代表管線級數變多，分支預測錯誤的懲罰（Branch penalty）與資料相依（Data dependency）造成的暫停週期（Stall cycles）影響隨之放大。
  • 前瞻傳遞（Forwarding / Bypassing）是用來解決資料冒險（Data Hazard）的核心硬體技術；控制冒險（Control Hazard）則依賴分支預測（Branch prediction）、延遲轉移（Delayed branch）或清空管線（Flushing）。

• 選項分析：

  • (a) 錯誤：Pipelining 能提升吞吐量（Throughput），但無法減少單一指令的完成時間（Latency）。
  • (b) 錯誤：多週期（Multi-cycle）實作因不同週期可分時共用硬體，允許可使用單一記憶體（Unified memory）存放指令與資料，但並非「強制必須（requires）」只能使用單一記憶體；若架構採用哈佛架構（分開的 Instruction/Data Memory）亦可實作多週期。此處敘述過於絕對且非 Multi-cycle 的定義本質。
  • (c) 正確：管線越深（Depth 越大），指令之間重疊階段越多，分支判斷與寫回的級數差拉大，使得各種 Hazards（特別是 Branch Penalty 與 Load-Use Stall）所損失的 Clock cycles 增加，即增加冒險的衝擊。
  • (d) 錯誤：Forwarding 是用來解決資料冒險（Data Hazard），而非控制冒險（Control Hazard）。

• 解題技巧：
  牢記兩大對比：

  1. Forwarding $\rightarrow$ Data Hazard。
  2. Pipelining 改善 Throughput，但不改善（甚至稍微增加）Latency。

• 【答案】：(c)

---

(3) Which of the following statement is true?

• 核心觀念：
  多媒體資料表示法與壓縮格式。

  • 失真壓縮（Lossy Compression）：利用人類視覺或聽覺心理感知極限去除冗餘資訊，壓縮率高但無法無失真還原（如 JPEG、MP3、MPEG）。
  • 無失真壓縮（Lossless Compression）：解壓縮後能 100% 還原原始資料（如 PNG、GIF、FLAC、ZIP）。
  • 像素（Pixel, Picture Element）：數位影像組成的最小基本單元。
  • DPI（Dots Per Inch）：每英吋點數，主要衡量列印或印刷解析度；螢幕顯示器的解析度規格通常以總像素量（如 $1920 \times 1080$）或 PPI（Pixels Per Inch）表示。

• 選項分析：

  • (a) 錯誤：標準 JPEG（Joint Photographic Experts Group）採用離散餘弦轉換（DCT）與量化，屬於失真壓縮（Lossy compression）。
  • (b) 錯誤：MP3（MPEG-1 Audio Layer III）利用心理聲學模型去除人耳不敏感的頻率，屬於失真壓縮（Lossy compression）。
  • (c) 正確：Pixel（像素）為二維數位點陣影像中不可再分割的最小取樣單位（Smallest addressable unit）。
  • (d) 錯誤：DPI（Dots Per Inch）主要用於印表機/印刷品的物理輸出解析度；顯示器使用 PPI（Pixels Per Inch）或原生像素維度（Pixel resolution）。

(7) Which of the following statement is true?

核心觀念

本題考查不同軟體技術在系統架構中的角色：

• Persistence technology：負責資料持久化，使資料在程式結束或系統重啟後仍能保存。
• Front-end technology：在使用者端瀏覽器執行。
• Back-end technology：在伺服器端執行，處理資料、商業邏輯與 API。

選項分析

• (a) MongoDB is a persistence technology：正確。
  MongoDB 是文件導向資料庫，能將資料持久儲存在磁碟中，因此屬於資料持久化技術。

• (b) jQuery is a back-end technology：錯誤。
  jQuery 是 JavaScript 函式庫，主要在瀏覽器端執行，屬於前端技術。

• (c) Express.js is client-end technology：錯誤。
  Express.js 是建立在 Node.js 上的伺服器端 Web framework，主要用於撰寫後端 API 與路由處理。

• (d) None of the above：錯誤。
  (a) 已經是正確敘述，因此不能選此項。

解題技巧

看到 MongoDB、MySQL、PostgreSQL 等資料庫，通常可聯想到資料持久化；看到 jQuery，則應聯想到瀏覽器端前端開發；Express.js 則屬於 Node.js 後端生態系。

【答案】(a)

---

(8) What is $(-128)_{10}$ in two's complement?

核心觀念

$n$ 位元二補數的表示範圍為：

$$-2^{n-1} \leq x \leq 2^{n-1}-1$$

題目選項皆為 8 位元，因此範圍為：

$$-2^7 \leq x \leq 2^7-1$$ $$-128 \leq x \leq 127$$

因此 $-128$ 正好是 8 位元二補數的最小值。

解題方法

在 8 位元二補數中：

$$128_{10}=10000000_2$$

二補數的最小負數 $-128$ 直接表示為：

$$10000000_2$$

也可由二補數規則理解：

1. $+128$ 無法以 8 位元有號二補數表示。
2. 8 位元中，符號位為 $1$，其餘位元為 $0$ 的特殊形式即代表 $-128$。

選項分析

• (a) 01111111：錯誤。
  符號位為 $0$，代表正數 $127$。

• (b) 11111111：錯誤。
  其值為 $-1$。

• (c) 10000000：正確。
  其值為 8 位元二補數的最小值 $-128$。

• (d) 11111110：錯誤。
  其值為 $-2$。

解題技巧

記住 8 位元二補數的兩個邊界：

$$01111111=127,\qquad 10000000=-128$$

【答案】(c)

---

(9) Which of the following statement is false?

核心觀念

本題考查快取記憶體（cache）與虛擬記憶體（virtual memory）的寫入策略：

• Write-through：資料寫入 cache 的同時，也立即寫入主記憶體。
• Write-back：資料先只更新 cache，等該 cache block 被替換時，若標記為 dirty，才寫回主記憶體。
• Write buffer：暫存尚未完成寫入主記憶體的資料，以降低 CPU 等待時間。
• Cache miss：所需資料不在 cache 中，必須從較低層記憶體載入。

選項分析

• (a) It makes no sense to implement a write-through scheme in a Virtual memory：正確。
  虛擬記憶體的低層儲存通常是磁碟或 SSD，速度遠低於主記憶體。若每次寫入都立即同步到磁碟，會造成極大的效能負擔，因此虛擬記憶體通常採用類似 write-back 的延後寫回策略。

• (b) On a data cache miss, the system first stalls the CPU pipeline, fetches data in memory, and restart instruction fetch：錯誤。
  data cache miss 發生時，CPU 會暫停或等待管線，從較低層記憶體載入資料，接著重新執行被中斷的指令或重新嘗試資料存取。正確描述應是恢復該指令的執行，不是重新開始 instruction fetch。

• (c) Write back refers to on data-write hit, just update the block in cache and write back to memory when a dirty block is replaced：正確。
  這正是 write-back cache 的定義。寫入命中時只更新 cache block，並將 dirty bit 設為 $1$；該 block 被替換時才寫回主記憶體。

• (d) In order to reduce the operation time of a write-through cache, a write buffer is used to hold data waiting to be written to memory：正確。
  write-through 每次寫入都必須同步更新主記憶體，若 CPU 等待寫入完成會降低效能。write buffer 可暫存資料，讓 CPU 先繼續執行。

解題技巧

看到「cache miss」時，標準流程是：

$$\text{暫停管線} \rightarrow \text{從低層記憶體載入 block} \rightarrow \text{更新 cache} \rightarrow \text{重新執行原指令}$$

【答案】(b)

---

(10) Which of the following is not a video container format?

核心觀念

影片檔案通常包含兩個不同層次：

• Container format（容器格式）：負責封裝影像、聲音、字幕與 metadata，例如 MP4、AVI、Ogg。
• Video codec（視訊編碼格式）：負責壓縮與解壓縮影像資料，例如 H.264、H.265、AV1。

選項分析

• (a) H.264：正確答案。
  H.264 是視訊編碼標準，不是容器格式。

• (b) MP4：錯誤。
  MP4 是常見的影片容器格式，可封裝 H.264 影像與 AAC 聲音。

• (c) AVI：錯誤。
  AVI 是 Microsoft 制定的影片容器格式。

• (d) Ogg：錯誤。
  Ogg 是多媒體容器格式，可封裝影像、聲音等資料。

解題技巧

核心觀念： 遞迴 (Recursion) 與迭代 (Iteration) 的轉換，以及最大公因數 (Greatest Common Divisor, GCD) 的歐幾里得演算法。

題目要求： 將給定的遞迴函數 greatest_common_divisor 改寫為迭代形式。

遞迴函數分析：
這個遞迴函數實現的是計算最大公因數的一種方法，基於歐幾里得演算法的一個變種：

• 如果 a > b，則 GCD(a, b) = GCD(a-b, b)。
• 如果 b > a，則 GCD(a, b) = GCD(a, b-a)。
• 如果 a == b，則 GCD(a, b) = a (或 b)。

這個過程會不斷減小 a 或 b 的值，直到兩者相等為止，此時的相等值就是它們的最大公因數。

迭代改寫思路：
遞迴函數的本質是通過重複執行相同的邏輯（減法和比較）直到滿足終止條件。迭代就是使用迴圈（如 while 或 for）來實現這種重複。

1. 終止條件： 遞迴的終止條件是 a == b。迭代也需要一個迴圈，該迴圈在 a != b 時繼續執行，並在 a == b 時終止。
2. 迴圈體： 在迴圈內部，我們需要執行與遞迴函數中相同的邏輯：
   • 如果 a > b，我們需要將 a 更新為 a - b。
   • 如果 b > a，我們需要將 b 更新為 b - a。
3. 返回值： 當迴圈終止時（即 a == b），變數 a (或 b) 就包含了最大公因數。

迭代函數實作：
我們可以使用一個 while 迴圈，只要 a 不等於 b，就繼續執行。

unsigned greatest_common_divisor_iterative (unsigned a, unsigned b) {
    // 當 a 和 b 不相等時，持續進行減法操作
    while (a != b) {
        // 如果 a 大於 b，則將 a 減去 b
        if (a > b) {
            a = a - b;
        }
        // 否則 (b 大於 a)，將 b 減去 a
        else { // b > a
            b = b - a;
        }
    }
    // 當 a 等於 b 時，迴圈終止，此時 a (或 b) 就是最大公因數
    return a;
}

程式碼解釋：

• unsigned greatest_common_divisor_iterative (unsigned a, unsigned b): 定義一個新的函數，接受兩個無符號整數 a 和 b 作為輸入。
• while (a != b): 設定迴圈條件，只要 a 和 b 的值不相等，迴圈就會繼續執行。
• if (a > b): 判斷 a 和 b 的大小。
• a = a - b;: 如果 a 大於 b，則根據歐幾里得演算法的原理，將 a 的值更新為 a - b。

核心觀念： 非同步 (Asynchronous) 程式設計，特別是 Node.js 中的事件循環 (Event Loop) 與 I/O 操作的處理。

程式碼分析：
這段程式碼使用了 Node.js 的 fs (File System) 模組來進行檔案的寫入 (writeFile) 和讀取 (readFile)。這兩個操作都是非同步的，意味著它們會立即啟動，但不會阻塞主執行緒。當這些 I/O 操作完成時，它們會將相應的回呼函式 (callback function) 加入到事件佇列 (event queue) 中，等待事件循環 (event loop) 執行。

程式碼的執行流程如下：

1. const fs = require("fs");：載入 fs 模組。
2. let john = { ... };：定義一個 JavaScript 物件 john。
3. fs.writeFile('john.json', JSON.stringify(john), function() { console.log('A'); });：
   • 啟動非同步的檔案寫入操作。
   • 它會將 john 物件轉換為 JSON 字串，然後寫入到 john.json 檔案中。
   • 這個操作需要時間，但它不會等待寫入完成。
   • 當寫入完成後，傳遞的回呼函式 function() { console.log('A'); } 會被加入到事件佇列中。
4. fs.readFile('john.json', function(data) { console.log('B'); });：
   • 啟動非同步的檔案讀取操作。
   • 它會嘗試讀取 john.json 檔案。
   • 這個操作也需要時間，但它不會阻塞主執行緒。
   • 當讀取完成後，傳遞的回呼函式 function(data) { console.log('B'); } 會被加入到事件佇列中。
   • 重要提示： 由於 fs.writeFile 啟動在 fs.readFile 之前，並且檔案寫入需要時間，fs.readFile 在執行時，john.json 文件可能還沒有完全寫入完成（或者根本還沒開始寫入）。在實際運行中，fs.readFile 的行為取決於檔案系統的緩衝和操作系統的排程。

核心觀念： WebAssembly (Wasm) 的特性、優勢與應用。

題目解析：
題目首先介紹了 WebAssembly 的基本定義：一種基於堆疊式虛擬機的二進位指令格式，設計用於嵌入瀏覽器，並且是各種高階程式語言的可移植編譯目標。然後要求回答兩個問題：WebAssembly 的關鍵優勢，以及一個基於 Wasm 實現起來較容易，但在 Wasm 出現前難以實現的應用場景。

(1) WebAssembly 的關鍵優勢：

根據題目描述和 WebAssembly 的普遍認知，其關鍵優勢包括：

• 高性能 (High Performance): Wasm 以二進位格式存在，相較於 JavaScript 的文字格式，解析和執行速度更快，接近原生程式碼的效能。它被設計為可以被 JIT 編譯成高效的機器碼。
• 可移植性 (Portability): Wasm 是一種標準化的二進位指令格式，可以在任何支援 Wasm 的環境（主要是現代瀏覽器，但也包括伺服器端如 Node.js、WASI 等）中運行，與底層硬體和作業系統無關。
• 安全隔離 (Security Isolation): Wasm 在瀏覽器環境中運行時，受到嚴格的沙盒 (sandbox) 保護，無法直接訪問主機系統資源，只能透過 JavaScript API 與環境互動，確保了安全性。
• 多語言支援 (Multi-language Support): 題目中提到「compilation of any high-level programming language」。這意味著開發者可以使用 C, C++, Rust, Go, C#, Python 等多種語言編寫程式碼，然後編譯成 Wasm 在瀏覽器中運行，無需重寫。這極大地擴展了網頁應用的開發可能性。
• 代碼復用 (Code Reuse): 允許將現有的桌面應用、遊戲引擎、函式庫等（通常用 C/C++ 編寫）移植到網頁上，實現跨平台運行。

總結關鍵優勢： 綜合以上幾點，「高性能」 和 「多語言支援/程式碼復用」 是最核心的優勢。特別是高性能，這是 Wasm 進入瀏覽器並與 JavaScript 協同工作的最大動機。

(2) 基於 WebAssembly 的應用場景（Wasm 出現前難以實現）：

在 WebAssembly 出現之前，瀏覽器中的 JavaScript 雖然功能強大，但在處理計算密集型任務時，效能是一個瓶頸。例如，需要大量數學運算、複雜的圖像處理、音訊/視訊編解碼、3D 渲染、遊戲引擎等。

應用場景提議： 高性能的瀏覽器端遊戲、複雜的影音編輯工具、科學計算模擬、CAD 軟體、甚至是運行部分桌面級應用。

以「瀏覽器端 3D 遊戲引擎」為例進行說明：

• Wasm 出現前（僅依賴 JavaScript）：
  • 開發高性能的 3D 遊戲，需要在瀏覽器中進行大量的幾何計算、物理模擬、著 તન (shader) 處理、場景管理等。
  • JavaScript 雖然有 JIT 編譯，但其動態類型、垃圾回收機制等，在處理大規模、高頻率的運算時，效能不如 C++ 等原生語言。
  • 要實現接近桌面級的 3D 遊戲體驗，JavaScript 的效能往往不足以支撐複雜的渲染管線和物理引擎，開發者可能需要大量優化 JavaScript 代碼，或者使用 WebGL API 但底層計算仍然受限。
  • 移植現有的 C++ 遊戲引擎（如 Unreal Engine, Unity 的部分功能）到網頁上非常困難，因為需要將 C++ 代碼完全重寫成 JavaScript，這工作量巨大且效能損失難以接受。

核心觀念： 演算法的時間複雜度分析。

題目要求計算四個不同操作或演算法的時間複雜度：Mergesort 的最壞情況、Insertion Sort 的平均情況、Heapsort 的最壞情況，以及刪除整個循環鏈結串列的操作。

時間複雜度表示法： 我們通常使用大 O 符號 ($O(\cdot)$) 來表示時間複雜度，它描述了演算法執行時間隨輸入規模 $n$ 增長而增長的趨勢。

(1) Worst case of Mergesort (合併排序的最壞情況時間複雜度):

• Mergesort (合併排序) 是一種分治 (Divide and Conquer) 演算法。它的基本思想是：
  1. 將列表分成兩半。
  2. 遞迴地對兩半進行排序。
  3. 將兩個已排序的半部分合併成一個已排序的列表。
• 合併 (Merge) 操作： 合併兩個已排序的列表需要線性時間，即 $O(k+l)$，其中 $k$ 和 $l$ 是兩個列表的大小。
• 遞迴關係： 設 $T(n)$ 為排序 $n$ 個元素的 Mergesort 所需時間。則 $T(n) = 2T(n/2) + O(n)$。
• 時間複雜度： 使用主定理 (Master Theorem) 或遞迴樹法 (Recursion Tree Method) 分析，可以得出 Mergesort 的時間複雜度在所有情況下（最好、平均、最壞）都是 $O(n \log n)$。這是因為每次遞迴都會將問題規模減半，而合併步驟始終是線性的。
• 【答案】$O(n \log n)$

(2) Average case of Insertion Sort (插入排序的平均情況時間複雜度):

• Insertion Sort (插入排序) 是一種簡單的排序演算法，它通過將元素逐個插入到已排序的序列中的正確位置來完成排序。
• 操作： 對於列表中的第 $i$ 個元素，它需要與前面 $i-1$ 個元素進行比較和可能的交換，直到找到正確的位置。
• 最好情況： 當列表已經排序時，每個元素只需與前一個元素比較一次，時間複雜度為 $O(n)$。
• 最壞情況： 當列表完全逆序時，第 $i$ 個元素需要與前面所有 $i-1$ 個元素比較，總比較次數和交換次數為 $1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}$，時間複雜度為 $O(n^2)$。
• 平均情況： 在隨機順序的輸入下，平均需要比較和移動的元素數量約為總數的一半。因此，平均情況下的時間複雜度與最壞情況相同。