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

本題主要在考察學生對 IEEE 754 浮點數標準的理解，包括其用途、單雙精準度的差異，以及使用時需注意的潛在問題。

核心觀念： IEEE 754 是一個用於表示浮點數（包含整數和分數）的標準，它定義了數值的儲存格式、運算規則以及例外情況處理。

詳解：

1. IEEE 754 標準是什麼？
   IEEE 754 標準是由電機電子工程師學會（IEEE）制定的一套浮點數表示與運算的標準。它定義了如何將一個實數（包括整數和小數）轉換成二進位的表示方式，以及在這些二進位表示上進行算術運算的規則。這個標準的目的是為了確保不同的電腦系統在處理浮點數時能有一致的結果，減少因表示法不同而產生的誤差。

2. 其用來表示何種型態的資料？
   IEEE 754 標準主要用來表示浮點數（floating-point numbers）。浮點數是可以帶有小數點的數字，可以表示非常大或非常小的數值，也可以表示整數。

3. IEEE 754 單倍精準度和雙倍精準度的差異為何？
   單倍精準度（single-precision）和雙倍精準度（double-precision）是 IEEE 754 定義的兩種常見浮點數格式。它們的主要差異在於儲存數值所需的位元數、表示的範圍以及精確度：

   • 單倍精準度 (Single-Precision):

     • 使用 32 位元來儲存一個浮點數。
     • 結構：1 位元符號 (sign bit) + 8 位元指數 (exponent) + 23 位元尾數 (mantissa/fraction)。
     • 表示範圍：大約在 $\pm 1.4 \times 10^{-45}$ 到 $\pm 3.4 \times 10^{38}$ 之間。
     • 精確度：大約有 6 到 9 位十進位數字的精確度。

   • 雙倍精準度 (Double-Precision):

     • 使用 64 位元來儲存一個浮點數。
     • 結構：1 位元符號 (sign bit) + 11 位元指數 (exponent) + 52 位元尾數 (mantissa/fraction)。
     • 表示範圍：大約在 $\pm 4.9 \times 10^{-324}$ 到 $\pm 1.8 \times 10^{308}$ 之間。
     • 精確度：大約有 15 到 17 位十進位數字的精確度。

   主要差異總結： 雙倍精準度比單倍精準度佔用更多的記憶體空間，但能表示的數值範圍更廣，且具有更高的精確度。

本題旨在考察學生對兩種基本線性資料結構——陣列（Array）和鏈結串列（Linked List）——的理解，包括它們的結構、特性以及在不同操作下的優劣勢。

核心觀念： 陣列和鏈結串列是儲存一系列元素的兩種基本方法，它們在記憶體配置、元素訪問和修改操作上有著根本性的差異。

詳解：

陣列（Array）和鏈結串列（Linked List）是兩種常見的線性資料結構，用於儲存相同類型元素的集合。它們的主要區別在於記憶體配置和存取方式。

1. 陣列（Array）

   • 特性：

     • 連續記憶體配置： 陣列的元素在記憶體中是連續儲存的。這意味著，如果第一個元素的記憶體位址是 $A$，每個元素的大小是 $S$，那麼第 $i$ 個元素的位址（從 0 開始索引）就是 $A + i \times S$。
     • 固定大小： 在許多語言（如 C/C++）中，陣列的大小在宣告時就必須確定，且在運行時無法動態改變。動態陣列（如 C++ 的 std::vector 或 Java 的 ArrayList）雖然可以改變大小，但其底層實現通常是透過重新分配一個更大的連續記憶體區塊並複製舊元素來完成的。
     • 隨機存取（Random Access）： 由於記憶體是連續的，陣列支援 O(1) 時間複雜度的隨機存取。也就是說，可以透過索引（index）直接訪問任何一個元素，而無需遍歷其他元素。

   • 優點：

     • 快速存取： 透過索引直接存取元素的時間複雜度為 O(1)。
     • 記憶體效率（在某些情況下）： 當元素大小固定且不需要頻繁插入/刪除時，連續儲存可以提高快取命中率，從而提升效能。

   • 缺點：

     • 插入/刪除操作慢： 在陣列的開頭或中間插入或刪除元素時，需要移動該位置之後的所有元素來保持記憶體的連續性，這導致時間複雜度為 O(n)，其中 n 是陣列的大小。
     • 大小固定（或重新分配開銷大）： 如果陣列大小固定，當儲存的元素超出容量時，需要進行重新分配，這是一個開銷較大的操作（需要分配新記憶體、複製舊元素、釋放舊記憶體）。

