109 年 國立臺灣大學地質科學系碩士班應用地質組《計算機概論（B）》

本大題共考 31 個名詞解釋，每個名詞 2 分，總計 62 分。此題主要在測試考生對計算機科學基礎知識的廣度與深度。以下將逐一解釋：

(1) disk formatting:

• 全名/定義: 硬碟格式化 (Disk Formatting) 是指在硬碟上建立檔案系統的過程。它會初始化磁碟，將其分割成磁區 (sectors) 和磁軌 (tracks)，並建立檔案系統結構，以便作業系統可以儲存和讀取檔案。
• 目的: 準備新的硬碟供作業系統使用，或清除舊的檔案系統並建立新的。
• 應用: 在安裝作業系統前，或在重新分割磁碟、清除資料時。
• 範例: 使用 Windows 的「格式化」工具，選擇 FAT32 或 NTFS 檔案系統來格式化一個新的 USB 隨身碟。

(2) XOR operation:

• 全名/定義: 異或運算 (Exclusive OR, XOR) 是一種邏輯運算，當兩個輸入值不同時，輸出為真 (1)；當兩個輸入值相同時，輸出為假 (0)。
• 目的: 用於位元操作、加密、錯誤檢測等。
• 應用: 密碼學 (如 One-Time Pad)、無暫存器交換兩個數值、偵測傳輸錯誤。
• 數學式: $A \oplus B = (A \land \neg B) \lor (\neg A \land B)$。真值表：

  A	B	A XOR B
  0	0	0
  0	1	1
  1	0	1
  1	1	0

• 範例: 1011 XOR 1100 = 0111。

(3) interrupt:

• 全名/定義: 中斷 (Interrupt) 是一種由硬體或軟體發出的訊號，指示 CPU 暫停目前正在執行的任務，並處理一個優先級更高的事件。
• 目的: 讓 CPU 能對外部事件（如鍵盤輸入、網路封包到達）或內部事件（如除以零）做出即時反應，而不必持續輪詢 (polling)。
• 應用: 鍵盤輸入、滑鼠移動、定時器到期、I/O 設備完成操作、程式錯誤。
• 範例: 當使用者按下鍵盤時，鍵盤控制器會產生一個中斷訊號，CPU 暫停當前工作，跳到鍵盤中斷處理程序，讀取按鍵資訊，然後恢復原工作。

(4) CUDA: Compute-Unified Device Architecture:

• 全名/定義: CUDA 是一種由 NVIDIA 開發的平行運算平台和應用程式介面 (API) 模型。它允許軟體開發人員使用 NVIDIA GPU 進行通用目的的計算。
• 目的: 利用 GPU 的強大並行處理能力來加速計算密集型應用。
• 應用: 高效能運算 (HPC)、科學模擬、深度學習、影像處理、密碼破解。
• 範例: 使用 CUDA 加速訓練神經網路模型，或進行天氣預報的複雜模擬。

(5) LRU: Least Recently Used:

• 全名/定義: 最近最少使用 (Least Recently Used, LRU) 是一種快取替換策略。當快取滿了需要載入新資料時，LRU 策略會移除最近最少被存取到的項目。
• 目的: 最大化快取命中率 (cache hit rate)，假設最近使用的資料在未來也可能被再次使用。
• 應用: 作業系統的頁面替換演算法、CPU 快取記憶體管理、網頁伺服器快取。
• 範例: 在一個只有 3 個快取槽的系統中，若訪問順序為 A, B, C, A, D，當訪問 D 時，LRU 會替換掉 C，因為 C 是在 A 和 B 之後被訪問，且是最後一個被訪問的。

(6) machine language:

• 全名/定義: 機械語言 (Machine Language) 是電腦 CPU 能直接理解和執行的最低階程式語言。它由二進位碼 (0 和 1) 組成，對應於電腦硬體的指令集架構 (ISA)。
• 目的: 指示 CPU 執行特定操作，如加法、載入資料、跳轉等。
• 應用: 系統啟動的引導載入程式 (bootloader)、極度效能要求的程式片段、嵌入式系統的底層控制。
• 範例: 一段二進位碼，如 10110000 01100001，可能代表將數值 97 (ASCII 'a') 載入到一個特定的 CPU 暫存器。

