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

核心觀念

本題考驗 OSI 七層模型（Open Systems Interconnection Model）中各層級傳輸資料的「協定資料單元」（Protocol Data Unit, PDU）定義。

OSI 模型由下至上分為七層，每一層傳輸與處理資料時，都有其對應的資料包裝名稱與基本單位：

1. 實體層（Physical Layer）：位元（Bit）/ 訊號（Signal）
2. 資料連結層（Data Link Layer）：訊框（Frame）
3. 網路層（Network Layer）：封包（Packet）
4. 傳輸層（Transport Layer）：區段（Segment，使用 TCP 時）/ 數據報（Datagram，使用 UDP 時）
5. 應用層 / 展現層 / 會議層（Application/Presentation/Session Layer）：資料（Data）/ 訊息（Message）

---

解題方法

根據 OSI 模型規範，當資料傳送至第二層（資料連結層）時，會加上該層的表頭（Header）與尾碼（Trailer，包含動態錯誤檢查編碼如 CRC），此資料包裝型態即稱為 訊框 (Frame)。因此，資料連結層傳送與處理的基本單位為 Frame。

---

選項分析

• (A) 封包 (packet)：錯誤。封包是 網路層（Network Layer, Layer 3） 的基本 PDU 單位（如 IP Packet）。

核心觀念

本題考驗網際網路協定套組（TCP/IP Protocol Suite）中應用層與網路層常見通訊協定的功能與作用。
在網路溝通中，人類習慣使用易讀易記的網域名稱（Domain Name，例如 www.ntu.edu.tw），而網路層設備（如路由器、伺服器）則是透過 IP 位址（IP Address，例如 140.112.8.116）進行封包定址與路由。因此，網路架構中需要一套分散式資料庫服務，專門負責將網域名稱解析為對應的 IP 位址，或進行反向查詢（由 IP 位址查詢網域名稱）。

---

解題方法與切入點

解題切入點在於識別題目關鍵字：「提供 IP 位置和網域名稱查詢的服務」。
在 TCP/IP 協定堆疊中：

1. 網域名稱轉 IP 位址 屬於應用層（Application Layer）的主機名稱解析服務。
2. 題目提到的其他協定（RARP, DHCP, ICMP, ARP）均屬於網路層（Network Layer）或資料鏈結層（Data Link Layer）的底層控制、定址與組態協定，不處理「網域名稱」層級的查詢。

因此，僅有 DNS（Domain Name System） 符合網域名稱與 IP 位址相互查詢與對應的需求。

---

選項分析

• (A) RARP (Reverse Address Resolution Protocol)：錯誤。
  反向位址解析協定。運作於網路介面層/資料鏈結層，主要功能是讓無磁碟工作站（Diskless Workstation）在啟動時，利用自身的實體位址（MAC Address）向 RARP 伺服器查詢並取得分配給自己的邏輯位址（IP Address）。它並不處理網域名稱（Domain Name）。
• (B) DHCP (Dynamic Host Configuration Protocol)：錯誤。
  動態主機設定協定。運作於應用層（基於 UDP），主要功能是自動分配 IP 位址、子網路遮罩（Subnet Mask）、預設閘道（Default Gateway）及 DNS 伺服器 IP 等網路組態參數給區域網路內的主機，並非提供網域名稱與 IP 位址之間的轉譯查詢服務。
• (C) DNS (Domain Name System)：正確。
  網域名稱系統。

核心觀念

本題旨在考驗對基本資料結構（Data Structures）之資料存取順序特徵的理解。

資料結構的資料存取順序常見有以下兩種：

1. LIFO（Last-In, First-Out，後進先出）：最後進入結構的元素，會最先被取出或移除。
2. FIFO（First-In, First-Out，先進先出）：最先進入結構的元素，會最先被取出或移除。

資料結構中，堆疊（Stack） 是標準採用 LIFO 順序運作的線性資料結構。其運算受限於僅能在一端（稱為 頂端 Top）進行插入（Push）與刪除（Pop）。

---

解題方法