2. 鏈結串列（Linked List）

   • 特性：
     • 非連續記憶體配置： 鏈結串列的元素（稱為節點，node）在記憶體中可以不連續儲存。每個節點包含兩個部分：儲存資料的數據域（data field）和指向下一個節點的指標（pointer/next link）。
     • 動態大小： 鏈結串列的大小是動態的，可以根據需要方便地增加或刪除節點。
     • 順序存取（Sequential Access）： 要存取鏈結串列中的某個元素，必須從鏈結串列的頭部（head）開始，沿著指標一個節點一個節點地遍歷，直到找到目標節點。因此，存取第 $i$ 個元素的平均時間複雜度為 O(n)。

本題主要考察學生對於 TCP 協定在 OSI 模型中的位置、其核心特性，以及兩個重要控制機制：壅塞控制（Congestion Control）與流量控制（Flow Control）的理解和它們之間的關係。

核心觀念： TCP 是網際網路中最重要的傳輸層協定之一，它提供了可靠、有序、面向連接的資料傳輸服務。壅塞控制和流量控制是 TCP 實現這些服務的關鍵機制。

詳解：

1. TCP 協定屬於 OSI 架構之哪一個層？
   TCP（Transmission Control Protocol）協定屬於 OSI（Open Systems Interconnection）模型的傳輸層（Transport Layer）。在 TCP/IP 模型中，它也位於傳輸層。

2. TCP 的主要特性為何？
   TCP 是一種**可靠的、面向連接的（connection-oriented）、全雙工（full-duplex）**的傳輸協議。其主要特性包括：

   • 連接導向（Connection-Oriented）： 在傳輸資料之前，TCP 會在客戶端和伺服器之間建立一個邏輯連接（透過三次握手 Three-Way Handshake）。資料傳輸結束後，連接會被釋放（透過四次揮手 Four-Way Handshake）。
   • 可靠傳輸（Reliable Transmission）： TCP 確保資料能夠正確、完整地從發送端傳輸到接收端。它透過以下機制實現可靠性：
     • 序號（Sequence Numbers）： 為每個傳送的位元組分配一個序號，接收端用來重組亂序的資料包，並偵測遺失的資料包。
     • 確認應答（Acknowledgments, ACK）： 接收端收到資料後會發送確認應答，告知發送端哪些資料已經成功接收。
     • 超時重傳（Timeout and Retransmission）： 如果發送端在預設時間內沒有收到某個資料包的 ACK，它會認為該資料包遺失，並重新發送。
     • 校驗和（Checksum）： 檢查資料在傳輸過程中是否有錯誤。
   • 有序傳輸（Ordered Delivery）： TCP 接收端會根據序號重新排列收到的資料段，確保應用層接收到的資料是按照發送順序組裝好的。
   • 流量控制（Flow Control）： 防止發送端傳送資料的速度過快，以免淹沒接收端的緩衝區。
   • 壅塞控制（Congestion Control）： 防止網路擁塞，避免因過多的資料包導致網路效能下降甚至癱瘓。
   • 全雙工（Full-Duplex）： 在一個 TCP 連接中，資料可以同時從客戶端傳輸到伺服器，以及從伺服器傳輸到客戶端。

3. 何為 TCP 的 Congestion Control 與 Flow Control？

   • 流量控制（Flow Control）：
     • 目的： 確保發送端不會以超過接收端處理能力的速率發送資料，防止接收端緩衝區溢出。

本題旨在考察學生對 SQL 中子查詢（Subquery）的兩種主要類型——相關子查詢（Correlated Subquery）和非相關子查詢（Non-correlated Subquery）的理解，以及它們的執行方式和效率差異。

核心觀念： 子查詢是嵌套在另一個 SQL 語句（如 SELECT, INSERT, UPDATE, DELETE）中的查詢。它們的執行方式決定了它們的效率和適用場景。

詳解：

在 SQL 中，子查詢（Subquery，也稱為嵌套查詢 Inner Query）是指嵌入在另一個 SQL 查詢語句中的 SELECT 語句。子查詢可以返回單個值、單個列、單個行或一個表。根據子查詢的執行方式，可以將其分為兩類：非相關子查詢和相關子查詢。

