111 年 國立中央大學網路學習科技研究所《計算機概論》

本題考驗二進位數轉換為十六進位的基本能力。

解題步驟：

1. 將二進位數 $10010_2$ 從右邊開始，每四位數為一組進行分組。如果最左邊的組不足四位，則在前面補零。
   $10010_2$ 分組後為 $1 \mid 0010$。
2. 在不足四位的組前面補零，使其成為四位數：$0001 \mid 0010$。

本題考驗對基本邏輯運算符 (AND, XOR, OR, NOR) 的理解與應用。

解題步驟：
我們要找出哪種邏輯運算能夠將 $0011$ 和 $1101$ 運算後得到 $1110$。我們逐一測試選項：

1. AND 運算：
   $0011 \text{ AND } 1101$
   逐位元進行 AND 運算：
   $0 \text{ AND } 1 = 0$
   $0 \text{ AND } 1 = 0$
   $1 \text{ AND } 0 = 0$
   $1 \text{ AND } 1 = 1$
   結果為 $0001$。這與題目要求的 $1110$ 不符。

2. XOR 運算：
   $0011 \text{ XOR } 1101$
   逐位元進行 XOR 運算：
   $0 \text{ XOR } 1 = 1$
   $0 \text{ XOR } 1 = 1$

本題考驗對電腦記憶體種類及其特性的基本認識。

各選項分析：
(A) 記憶體（Memory）是電腦用於存放程式指令和資料（包括輸入的資料、處理中的資料以及輸出的結果）的核心部件。這個敘述是正確的。

(B) DRAM (Dynamic Random Access Memory) 的基本記憶單元是由一個電容器（Capacitor）和一個電晶體（Transistor）組成。電容器用於儲存電荷，代表 0 或 1 的狀態。由於電容器會漏電，需要週期性地刷新（Refresh）來維持資料，因此稱為「動態」。這個敘述是正確的。

本題考驗對 RAID (Redundant Array of Independent Disks) 技術中不同等級 (Level) 的容錯 (Fault Tolerance) 能力的了解。

各 RAID Level 的容錯能力分析：

• RAID 0 (Striping)：資料被分割成區塊，並分散儲存在多個硬碟上。這種方式可以提高讀寫效能，但沒有任何冗餘。如果其中任何一個硬碟發生故障，整個陣列的資料都會丟失。因此，RAID 0 不具有容錯能力。

• RAID 1 (Mirroring)：資料被完整地複製到兩個或多個硬碟上。這提供了高度的容錯能力，因為如果其中一個硬碟故障，陣列仍然可以從另一個硬碟讀取資料。