1. 分析 LIFO 定義：尋找題目選項中，哪一個資料結構的插入與刪除操作僅在同一端點進行，進而符合「最後加入者最先離開」的特徵。
2. 對照各選項資料結構特徵：
   • 陣列（Array）：隨機存取（Random Access）。
   • 佇列（Queue）與環狀佇列（Circular Queue）：先進先出（FIFO）。
   • 堆疊（Stack）：後進先出（LIFO）。
   • 鏈結串列（Linked List）：依指標存取，無固定之 LIFO 或 FIFO 強制限制。

---

選項分析

• (A) 陣列 (Array)：錯誤。
  陣列為連續記憶體空間構成的資料 structures，支援隨機存取（Random Access）。只要知道索引值（Index），即可以 $O(1)$ 的時間複雜度讀取任意位置的元素，並不限定後進先出的順序。

核心觀念

本題考查**二元樹的樹狀結構走訪（Binary Tree Traversal）**機制。

二元樹（Binary Tree）的深度優先走訪（Depth-First Traversal）依據父節點（V）、**左子節點/左子樹（L）與右子節點/右子樹（R）**的探訪先後順序，主要分為三種基本走訪方式：

1. 前序走訪（Preorder Traversal）：走訪順序為 根（V）$\rightarrow$ 左（L）$\rightarrow$ 右（R）。
2. 中序走訪（Inorder Traversal）：走訪順序為 左（L）$\rightarrow$ 根（V）$\rightarrow$ 右（R）。
3. 後序走訪（Postorder Traversal）：走訪順序為 左（L）$\rightarrow$ 右（R）$\rightarrow$ 根（V）。

其名稱中的「前、中、後」係指父節點（根節點）被探訪的時間點：

• 父節點最先探訪 $\rightarrow$ 前序
• 父節點在左右子節點中間探訪 $\rightarrow$ 中序
• 父節點最後探訪 $\rightarrow$ 後序

---

解題方法

根據題目敘述：

• 探訪順序為：先探訪父節點 $\rightarrow$ 再探訪左子節點 $\rightarrow$ 最後探訪右子節點。
• 簡記為：父（V） $\rightarrow$ 左（L） $\rightarrow$ 右（R）。

由於父節點位於探訪順序的最前面，對應 Depth-First Traversal 的定義，此走訪方式即稱為前序法（Preorder Traversal）。

---

選項分析

核心觀念

本題考查資料庫管理系統（DBMS）的分類與架構，特別是**關聯式資料庫（RDBMS）與非關聯式資料庫（NoSQL）**的差異。

1. 關聯式資料庫（Relational Database Management System, RDBMS）：

   • 資料模型：基於關聯模型（Relational Model），資料以表格（Table / Relation）的形式呈現，由行（Row / Tuple）與列（Column / Attribute）組成。
   • 查詢語言：採用結構化查詢語言（SQL, Structured Query Language）。
   • 特性：具備嚴格的 Schema（預先定義欄位結構與型態），並遵循 ACID 原則（Atomicity 原子性、Consistency 一致性、Isolation 隔離性、Durability 持久性），適合處理高度關聯且要求資料一致性的交易系統。

2. 非關聯式資料庫（NoSQL Database）：

   • 資料模型：打破傳統關聯表格的形式，常見型態包括文件型（Document-oriented）、鍵值型（Key-Value）、列家族型（Column-family）與圖形型（Graph）。
   • 特性：無固定 Schema（Schema-less 或 Dynamic Schema），易於橫向擴充（Horizontal Scaling），通常遵循 BASE 原則（Basically Available, Soft state, Eventual consistency），適合處理海量資料、半結構化或非結構化資料。

---

解題方法

解題切入點為區分各大主流資料庫系統屬於 SQL (RDBMS) 亦或 NoSQL：

1. 檢視各選項之資料庫系統。
2. 辨識其資料儲存架構：是否使用 SQL 語法與關聯式表格儲存。
3. 找出不屬於 RDBMS（即屬於 NoSQL）的選項。

---

選項分析

核心觀念