1. 非相關子查詢（Non-correlated Subquery）

   • 定義： 子查詢的執行與外部查詢（Outer Query）無關。子查詢會被獨立執行一次，其結果會被傳遞給外部查詢。
   • 執行方式：
     1. 首先執行子查詢。
     2. 然後將子查詢的結果作為一個常量值或一個結果集，用於外部查詢的條件判斷或資料來源。
     3. 外部查詢接著執行，並使用子查詢提供的結果。
   • 特性：
     • 獨立執行： 子查詢只執行一次。
     • 結果穩定： 子查詢的結果不隨外部查詢的每一次迭代而改變。
     • 效率： 通常效率較高，因為它只執行一次。
   • 範例： 找出所有薪水高於平均薪水的員工。

     SELECT employee_name, salary
     FROM employees
     WHERE salary > (SELECT AVG(salary) FROM employees);
     

     在這個例子中，子查詢 (SELECT AVG(salary) FROM employees) 會先獨立執行一次，計算出所有員工的平均薪水。然後，外部查詢 SELECT employee_name, salary FROM employees WHERE salary > avg_salary 會使用這個計算出的平均薪水值來篩選員工。

2. 相關子查詢（Correlated Subquery）

   • 定義： 子查詢的執行依賴於外部查詢的當前迭代。也就是說，子查詢的條件中引用了外部查詢的列。
   • 執行方式：
     1. 外部查詢開始執行，它會逐行處理。
     2. 對於外部查詢的每一行，子查詢會被執行一次。
     3. 子查詢在執行時，會使用外部查詢當前行的相關值來進行篩選或計算。
     4. 子查詢的結果用於外部查詢當前行的條件判斷。
     5. 這個過程對外部查詢的每一行都重複進行。
   • 特性：
     • 多次執行： 子查詢會被執行多次，通常與外部查詢返回的行數相同。
     • 結果依賴性： 子查詢的結果會根據外部查詢當前行的上下文而改變。
     • 效率： 通常效率較低，因為它可能需要執行大量次。
   • 範例： 找出每個部門中薪水高於該部門平均薪水的員工。

本題考察學生對 IPv4 向 IPv6 過渡原因的理解、NAT 機制的解釋，以及 NAT 在 IPv4 向 IPv6 過渡中的作用。

核心觀念： IPv4 位址耗盡是推動 IPv6 發展的主要動力。NAT 是一種緩解 IPv4 位址短缺的技術，但它也帶來了一些複雜性，並且在向 IPv6 過渡時扮演著特殊的角色。

詳解：

1. 需要逐步從 IPv4 轉換到 IPv6 的主要原因為何？
   從 IPv4 轉換到 IPv6 的最主要原因，也是最根本的原因是：IPv4 位址枯竭（IPv4 Address Exhaustion）。

   • IPv4 位址空間限制： IPv4 使用 32 位元來表示位址，總共只有 $2^{32} \approx 43$ 億個位址。隨著網際網路的爆炸性成長、連網裝置數量（電腦、手機、物聯網設備等）的激增，IPv4 位址空間已基本耗盡。
   • IPv6 的巨大位址空間： IPv6 使用 128 位元來表示位址，總共可以提供 $2^{128}$ 個位址，這個數量極其龐大，足以滿足未來數十億甚至兆級的設備連網需求，幾乎可以為地球上的每一個顆粒提供一個獨立的 IP 位址。
   • 其他原因（輔助）：
     • 簡化報頭（Simplified Header）： IPv6 的報頭結構比 IPv4 更為簡單和高效，有利於路由器處理。
     • 更好的支援行動性（Mobility）： IPv6 在設計上對行動 IP 有更好的支援。
     • 更有效的路由（Efficient Routing）： 透過更優化的位址結構和路由演算法，IPv6 可以實現更小的路由表和更高效的路由。
     • 內建安全性（IPsec）： IPv6 內建了對 IPsec 的支援，雖然 IPv4 也可以透過額外配置實現，但 IPv6 將其作為標準的一部分。
     • 無狀態自動設定（Stateless Autoconfiguration）： IPv6 允許設備在沒有 DHCP 伺服器的情況下，也能夠自動配置 IP 位址。