本題考驗二補數 (Two's Complement) 的計算方法。二補數是電腦中表示帶符號整數的標準方法。

假設我們要計算 $-3$ 的二補數，並且預設是 4 位元 (bits) 的表示。

計算步驟：

1. 找出 3 的二進位表示：
   在 4 位元系統下，3 的二進位表示是 $0011_2$。

2. 對 3 的二進位表示進行位元反轉 (One's Complement)：
   將 $0011$ 的每一位元反轉：$0$ 變為 $1$，$1$ 變為 $0$。
   $0011$ 反轉後得到 $1100$。

本題考驗對 RAM (Random Access Memory) 和 ROM (Read-Only Memory) 在斷電後是否保留資料的特性。

• RAM (Random Access Memory)：RAM 是一種揮發性記憶體 (Volatile Memory)。這意味著它需要持續的電力供應來維持其儲存的資料。

本題考驗對物件導向程式設計 (Object-Oriented Programming, OOP) 中基本概念的理解。

各選項解釋：

• (A) 類別 (Class)：類別是物件的藍圖或模板。它定義了一組共同的屬性 (Attributes) 和行為 (Methods)，這些屬性代表物件的狀態，而行為代表物件可以執行的操作。一個類別可以創建出多個具有相同結構和行為的物件。因此，類別代表了一群相似物件的共同定義。

• (B) 繼承 (Inheritance)：繼承是一種機制，允許一個類別（子類別或派生類別）繼承另一個類別（父類別或基底類別）的屬性和方法。

本題考驗對 OSI (Open Systems Interconnection) 模型七層架構中各層的功能及代表性協定的了解。

OSI 模型七層架構及其主要功能：

1. 應用層 (Application Layer)：提供網路服務給終端使用者應用程式。
2. 表現層 (Presentation Layer)：負責資料的格式化、加密與解密。
3. 會議層 (Session Layer)：負責建立、管理和終止應用程式之間的通訊會話。
4. 傳輸層 (Transport Layer)：負責端對端 (End-to-End) 的資料傳輸，確保資料的可靠性（如 TCP）或效率（如 UDP）。它也負責流量控制和錯誤恢復。

本題考驗對雲端運算三大服務模式 (SaaS, IaaS, PaaS) 的基本理解，特別是與儲存裝置的關聯。

雲端運算的服務模式：

• (A) Software as a Service (SaaS)：使用者透過網路存取由雲端供應商提供的應用程式。例如 Gmail, Dropbox。SaaS 提供了完整的軟體應用，使用者無需管理底層的基礎設施或平台。雖然 SaaS 應用可能使用儲存裝置，但 SaaS 本身不直接代表「使用儲存裝置」的服務。

• (B) Infrastructure as a Service (IaaS)：使用者透過網路存取基本的計算資源，包括伺服器、儲存空間、網路和作業系統。IaaS 提供了最底層的基礎設施，使用者可以自行配置和管理。透過 IaaS，使用者可以租用和使用雲端的儲存裝置，例如虛擬硬碟、物件儲存等。

本題考驗對網路基本名詞和功能的了解，特別是 DNS 的作用。

各選項解釋：

• (A) 網域名稱伺服器 (DNS - Domain Name System)：DNS 的主要功能就是提供網域名稱與 IP 位址之間的對應查詢服務。當使用者在瀏覽器輸入網域名稱（例如 www.google.com）時，電腦會透過 DNS 伺服器來查詢該網域名稱所對應的 IP 位址，然後才能與該網站的伺服器建立連線。

本題考驗對不同類型程式語言及編譯/解釋過程的理解。

各選項分析：

• (A) 自然語言是用一連串的 0 與 1 來代表資料或指令。
  這是錯誤的。用一連串的 0 與 1 來代表資料或指令的是機器語言 (Machine Language)，它是電腦 CPU 直接能理解和執行的語言。自然語言 (Natural Language) 是人類日常使用的語言，如中文、英文等，其結構複雜且非結構化，不適合電腦直接執行。

• (B) 機器語言佔用記憶體少,執行時間短。
  這是正確的。機器語言是電腦硬體能直接執行的指令碼，不需要經過翻譯，因此執行速度最快，佔用記憶體也相對較少（相較於需要編譯或解釋的高階語言）。

核心觀念

Deadlock（死結）是指一組程序彼此等待對方所持有的資源，導致所有程序都無法繼續執行。

作業系統中，deadlock 成立的必要條件通常以 Coffman 四大必要條件表示：

1. 互斥（Mutual Exclusion）：某些資源同一時間只能由一個程序使用。
2. 持有並等待（Hold and Wait）：程序已持有部分資源，同時等待其他資源。
3. 不可剝奪（No Preemption）：程序持有的資源不能被系統強制取回，只能由程序自行釋放。
4. 循環等待（Circular Wait）：形成程序與資源之間的循環等待關係。

只要破壞其中一項，就能避免 deadlock。

解題方法

本題問的是「何者不是造成系統資源 deadlock 的主要原因」，因此逐一對照各選項是否會促成上述必要條件。

重點在於辨認：

• 「不可中斷」對應不可剝奪。
• 「分階段要求資源」對應持有並等待。
• 「多重任務」提供程序彼此同時競爭與等待的環境。
• 真正容易造成 deadlock 的是不可同時共享的資源，而不是可以同時共享的資源。

選項分析

(A) 同時有多重任務的設計

正確。多重任務環境中，許多程序可能同時執行並競爭 CPU、記憶體、檔案、I/O 裝置等資源。

若程序彼此持有資源並等待其他程序釋放資源，就可能形成循環等待。因此，多重任務是 deadlock 發生的重要背景條件。

(B) 不可中斷其他程序

正確。此選項對應 Coffman 條件中的「不可剝奪」。

核心觀念

本題考查網際網路常見應用層協定的功能：

• DNS（Domain Name System）：將網域名稱解析為 IP 位址；反向解析則是將 IP 位址查回網域名稱。
• SMTP（Simple Mail Transfer Protocol）：負責電子郵件的寄送與郵件伺服器間的轉送。
• FTP（File Transfer Protocol）：用於檔案傳輸，傳統 FTP 不會加密帳號與密碼。
• MIME（Multipurpose Internet Mail Extensions）：使電子郵件能夠攜帶圖片、文件等非純文字內容。

解題方法

先判斷每個選項對協定功能的描述是否符合定義。特別注意 DNS 的「正向解析」與「反向解析」方向：

• 正向 DNS：網域名稱 $\rightarrow$ IP 位址
• 反向 DNS：IP 位址 $\rightarrow$ 網域名稱

題目將 DNS 描述為「IP 到域名的解析」，這是反向 DNS 的方向，並非一般所指的 DNS 網域名稱解析，因此此敘述錯誤。

選項分析

(A) DNS 是提供 IP 到域名的解析。

錯誤。一般 DNS 最基本的功能是將網域名稱解析為 IP 位址，例如：

$$www.example.com \rightarrow 93.184.216.34$$

IP 位址查回網域名稱屬於反向 DNS（Reverse DNS），常透過 PTR 紀錄完成。若題目直接描述一般 DNS 的主要功能，標準答案應為「網域名稱到 IP 位址」，因此本選項的方向描述錯誤。

(B) 電子郵件是用 SMTP 發到傳送方郵件伺服器。

本題考驗將中序表達式 (Infix Expression) 轉換為後序表達式 (Postfix Expression) 的能力。後序表達式也稱為逆波蘭表示法 (Reverse Polish Notation, RPN)。

轉換規則：
我們需要遵循運算子優先順序（乘除優先於加減）和結合性（通常是從左到右）來進行轉換。

中序表達式：$A*B+C-D/E$

轉換步驟：

1. 識別運算子優先順序：

   • 乘 (*) 和除 (/) 的優先順序最高。
   • 加 (+) 和減 (-) 的優先順序較低。
   • 在相同優先順序的運算子之間，從左到右結合。

2. 應用轉換規則：
   我們可以使用堆疊 (Stack) 來輔助轉換。

   • 掃描中序表達式。
   • 遇到運算元 (Operand)，直接輸出到後序表達式。
   • 遇到運算子 (Operator)：
     • 如果堆疊為空，或堆疊頂端運算子的優先順序低於當前運算子，則將當前運算子壓入堆疊。
     • 如果堆疊頂端運算子的優先順序高於或等於當前運算子，則將堆疊頂端的運算子彈出並輸出，直到堆疊頂端的運算子優先順序低於當前運算子，或堆疊為空，然後將當前運算子壓入堆疊。
   • 掃描完所有運算元和運算子後，將堆疊中剩餘的運算子依序彈出並輸出。

讓我們逐步轉換 $A*B+C-D/E$:

• 掃描 A：輸出 A。後序：A
• 掃描 *：堆疊為空，壓入 。堆疊：[]
• 掃描 B：輸出 B。後序：A B
• 掃描 +：* 的優先順序高於 +。彈出 *，輸出 *。後序：A B *。然後壓入 +。堆疊：[+]

本題考驗對資料庫正規化 (Database Normalization) 的目的和好處的理解。

資料庫正規化是資料庫設計中的一個重要過程，旨在通過將大型表格分解為較小的、結構良好的表格，並定義表格之間的關係，來減少資料冗餘 (Data Redundancy) 和改進資料的完整性 (Data Integrity)。

正規化的主要好處包括：

1. 減少資料冗餘 (Reduce Data Redundancy)：通過將資料分解到不同的表中，避免同一資訊在多個地方重複儲存。這直接有助於減少資料異常 (Data Anomalies)，如插入異常 (Insertion Anomaly)、刪除異常 (Deletion Anomaly) 和更新異常 (Update Anomaly)。例如，如果一個地址在多個地方重複儲存，更新地址時必須在所有地方都修改，否則就會產生不一致。正規化後，地址只需要儲存在一個地方。

2. 提高資料完整性 (Improve Data Integrity)：通過減少冗餘和異常，確保資料的一致性和準確性。

3. 簡化資料庫結構 (Simplify Database Structure)：將大型、複雜的表分解成更小、更專注的表，使得資料庫的結構更清晰。

本題考驗對循序搜尋法 (Sequential Search) 和二分搜尋法 (Binary Search) 的時間複雜度與前提條件的理解。

假設總共有 $N = 10,000$ 筆資料。

循序搜尋法 (Sequential Search)：

• 前提條件：不需要資料預先排序。
• 搜尋方式：從第一個元素開始，逐一與目標值比較，直到找到目標或遍歷完所有元素。
• 時間複雜度：
  • 最佳情況：目標值是第一個元素，只需搜尋 1 次。
  • 最差情況：目標值是最後一個元素，或目標值不存在，需要搜尋 $N$ 次。
  • 平均情況：假設目標值平均分佈在所有位置，平均需要搜尋 $(1+N)/2$ 次。
• 對於 $N=10,000$：
  • 最多搜尋 10,000 次。
  • 平均約需 $(1+10000)/2 \approx 5000.5$ 次。

二分搜尋法 (Binary Search)：

• 前提條件：資料必須是預先排序的。
• 搜尋方式：每次將搜尋範圍縮小一半。比較中間元素與目標值，如果目標值較小，則在前半部分繼續搜尋；如果目標值較大，則在後半部分繼續搜尋。
• 時間複雜度：
  • 最佳情況：目標值剛好是中間元素，只需搜尋 1 次。
  • 最差情況：每次都將搜尋範圍縮小，直到範圍為 1。其複雜度為 $O(\log_2 N)$。
• 對於 $N=10,000$：
  • 最多搜尋的次數約為 $\lceil \log_2 10000 \rceil$。
  • $2^{10} = 1024$
  • $2^{13} = 2^{10} \times 2^3 = 1024 \times 8 = 8192$

本題考驗對資料探勘中非監督學習 (Unsupervised Learning) 和監督學習 (Supervised Learning) 的區別，以及分群 (Clustering) 演算法的特性。

非監督學習 (Unsupervised Learning)：

• 特點：訓練資料不包含標籤 (labels) 或目標變數 (target variable)。演算法的目標是從資料中發現潛在的結構、模式或關聯。
• 常見任務：分群 (Clustering)、降維 (Dimensionality Reduction)、關聯規則挖掘 (Association Rule Mining)。

監督學習 (Supervised Learning)：

• 特點：訓練資料包含輸入特徵和對應的標籤。演算法的目標是學習一個映射關係，能夠對新的、未見過的資料進行預測或分類。
• 常見任務：分類 (Classification)、迴歸 (Regression)。

本題考驗對 C 語言函式執行的理解，特別是陣列操作和迴圈的行為。

函式 f 的目的是找出陣列中最大值的索引 (index)。

函式參數：

• a[]: 整數陣列，包含 10 個元素。
• n: 陣列的大小，這裡為 10。

函式執行步驟：

1. int index = 0;：初始化一個變數 index，並設為 0。這個變數將用來記錄目前為止找到的最大值的索引。初始時，我們假設 a[0] 是最大的。

2. for (int i=1; i<=n-1; i=i+1)：開始一個迴圈，變數 i 從 1 開始，一直到 n-1 (也就是 9)，每次遞增 1。迴圈會遍歷陣列中從索引 1 到索引 9 的元素。

3. if (a[i] > a[index]) { index = i; }：在迴圈的每一次迭代中，比較當前元素 a[i] 與目前記錄的最大值 a[index]。

   • 如果 a[i] 大於 a[index]，表示我們找到了目前為止更大的值，因此更新 index 為當前元素的索引 i。
   • 如果 a[i] 不大於 a[index]，則 index 保持不變。

4. return index;：迴圈結束後，index 變數將會是陣列中最大元素的索引。函式回傳這個 index 值。

現在，我們逐步跟蹤函式使用陣列 a[10]={1, 3, 9, 2, 5, 8, 4, 9, 6, 7} 來執行：

• 初始：index = 0 (對應值 a[0]=1)

• i = 1: a[1]=3。3 > a[index](1) ? 是。 index = 1。 (目前最大值索引為 1，值為 3)

• i = 2: a[2]=9。9 > a[index](3) ? 是。 index = 2。 (目前最大值索引為 2，值為 9)

• i = 3: a[3]=2。2 > a[index](9) ? 否。 index 保持為 2。

• i = 4: a[4]=5。5 > a[index](9) ? 否。 index 保持為 2。

• i = 5: a[5]=8。8 > a[index](9) ? 否。 index 保持為 2。

• i = 6: a[6]=4。4 > a[index](9) ? 否。 index 保持為 2。

• i = 7: a[7]=9。9 > a[index](9) ? 否 (因為是 >)。 index 保持為 2。
  注意：這裡有兩個 9。由於條件是 a[i] > a[index]，當遇到第二個 9 時，a[7] (9) 並不嚴格大於 a[2] (9)，所以 index 不會更新。這意味著函式會回傳第一個出現的最大值的索引。

• i = 8: a[8]=6。6 > a[index](9) ? 否。 index 保持為 2。

• i = 9: a[9]=7。7 > a[index](9) ? 否。 index 保持為 2。

本題考驗對 C 語言迴圈和陣列操作的理解，以及程式執行的追蹤。

程式碼分析：

1. 第一個迴圈：

   for (i=1; i<=100; i=i+1) {
       b[i] = i;
   }
   

   這個迴圈將陣列 b 的元素從索引 1 到 100 進行初始化。
   b[1] = 1
b[2] = 2
   ...
   b[100] = 100
   注意：這個迴圈從 i=1 開始，所以 b[0] 的值未定義（或保持其初始值，如果有的話）。這裡假設 b 是一個足夠大的陣列，至少有 101 個元素。

2. 初始化 a[0]：

   a[0] = 10;
   

   將陣列 a 的第一個元素 a[0] 設定為 10。

3. 第二個迴圈：

   for (i=1; i<=100; i=i+1) {
       a[i] = b[i] + a[i-1];
   }
   

   這個迴圈根據前一個 a 的值和 b 的值來計算 a[i]。這是一個遞迴關係。
   讓我們展開幾項來觀察規律：

   • i = 1: a[1] = b[1] + a[0] = 1 + 10 = 11
   • i = 2: a[2] = b[2] + a[1] = 2 + 11 = 13
   • i = 3: a[3] = b[3] + a[2] = 3 + 13 = 16
   • i = 4: a[4] = b[4] + a[3] = 4 + 16 = 20

本題考驗對遞迴函式 (Recursive Function) 的理解與追蹤。

函式 a(n, m) 的定義如下：

• 基本情況 1：如果 n < 10 且 m < 10，則直接回傳 n + m。
• 遞迴情況 1：如果 n < 10 且 m >= 10，則回傳 a(n, m-2) + m。
• 遞迴情況 2：如果 n >= 10，則回傳 a(n-1, m) + n。

我們需要計算 a(11, 12) 的回傳值。

逐步追蹤函式呼叫：

1. 呼叫 a(11, 12)：

   • n = 11, m = 12。
   • n >= 10 (11 >= 10) 是 true。
   • 執行 return a(n-1, m) + n;
   • 即 return a(11-1, 12) + 11;
   • 即 return a(10, 12) + 11;
   • 我們需要先計算 a(10, 12)。

2. 呼叫 a(10, 12)：

   • n = 10, m = 12。
   • n >= 10 (10 >= 10) 是 true。
   • 執行 return a(n-1, m) + n;
   • 即 return a(10-1, 12) + 10;
   • 即 return a(9, 12) + 10;
   • 我們需要先計算 a(9, 12)。

3. 呼叫 a(9, 12)：

   • n = 9, m = 12。
   • n < 10 (9 < 10) 是 true。
   • 檢查 m < 10。m = 12，所以 m < 10 是 false。