本題考查開放系統互連參考模型（OSI 7-Layer Reference Model）中，**網路層（Network Layer）**的功能與對應的網路硬體設備。

OSI 模型將網路通訊協定劃分為七個層級，由下至上分別為：

1. 實體層（Physical Layer）：負責位元傳輸與訊號轉換（如：中繼器 Repeater、集線器 Hub）。
2. 資料鏈結層（Data Link Layer）：負責訊框（Frame）傳送與 MAC 位址定址（如：網路卡 NIC、橋接器 Bridge、交換器 Switch）。
3. 網路層（Network Layer）：負責封包（Packet）路徑選擇（Routing）與 IP 位址定址（如：路由器 Router）。
4. 傳輸層（Transport Layer）：負責端到端（End-to-End）連線與流量控制（如：四層交換器 Layer 4 Switch）。
5. 會議層（Session Layer）：負責管理應用程式間的對話與會話建立。
6. 簡報層（Presentation Layer）：負責資料格式轉換、加解密與壓縮。
7. 應用層（Application Layer）：提供使用者網路服務介面。

解題方法

判斷網路設備屬於 OSI 第幾層的關鍵，在於該設備運作時所依據的標頭（Header）資訊與定址方式：

• **路由器（Router）**的主要功能是進行「路由選擇」（Routing）與「封包轉送」（Packet Forwarding）。
• 路由器藉由解析 IP 封包的邏輯位址（IP Address），並查閱內部的**路由表（Routing Table）**來決定封包的最佳傳輸路徑。
• 由於 IP 位址與路由協定均屬於 OSI 模型的第三層（網路層，Network Layer），因此路由器屬於第三層網路設備。

核心觀念

本題旨在考察**字元編碼系統（Character Encoding）**的發展歷程、字集（Character Set）與編碼機制（Encoding Scheme）的區別，以及各主流標準的字元範圍、位元長度與實際應用場景。

關鍵觀念與定義包含：

1. 字元集（Character Set / Repertoire）：定義了「哪些字元存在」以及每個字元對應的唯一數值編號（Code Point，碼位）。
2. 編碼機制（Encoding Scheme）：定義「如何將字元的碼位轉換為電腦記憶體中的二進位位元組（Bytes）序列」。
3. ASCII（American Standard Code for Information Interchange）：7-bit 的美國標準資訊交換碼，單位元組編碼。
4. Big5（大五碼）：繁體中文最常見的雙位元組（Double-Byte Character Set, DBCS）變長編碼系統。
5. Unicode（統一碼 / 萬國碼）：跨語言的通用字元集標準（UCS），旨在涵蓋全世界所有文字系統。
6. UTF-8 / UTF-16 / UTF-32：Unicode 的三種主要傳輸/儲存格式（Unicode Transformation Format），分別採用變長（1~4 Bytes）、變長（2或4 Bytes）及定長（4 Bytes）的實現方式。

---

解題方法

本題為敘述型觀念比較題，切入點應分為兩個核心部分：

1. 概念比較：分別說明 ASCII、Big5、Unicode 的定義，並以「字元集涵蓋範圍」、「位元長度/儲存空間」、「相容性」等維度比較三者異同。
2. 實作應用：解析 UTF-8、UTF-16、UTF-32 的編碼特性與各自最適用的實際應用場景。

---

題目詳細解析與答案

一、 ASCII、Big5、Unicode 的定義與異同

1. 三大編碼系統定義

• ASCII：
  • 定義：1963 年發布的美國標準資訊交換碼，為單位元組（1 Byte）編碼系統。
  • 範圍：使用 7 個位元（7 bits）來表示字元，共定義 $2^7 = 128$ 個字元（編碼區間 $0 \sim 127$ 或 0x00 $\sim$ 0x7F），包含英文字母（大小寫）、阿拉伯數字、常用符號及控制字元（如 CR, LF, TAB 等）。最高位元（第 8 bit）通常留作檢錯位元（Parity Bit）或延伸字元使用。