(7) FTTH: Fiber To The Home:

• 全名/定義: 光纖到家 (Fiber To The Home, FTTH) 是一種寬頻網路傳輸技術，它使用光纖電纜直接連接到家庭或企業。
• 目的: 提供比傳統銅纜 (如 DSL) 更高速度、更大頻寬的網際網路接入。
• 應用: 高速寬頻上網、IPTV、VoIP、遠端辦公、線上遊戲。
• 範例: 使用者家中直接連接光纖線路，享有數百 Mbps 甚至 Gbps 的下載與上傳速度。

(8) twisted-pair cable:

• 全名/定義: 雙絞線 (Twisted-pair cable) 是一種常見的網路線纜，由兩條絕緣的銅線互相纏繞而成。纏繞的目的是減少電磁干擾 (EMI) 和串音 (crosstalk)。
• 目的: 在區域網路 (LAN) 中傳輸資料訊號。
• 應用: 乙太網路 (Ethernet) 連接，如 Cat5e, Cat6 線纜。
• 範例: 用於連接電腦到路由器或交換器的網路線。

(9) DRAM:

• 全名/定義: 動態隨機存取記憶體 (Dynamic Random-Access Memory, DRAM) 是一種廣泛使用的半導體記憶體。它需要不斷地被重新整理 (refresh) 以保持儲存的電荷，因此稱為「動態」。
• 目的: 作為電腦的主記憶體 (RAM)，儲存作業系統、應用程式和正在處理的資料。
• 應用: 電腦、手機、伺服器等電子設備的主記憶體。
• 特性: 相較於 SRAM，DRAM 儲存密度更高，成本較低，但存取速度較慢，且需要刷新。

(10) Unicode:

• 全名/定義: Unicode 是一個字元編碼標準，旨在為世界上所有書寫系統中的每個字元分配一個唯一的數位值。
• 目的: 解決不同編碼標準之間不相容的問題，實現全球範圍內的文字資訊交換。
• 應用: 網頁 (HTML, CSS, JavaScript)、作業系統、各種應用程式，支援多國語言顯示。
• 範例: 字母 'A' 在 Unicode 中是 U+0041，中文字「字」是 U+5B57。

(11) TCP/IP:

• 全名/定義: 傳輸控制協定/網際網路協定 (Transmission Control Protocol/Internet Protocol, TCP/IP) 是一組網路通訊協定，是網際網路的基礎。IP 負責封包的路由，TCP 負責可靠的、按序的資料傳輸。
• 目的: 實現不同網路設備之間的資料交換和通訊。
• 應用: 網際網路上的所有通訊，包括網頁瀏覽 (HTTP)、電子郵件 (SMTP)、檔案傳輸 (FTP) 等。
• 範例: 當你瀏覽網頁時，你的電腦使用 TCP/IP 協定與網頁伺服器進行通訊。

(12) QoS:

• 全名/定義: 服務品質 (Quality of Service, QoS) 是一組技術，用於管理網路流量，以確保特定應用程式或使用者獲得所需的網路效能（如頻寬、延遲、封包遺失率）。
• 目的: 優先處理關鍵應用程式的流量，例如 VoIP 或視訊會議，以提供更好的使用者體驗。
• 應用: 寬頻網路、企業網路、VoIP 服務、線上遊戲。
• 範例: 在家庭路由器中設定 QoS，為線上遊戲分配更高的優先級，減少遊戲延遲。

(13) recursive:

• 全名/定義: 遞迴 (Recursive) 是一種在程式設計中，一個函數或方法呼叫自身來解決問題的技術。遞迴通常需要一個基本情況 (base case) 來終止呼叫。
• 目的: 以更簡潔、更符合數學定義的方式來表達和解決某些問題，特別是那些可以分解為相似子問題的問題。
• 應用: 階乘計算、斐波那契數列、樹狀結構的遍歷、分治演算法 (如快速排序)。
• 範例: 計算階乘的遞迴函數：factorial(n) = n * factorial(n-1)，基本情況為 factorial(0) = 1。

(14) private key:

• 全名/定義: 私鑰 (Private Key) 是非對稱加密 (asymmetric cryptography) 中的一個組成部分。它與公鑰 (public key) 配對，私鑰必須由擁有者嚴格保密，用於解密資料或數位簽章。
• 目的: 確保資料的機密性、完整性和 autenticity。
• 應用: SSL/TLS 加密、數位簽章、安全電子郵件 (PGP)、加密貨幣交易。
• 範例: 在 SSL/TLS 連線建立時，伺服器使用其私鑰解密從客戶端傳來的預主密鑰，以確保通訊安全。

(15) rootkit:

• 全名/定義: Rootkit 是一種惡意軟體，它能隱藏在作業系統中，並允許攻擊者獲得對系統的最高權限 (root access)。它通常會修改系統的核心元件，以逃避偵測。
• 目的: 隱藏惡意活動、竊取資料、建立後門。
• 應用: 網路攻擊、資訊竊取。
• 範例: 一個 rootkit 可能會修改系統日誌，讓惡意程式的活動不被記錄下來。

(16) RISC: Reduced Instruction Set Computer:

本題考驗對計算複雜度理論中 P 類別與 NP 類別的理解，以及 P=NP 問題的闡述。

P 類別 (Polynomial Time Class)

• 全名: P 類別代表可以在「多項式時間」(Polynomial Time) 內被「確定性圖靈機」(Deterministic Turing Machine) 解決的所有決策問題 (Decision Problems) 的集合。
• 說明: 決策問題是指答案為「是」或「否」的問題。多項式時間是指解決問題所需的時間與問題規模 $n$ 的多項式函數成正比，例如 $O(n^k)$，其中 $k$ 是一個常數。這類問題被認為是「有效率」地可解的。

NP 類別 (Nondeterministic Polynomial Time Class)

• 全名: NP 類別代表可以在「多項式時間」內被「非確定性圖靈機」(Nondeterministic Turing Machine) 驗證 (verify) 的所有決策問題的集合。
• 說明: 這意味著，如果問題的答案是「是」，那麼存在一個「證明」(certificate) 或「提示」(witness)，可以在多項式時間內被確定性圖靈機驗證。換句話說，雖然找到這個證明可能很困難，但一旦給出證明，驗證它是正確的卻是容易的。

本題考查 OSI (Open Systems Interconnection) 模型，這是國際標準化組織 (ISO) 提出的一個網路通訊參考模型，將網路通訊過程劃分為七個邏輯層。

OSI 模型共有七層，由下往上分別是：

1. 實體層 (Physical Layer)

   • 功能: 負責傳輸原始的位元流，處理網路硬體（如網線、連接器、網卡）的規格和傳輸媒介。
   • 單位: 位元 (bits)。

2. 資料鏈結層 (Data Link Layer)

   • 功能: 在實體層提供的基礎上，提供可靠的點對點資料傳輸，負責封包的定址 (MAC 位址)、流量控制和錯誤檢測 (不一定糾正)。
   • 單位: 訊框 (frames)。
   • 常見協定: Ethernet, PPP。

3. 網路層 (Network Layer)

   • 功能: 負責將封包從來源端傳送到目的端，跨越不同的網路。主要處理邏輯定址 (IP 位址) 和路徑選擇 (routing)。
   • 單位: 封包 (packets)。
   • 常見協定: IP (Internet Protocol), ICMP。

4. 傳輸層 (Transport Layer)

   • 功能: 提供端對端 (end-to-end) 的資料傳輸服務，負責將來自上層的資料分割成較小的段落 (segments)，並確保資料的可靠傳輸 (如 TCP) 或提供快速但不保證可靠的傳輸 (如 UDP)。
   • 單位: 區段 (segments) 或資料包 (datagrams)。

本題考查堆疊 (Stack) 和佇列 (Queue) 這兩種基本資料結構的定義、特性與差異。

堆疊 (Stack)

• 定義: 堆疊是一種線性資料結構，遵循「後進先出」(Last-In, First-Out, LIFO) 的原則。
• 操作:
  • Push: 將一個元素加入堆疊頂部。
  • Pop: 從堆疊頂部移除並回傳一個元素。
  • Peek (或 Top): 回傳堆疊頂部的元素，但不移除。
  • isEmpty: 檢查堆疊是否為空。