2. 何為 NAT 機制？
   NAT（Network Address Translation，網路位址轉換）是一種在 IP 數據包通過路由器或防火牆時，修改其 IP 位址和埠號資訊的技術。

   • 主要功能： 允許一個組織內部使用私有 IP 位址（Private IP Addresses）的網路，與網際網路上的公共 IP 位址（Public IP Addresses）進行通訊。
   • 工作原理： 當內部主機發送資料包到外部網路時，NAT 設備（通常是路由器）會將資料包的來源 IP 位址（私有 IP）和來源埠號，轉換為 NAT 設備的公共 IP 位址和一個新的埠號。當外部網路回傳資料包時，NAT 設備會根據儲存的轉換表，將資料包的目標 IP 位址（公共 IP）和目標埠號，還原回原來的私有 IP 位址和埠號，再轉發給內部主機。
   • 主要目的是： 緩解 IPv4 位址枯竭的問題，讓大量使用私有 IP 位址的設備共享少量的公共 IP 位址。

3. 其通常會搭配何種 IP 以使用之？
   NAT 機制通常會搭配**私有 IP 位址（Private IP Addresses）**來使用。

本題考察學生對關聯式資料庫正規化（Normalization）的理解，包括其目的、意義，以及第二和第三正規化（2NF, 3NF）的定義與判斷標準。

核心觀念： 正規化是關聯式資料庫設計中的一個關鍵過程，旨在減少資料冗餘、消除資料異常，並提高資料的一致性和完整性。

詳解：

1. 為何後續需要進行正規化（Normalization）的處理？其主要意涵為何？

   • 目的： 正規化是關聯式資料庫設計中的一個系統化過程，旨在將一個資料庫的表結構組織得更合理，以達到以下目標：

     1. 減少資料冗餘（Reduce Data Redundancy）： 避免同一份資料在多處重複儲存。
     2. 消除資料異常（Eliminate Data Anomalies）：
        • 插入異常（Insertion Anomaly）： 當新增一筆資料時，可能需要額外添加不相關的資訊，或者無法新增單獨的資訊。
        • 刪除異常（Deletion Anomaly）： 當刪除一筆資料時，可能導致其他不相關的資訊也被一併刪除。
        • 更新異常（Update Anomaly）： 當更新一筆資料時，可能需要在多處進行更新，若有遺漏，則會造成資料不一致。
     3. 提高資料的一致性與完整性（Improve Data Consistency and Integrity）： 透過減少冗餘和異常，確保資料的準確性和可靠性。
     4. 簡化資料庫結構： 將大型、複雜的表分解成更小、更專注的表，使結構更清晰，易於理解和維護。

   • 主要意涵： 正規化的核心意涵在於**「將資料依據其所屬的實體或關係進行劃分，並確保每個表只描述一個主題（或實體集），且表中的屬性（欄位）都與該表的主鍵（Primary Key）直接相關。」** 透過這種方式，可以建立一個結構良好、易於管理且資料冗餘最小化的資料庫。

2. 何為第二正規化（Second Normal Form, 2NF）？

   • 定義： 一個關係模式（表）若滿足第一正規化（1NF），並且其每一個非主屬性（non-prime attribute）都完全函數依賴於其主鍵（primary key），則稱該關係模式滿足第二正規化（2NF）。
   • 判斷標準：
     1. 首先，該表必須已經是 1NF（即表中的所有屬性值都是原子值，沒有重複群組）。
     2. 其次，檢查表的主鍵。如果主鍵是單一屬性，則該表自動滿足 2NF。
     3. 如果主鍵是複合屬性（由多個屬性組成），則需要檢查是否存在非主屬性，它只依賴於主鍵的一部分，而不是整個主鍵。如果存在這種情況，就存在部分函數依賴（Partial Functional Dependency），該表就不滿足 2NF。
   • 如何達到 2NF： 如果一個表不滿足 2NF，可以通過將部分函數依賴分解成新的表來達到 2NF。例如，如果表 R 有主鍵 {A, B} 和非主屬性 C，且 C 只依賴於 A（A → C），則將表 R 分解為：
     • 表 R1：主鍵 {A, B}，屬性 ...
     • 表 R2：主鍵 {A}，屬性 C
   • 範例： 假設有一個 OrderDetails 表，主鍵是 {OrderID, ProductID}，包含 Quantity 和 ProductName。