• Big5（大五碼）：
  • 定義：1984 年由台灣財團法人資訊工業策進會（資策會）聯合五大電腦公司共同創立的繁體中文變長雙位元組字元編碼系統。
  • 範圍：採用 2 個位元組（16 bits）表示一個中文字，ASCII 字元則維持 1 位元組。收錄了 13,058 個繁體中文字及符號（包含常用字 5,401 字、次常用字 7,657 字）。高位元組區間為 0xA1 $\sim$ 0xF9，低位元組區間為 0x40 $\sim$ 0x7E 及 0xA1 $\sim$ 0xFE。
• Unicode（萬國碼）：
  • 定義：由 Unicode 聯盟於 1991 年推出的國際標準字元集（ISO 10646），旨在解決傳統編碼中不同語言碼頁（Code Page）互相衝突、出現亂碼（Mojibake）的問題。
  • 範圍：Unicode 將世界上現存與古代的所有文字符號統一編號。碼位空間從 U+0000 到 U+10FFFF，共計包含 $17 \times 65536 = 1,114,112$ 個碼位（分成 17 個平面 Plane），目前已收錄超過 15 萬個字元。

2. 三者之異同比較

比較維度	ASCII	Big5	Unicode
目標語言	英文與美式符號	繁體中文（台灣、香港、澳門等）	全球所有語言與符號（包含 Emoji）
字元集屬性	字元集兼編碼格式	繁體中文專用碼頁（Code Page）	純粹的通用字元集（需搭配 UTF 實現儲存）
位元長度	定長 7 bits（占 1 Byte）	變長（ASCII 占 1 Byte，中文字占 2 Bytes）	抽象碼位（概念上為 21 bits，透過 UTF 轉譯）
字元容量	128 個字元	約 13,058 個字元	可達 $1,114,112$ 個碼位
相容性	最基礎標準，被 Big5 與 UTF-8 向下相容	僅相容 ASCII，與其他語系（如 GB2312, Shift-JIS）衝突	相容 ASCII（碼位 0~127 完全一致）

---

二、 UTF-8、UTF-16、UTF-32 的定義與應用

Unicode 僅定義了字元的「號碼（Code Point）」，而 UTF（Unicode Transformation Format） 則是將這些號碼映射為記憶體或檔案位元組串流的具體實作。

1. UTF-8

• 編碼特性：
  • 變長位元組編碼（Variable-length encoding），長度為 1 到 4 個位元組。

核心觀念

本題旨在考驗考生對物件導向程式設計（Object-Oriented Programming, OOP）中**變數作用域（Scope）與生命週期（Lifetime / Extent）**的理解，特別是依附於「類別（Class）」、「物件實例（Instance）」與「區塊/方法（Block/Method）」三個不同層級之變數的差異：

1. Class Variable（類別變數 / 靜態變數 Static Variable）：
   • 屬於類別本身，而非個別物件實例。
   • 在記憶體中僅存在一份共享拷貝（所有同類別的物件實例共用同一份記憶體位址）。
   • 生命週期：隨類別載入（Class Loading）時建立，直到程式結束或類別被解除載入（Unload）時銷毀。
2. Instance Variable（實例變數 / 成員變數 Member Variable）：
   • 屬於個別物件實例。
   • 每當透過 new 或建構子建立一個新物件時，該物件都會擁有自己獨立的一份變數拷貝。
   • 生命週期：隨物件被建立（Instantiation）時分配記憶體，當物件失去引用並被垃圾回收（Garbage Collection, GC）或手動釋放時銷毀。
3. Local Variable（區域變數）：
   • 宣告於方法（Method）、建構子（Constructor）或程式區塊（Block, 如 for, if）內部。
   • 僅能在其宣告的區塊範圍（Scope）內被存取。
   • 生命週期：當程式執行進入該方法/區塊時建立（通常於 Stack 堆疊區分配），離開該方法/區塊時立即銷毀釋放。

---

解題方法

解答此題時，應採取三段式對比分析：