• 應用: 函數呼叫時的參數和局部變數儲存 (呼叫堆疊)、運算式求值 (如中序轉後序)、瀏覽器中的「上一頁」功能、DFS 演算法。
• 範例: 想像一疊盤子，你只能在最上面放盤子 (Push)，也只能從最上面取走盤子 (Pop)。

佇列 (Queue)

• 定義: 佇列是一種線性資料結構，遵循「先進先出」(First-In, First-Out, FIFO) 的原則。
• 操作:
  • Enqueue (或 Add, Push): 將一個元素加入佇列的尾部 (rear)。
  • Dequeue (或 Remove, Pop): 從佇列的頭部 (front) 移除並回傳一個元素。
  • Peek (或 Front): 回傳佇列頭部的元素，但不移除。

本題考查編譯器 (Compiler) 和直譯器 (Interpreter) 這兩種程式語言執行方式的差異、優缺點。

編譯器 (Compiler)

• 定義: 編譯器是一種將整個原始程式碼 (source code) 一次性翻譯成目標機器碼 (machine code) 或另一種中間語言 (如位元組碼 bytecode) 的程式。
• 工作流程:
  1. 編譯 (Compilation): 掃描整個原始程式碼，進行詞法分析、語法分析、語義分析、優化，然後生成目標程式碼。
  2. 執行 (Execution): 生成的目標程式碼可以獨立執行，無需編譯器。
• 優點:
  • 執行速度快: 目標程式碼是針對特定硬體優化的，執行效率高。
  • 程式碼保護: 原始碼不直接暴露，增加了程式碼的保護性。
  • 錯誤檢查全面: 在編譯階段會進行較為全面的語法和語義檢查，可能在執行前發現更多錯誤。
• 缺點:
  • 開發週期長: 每次修改程式碼後，都需要重新編譯整個程式，耗時。
  • 生成檔案較大: 產生的目標程式碼可能較大。
  • 跨平台性問題: 編譯出的機器碼通常是平台相關的，需要在不同平台上重新編譯。

直譯器 (Interpreter)

• 定義: 直譯器是一種逐行或逐指令地讀取原始程式碼，並立即執行翻譯結果的程式。
• 工作流程:
  1. 執行 (Execution): 讀取一行原始碼，翻譯成機器指令，執行該指令，然後再讀取下一行。
• 優點:
  • 開發快速: 修改程式碼後可立即執行，無需等待編譯，適合快速原型開發和除錯。
  • 跨平台性好: 只要目標平台安裝了相應的直譯器，同一份原始碼就可以在不同平台上執行。
  • 除錯容易: 錯誤通常在執行到出錯的那一行時立即報告，易於定位。
• 缺點:
  • 執行速度慢: 每次執行都需要即時翻譯，效率較低。
  • 程式碼保護性弱: 原始碼需要直接提供給直譯器執行。

本題要求將一個中序表達式轉換為後序表達式。這通常使用堆疊 (Stack) 來實現。

基本規則:

1. 掃描中序表達式中的每個符號。
2. 若符號是運算元 (operand)，則直接輸出。
3. 若符號是運算子 (operator)：
   • 若堆疊為空，則將運算子壓入堆疊。
   • 若堆疊不為空，則比較當前運算子的優先級與堆疊頂部運算子的優先級。
     • 若當前運算子的優先級高於或等於堆疊頂部運算子，則將當前運算子壓入堆疊。
     • 若當前運算子的優先級低於堆疊頂部運算子，則從堆疊頂部彈出運算子並輸出，直到堆疊頂部運算子的優先級低於當前運算子，或堆疊為空，然後再將當前運算子壓入堆疊。
4. 若符號是左括號 '(': 直接壓入堆疊。
5. 若符號是右括號 ')': 從堆疊頂部彈出運算子並輸出，直到遇到左括號 '('。然後將左括號彈出但不輸出。
6. 掃描完所有符號後，將堆疊中剩餘的運算子依序彈出並輸出。

運算子優先級:

• *, / (高優先級)
• +, - (低優先級)

表達式: $a + b * e + c / d$

轉換過程:

符號	堆疊 (Stack)	輸出 (Output)	說明
a	[]	a	運算元，直接輸出。
+	[+]	a	堆疊為空，壓入 +。

本題考查將十進位數轉換為二進位數。需要分別處理整數部分和小數部分。

1. 整數部分轉換 (113)