1. 定義與特徵說明：針對三種變數從「宣告位置」、「記憶體配置區域（Heap vs Stack vs Data/Static Segment）」、「預設值（Default Value）」及「生命週期」進行條理化說明。
2. 應用場域（Use Cases）：明確舉出各變數在真實軟體開發中的典型應用場景。
3. 程式碼範例與複雜度分析：提供一段簡潔且嚴謹的 OOP 程式碼範例（以 Java 為例），呈現三種變數的語法結構與運作機制。

---

選項與觀念對比分析（詳細表解）

本題為問答題，下表針對三種變數的核心特性進行全方位詳細對比：

特性比較項目	Class Variable (類別變數)	Instance Variable (實例變數)	Local Variable (區域變數)
關鍵字/宣告位置	類別內部、方法外部，使用 static 修飾符	類別內部、方法外部，無 static 修飾符	方法、建構子或程式區塊（如 if/for）內部
記憶體配置區域	方法區 / 靜態區 (Method Area / Static Segment)	堆疊區 (Heap Segment)	棧區 (Stack Segment)
記憶體份數	該類別所有實例共用唯一一份	每個物件實例各自擁有一份	每次方法調用獨立於記憶體棧幀中分配
預設初始值	有系統預設值 (如 numeric 為 0, boolean 為 false, reference 為 null)	有系統預設值 (同左)	無預設值，使用前必須顯式初始化，否則編譯報錯
存取方式	可直接使用 類別名稱.變數名 存取	必須透過 物件實例名稱.變數名 存取	直接在作用域內使用 變數名 存取

應用場域說明：

1. Class Variable 的應用場域：
   • 計數器與全域狀態：用來統計該類別共建立了多少個物件實例（如 counter）。
   • 常數定義（Constants）：結合 final 關鍵字定義跨物件共享且不可變的常數（例如 Math.PI 或系統設定參數 MAX_CONNECTIONS）。
   • 共享資源池/快取：多個物件需共用的資源或單例模式（Singleton Pattern）中的實例引用。
2. Instance Variable 的應用場域：
   • 描述物件的獨特狀態與屬性：如 Person 類別中的 name、age、id；或 BankAccount 中的 balance。每個物件這些屬性值各自獨立、互不影響。
3. Local Variable 的應用場域：

核心觀念

本題旨在考驗物件導向程式設計（Object-Oriented Programming, OOP）中四大特性之一——多型（Polymorphism） 的基本定義與實務應用機制。

1. 多型（Polymorphism）的定義：字面意思為「多種型態（Poly = Many, Morph = Form）」。在物件導向程式設計中，多型是指**「允許不同的類別（Class）物件對同一個訊息（或方法呼叫）做出各自不同的回應」**。換言之，即「介面統一，實作多元（Same Interface, Multiple Implementations）」。
2. 多型實現的兩大機制：
   • 編譯期多型（Compile-time / Static Polymorphism）：主要透過方法重載（Method Overloading） 實現。在編譯階段，編譯器根據傳入參數的個數與型別決定呼叫哪一個方法（稱為靜態繫結 Static Binding）。
   • 執行期多型（Runtime / Dynamic Polymorphism）：主要透過繼承（Inheritance）、抽象類別（Abstract Class）/ 介面（Interface） 與 方法覆寫（Method Overriding） 實現。程式在執行階段，才根據指標或參考實際指向的物件型別來決定執行哪個實作（稱為動態繫結 Dynamic Binding / Late Binding）。

---

解題方法

解答本題應分為兩大區塊：第一部分完整說明「多型」的語意與核心運作機制；第二部分詳細說明「程式撰寫上的運用機制與範例」，並以物件導向語言（如 Java / C++）示範多型如何發揮彈性與可維護性。

1. 多型 (Polymorphism) 的核心概念與機制

• 抽象介面與多樣實作：高層模組（呼叫端）只需操作抽象父類別（或介面）型別的變數，不必關心底層確切是哪一個子類別物件，程式會在執行時動態解析並執行對應子類別覆寫（Override）後的方法。
• 動態繫結（Dynamic Binding）：背後機制通常依賴虛擬方法表（Virtual Method Table, vtable）。編譯時僅檢查介面是否存在，執行時透過物件表頭指向的 vtable 找出實際呼叫的函式位址。

2. 程式撰寫上如何運用此概念

在實際撰寫程式時，多型主要發揮在以下三大面向：

1. 減少分支判斷（消除 if-else 或 switch-case）：
   若無多型，處理不同類別物件時需要不斷以 if (type == A) ... else if (type == B) 判斷；具備多型後，可以直接統一發出呼叫（如 shape.draw()）。
2. 提高程式擴充性與維護性（符合開放封閉原則 OCP）：
   新增功能或子類別時，舊有的呼叫端程式碼完全不需要修改，只需新增子類別並覆寫方法即可。
3. 介面導向程式設計（Design Patterns 基礎）：
   如工廠模式（Factory Pattern）、策略模式（Strategy Pattern）等設計模式，均極度仰賴多型來達成模組間的低耦合（Loose Coupling）。

---

關鍵程式碼示範（Java）

以下以圖形繪製系統示範「執行期多型」的撰寫方式與運作機制：

核心觀念

本題主要考驗資料庫系統（Database Systems）的核心設計哲學與資料模型分類，包含以下兩大核心考點：

1. 關聯式資料庫（Relational Database Systems, RDBMS）與 NoSQL 資料庫之比較：
   • 關聯式資料庫：基於 Edgar F. Codd 提出的關聯模型（Relational Model），資料以二維表（Table/Relation）組織，強調資料的結構化、一致性與 ACID 交易特性（Atomicity, Consistency, Isolation, Durability）。
   • NoSQL 資料庫（Not Only SQL）：為因應巨量資料（Big Data）、高並行與非結構化/半結構化資料而設計，通常捨棄嚴格的 ACID 轉而採用 BASE 特性（Basically Available, Soft state, Eventual consistency），支援 Key-Value、Document、Column-family、Graph 等多樣化資料模型。
2. Schema on Write 與 Schema on Read 之概念：
   • Schema on Write（寫入時模式）：資料在「寫入/儲存」資料庫前，必須嚴格符合預先定義好的 Schema。若資料格式不符則拒絕寫入。
   • Schema on Read（讀取時模式）：資料在寫入時不做格式檢查與轉換（直接以原始/半結構化形式存入），直到「讀取/查詢」時才解析資料結構並套用 Schema。

---

解題方法

本題為觀念申論題，答題架構應分為三大部分，切入點如下：

1. 關聯式資料庫的概念說明：從關聯模型（Table、Row、Column、Primary/Foreign Key）與 SQL 語言切入，說明其透過正規化（Normalization）減少資料冗餘並維持資料完整性（Data Integrity）與 ACID 交易。
2. 關聯式與 NoSQL 資料庫之主要差異比較：從資料模型、擴展性（Scaling）、交易特性（Transaction）、Schema 彈性及查詢語言等維度進行系統化對比（建議整理為比較表格，讓閱卷老師一目了然）。
3. Schema on Write 與 Schema on Read 之詳細解釋與對比：針對定義、運作機制、適用場景及優缺點進行深度的說明。

---

解題與觀念剖析

一、關聯式資料庫（Relational Database）的概念

關聯式資料庫（RDBMS）是以**關聯模型（Relational Model）**為基礎的資料庫管理系統。其核心概念包含：

• 資料結構：資料儲存於由列（Row / Tuple）與欄（Column / Attribute）組成的二維表格（Table / Relation）中。
• 關聯性與完整性：表格之間透過主鍵（Primary Key）與外鍵（Foreign Key）建立關聯，並實施實體完整性（Entity Integrity）與參照完整性（Referential Integrity）。
• 資料操作與規範：使用標準化查詢語言 SQL（Structured Query Language），並透過正規化（Normalization）技術消除資料重複（Redundancy）。
• 交易管理（ACID）：支援完整的交易特性，確保在多使用者並行存取或系統故障時，資料庫依然保持絕對的一致性與可靠性。