使用除以 2 取餘數的方法，直到商為 0。

• $113 \div 2 = 56$ 餘 1
• $56 \div 2 = 28$ 餘 0
• $28 \div 2 = 14$ 餘 0
• $14 \div 2 = 7$ 餘 0
• $7 \div 2 = 3$ 餘 1
• $3 \div 2 = 1$ 餘 1
• $1 \div 2 = 0$ 餘 1

將餘數從下往上讀取，得到二進位整數部分為 $1110001_2$。

核心觀念

本題考查二元樹的深度優先搜尋（Depth-First Search, DFS）與廣度優先搜尋（Breadth-First Search, BFS）。

依題圖的標準二元樹結構，節點關係為：

• $S$ 的左子節點為 $E$
• $E$ 的左、右子節點分別為 $A、R$
• $R$ 的左、右子節點分別為 $C、H$
• $C$ 的左子節點為 $T$

可表示為：

        S
       /
      E
     / \
    A   R
       / \
      C   H
     /
    T

本題 DFS 採用二元樹最常見的「先拜訪節點，再拜訪左子樹，最後拜訪右子樹」規則，也就是前序走訪（preorder）：

$$\text{Root} \rightarrow \text{Left} \rightarrow \text{Right}$$

BFS 則按照樹的層級，由上而下、同一層由左而右拜訪。

解題方法：DFS

DFS 優先沿著目前節點的左側往下走，走到底後回溯，再處理右子樹。

依序拜訪如下：

1. 從根節點 $S$ 開始，輸出 $S$
2. 進入 $S$ 的左子樹，輸出 $E$
3. 進入 $E$ 的左子樹，輸出 $A$
4. $A$ 沒有子節點，回溯至 $E$
5. 進入 $E$ 的右子樹，輸出 $R$
6. 進入 $R$ 的左子樹，輸出 $C$
7. 進入 $C$ 的左子樹，輸出 $T$

本題要求使用插入排序 (Insertion Sort) 演算法對給定的列表進行排序，並列出每一輪排序 (pass) 後的結果。

插入排序 (Insertion Sort)
插入排序的工作原理是將列表分為已排序部分和未排序部分。它從未排序部分的第一个元素開始，將其插入到已排序部分的正確位置，直到所有元素都被插入。

列表: [18, 99, 21, 14, 149, 31, 8]

排序過程:

Pass 1: 考慮第一個元素 18。它自己本身就是一個已排序的列表。

• 已排序部分: [18]
• 未排序部分: [99, 21, 14, 149, 31, 8]
• 列表狀態: [18, 99, 21, 14, 149, 31, 8]

Pass 2: 考慮下一個元素 99。將 99 插入到已排序部分 [18] 中。99 大於 18，所以放在 18 的後面。

• 已排序部分: [18, 99]
• 未排序部分: [21, 14, 149, 31, 8]
• 列表狀態: [18, 99, 21, 14, 149, 31, 8]

Pass 3: 考慮下一個元素 21。將 21 插入到已排序部分 [18, 99] 中。

• 21 小於 99，將 99 向右移動。列表變為 [18, _, 99, ...]
• 21 大於 18，將 21 插入到 18 和 99 之間。
• 已排序部分: [18, 21, 99]
• 未排序部分: [14, 149, 31, 8]
• 列表狀態: [18, 21, 99, 14, 149, 31, 8]

Pass 4: 考慮下一個元素 14。將 14 插入到已排序部分 [18, 21, 99] 中。

• 14 小於 99，將 99 向右移動。列表變為 [18, 21, _, 99, ...]
• 14 小於 21，將 21 向右移動。列表變為 [18, _, 21, 99, ...]
• 14 小於 18，將 18 向右移動。列表變為 [_, 18, 21, 99, ...]
• 將 14 插入到開頭。
• 已排序部分: [14, 18, 21, 99]
• 未排序部分: [149, 31, 8]
• 列表狀態: [14, 18, 21, 99, 149, 31, 8]

Pass 5: 考慮下一個元素 149。將 149 插入到已排序部分 [14, 18, 21, 99] 中。

• 149 大於 99。直接插入到末尾。
• 已排序部分: [14, 18, 21, 99, 149]
• 未排序部分: [31, 8]