---

選項分析 / 比較維度分析

二、關聯式資料庫與 NoSQL 資料庫的主要差異

比較維度	關聯式資料庫 (RDBMS)	NoSQL 資料庫
資料模型 (Data Model)	結構化二維表（Table）	多樣化（鍵值對 Key-Value、文件 Document、寬欄位 Column-Family、圖形 Graph）
Schema 規範	預先定義（Rigid / Schema-on-Write）	無固定模式或動態模式（Dynamic / Schema-less）
擴展方式 (Scaling)	垂直擴展（Scale-Up，提升單機硬體規格）	水平擴展（Scale-Out，透過分散式叢集加機器）
交易特性 (Transaction)	遵循 ACID 特性（強調強一致性 Consistency）	遵循 BASE 特性（基本可用、軟狀態、最終一致性）

核心觀念

本題旨在考驗對 OSI 七層模型（OSI 7-Layer Model）與 TCP/IP 網路架構中**網路層（Network Layer）與資料鏈結層（Data Link Layer）**之位址機制與運作原理的理解。

1. IP 位址（Internet Protocol Address）：

   • 運作於 OSI 第三層（網路層, Network Layer）。
   • 為邏輯位址（Logical Address），可透過 DHCP 或手動設定動態分配與變更。
   • 負責**跨網段（End-to-End）**的定址與路由選擇（Routing），標示資料封包最終的來源端與目的端。

2. MAC 位址（Media Access Control Address）：

   • 運作於 OSI 第二層（資料鏈結層, Data Link Layer）。
   • 為實體位址（Physical Address） / 硬體位址，出廠時燒錄於網路介面卡（NIC）中，全球唯一（前 24 位元為 OUI 廠商識別碼）。
   • 負責**區域網路內部（Hop-to-Hop / Point-to-Point）**相鄰設備間的直接框架（Frame）傳送與介面識別。

3. 位址解析協定（Address Resolution Protocol, ARP）：

   • 用於將同網段內的 IP 位址（3 層）映射轉換為對應的 MAC 位址（2 層）。

---

解題方法：比較與傳送流程分析

本題需分為兩大部分解答：第一部分為 IP 位址與 MAC 位址的異同比較；第二部分為 同網段（LAN）內 A 點傳輸資料給 B 點時，兩位址的應用與轉送機制。

一、 IP 位址與 MAC 位址之比較

比較項目	IP 位址 (Internet Protocol Address)	MAC 位址 (Media Access Control Address)
OSI 層級	第三層：網路層 (Network Layer)	第二層：資料鏈結層 (Data Link Layer)
位址性質	邏輯位址 (Logical Address)，可動態變更與分配	實體／硬體位址 (Physical/Hardware Address)，出廠固定
位址長度與格式	IPv4：32 bits（點分十進位，如 192.168.1.1）<br>IPv6：128 bits（十六進位以冒號分隔）	48 bits（6 個 byte，十六進位表示，如 AA:BB:CC:11:22:33）
作用範圍	端到端 (End-to-End)，全網網際路由	跳到跳 (Hop-to-Hop)，僅在同一個區域網路 (LAN) 有效
主要功能	決定資料封包在網際網路上的路徑 (Routing)	決定資料框架在同網段實體介面間的遞送 (Switching)

---

二、 同一區域網路內 A 傳送資料至 B 的位址應用與轉送過程

假設 A 點 IP 為 $IP_A$、MAC 為 $MAC_A$；B 點 IP 為 $IP_B$、MAC 為 $MAC_B$。兩者位於同一個 Subnet（區域網路）內。

[ A 點 ] -------------------- ( Switch / Hub ) -------------------- [ B 點 ]
IP: IP_A                                                            IP: IP_B
MAC: MAC_A                                                          MAC: MAC_B

資料傳送步驟說明：

核心觀念

本題考查資料結構中的**雜湊搜尋法（Hashing Search）**及其相關機制。雜湊搜尋法是一種利用函數對應（Mapping）來達到高效搜尋與儲存的技術，其核心概念與常考要點如下：

1. 雜湊函數（Hash Function）：將鍵值（Key, $k$）映射至雜湊表（Hash Table）中對應位址/槽位（Bucket/Slot, $h(k)$）的數學函數。理想狀況下可實現 $O(1)$ 時間複雜度的平均搜尋與插入。
2. 雜湊碰撞（Collision）與溢位（Overflow）：當兩個或多個相異的鍵值 $k_1 \neq k_2$，經過雜湊函數計算得到相同的位址，即 $h(k_1) = h(k_2)$ 時，稱為碰撞。若該槽位空間已滿無法容納新資料，則稱為溢位。
3. 碰撞處理（Collision Handling）：為避免碰撞導致資料覆蓋或無法儲存，必須實施系統性的解決機制。主要分為兩大類：
   • 開放定址法（Open Addressing）：所有資料皆儲存於雜湊表中，碰撞時依特定探測序列（Probing Sequence）尋找下一個可用的空槽位。
   • 鏈結法 / 封閉定址法（Chaining / Closed Addressing）：每個槽位維護一個鏈結串列（Linked List），將碰撞至相同位址的資料串接在後端。
4. 資料叢聚（Clustering）：在碰撞處理過程中，鍵值過度集中佔據連續槽位的現象，會顯著拉長探測長度，降低搜尋與插入效能。

---

解題方法

本題為問答申論題，答題切入點應針對四個子問題依序進行系統化、精確的觀念論述與分類說明。

2.6.1. 何為雜湊函數 (Hash Function) 的概念？其目的為何？

• 概念：
  雜湊函數 $h$ 是一個將大範圍或不固定長度的鍵值空間（Key Space, $U$）映射至固定大小的雜湊表位址空間（Address Space, $\{0, 1, \dots, m-1\}$）之函數，寫作：
  $h: U \to \{0, 1, \dots, m-1\}$
• 目的：
  1. 提升搜尋與存取效率：經由鍵值直接計算出資料的儲存記憶體位址，省去傳統陣列/串列線性搜尋 $O(n)$ 或樹狀結構對數搜尋 $O(\log n)$ 的比較過程，使平均搜尋時間達到 $O(1)$。
  2. 空間壓縮與記憶體最佳化：鍵值空間（如身份證字號、字串）通常遠大於實際要儲存的資料筆數。雜湊函數能將廣大的鍵值空間壓縮對應至合理大小的記憶體空間（雜湊表）中。
  3. 均勻分佈（Uniform Distribution）：優秀的雜湊函數目的在於儘可能將鍵值均勻地散射（Scatter）到各個槽位中，降低碰撞發生的機率。

2.6.2. 為何需要進行碰撞問題處理 (Collision Handling)？

• 必要性說明：
  1. 抽屜原理（Pigeonhole Principle）：鍵值空間的大小 $|U|$ 遠大於雜湊表的大小 $m$（即 $|U| > m$），因此根據鴿籠原理，必然存在 $k_1 \neq k_2$ 使得 $h(k_1) = h(k_2)$。
  2. 避免資料覆蓋與維護正確性：若發生碰撞而不作處理，後寫入的資料會直接覆蓋先前的資料，導致資料遺失與搜尋結果錯誤。
  3. 確保完整存取能力：正確的碰撞處理機制可保證系統在發生碰撞時，仍能正確地將資料放入替代位置（或串列中），並在日後查詢時順利定位與取出該筆資料。

2.6.3. 常見的碰撞問題處理方法為何？

常見的碰撞處理方法可歸納為以下兩大類別：

1. 開放定址法（Open Addressing）
   當發生碰撞 $h(k)$ 時，探測下一個位置 $H_i(k) = (h(k) + f(i)) \bmod m$，其中 $i = 1, 2, 3, \dots$：
   • 線性探測法（Linear Probing）：$f(i) = i$。依序檢查下一個連續槽位 $h(k)+1, h(k)+2, \dots$。優點是局部性良好（Cache Friendly），缺點是容易產生主叢聚問題（Primary Clustering）。