113 年 國立中山大學資訊管理學系碩士班甲組《計算機概論》

此題主要在考驗 CPU 的基本架構與指令執行流程。CPU 的 fetch-decode-execute-store 週期是執行指令的標準步驟。

• Fetch: 從記憶體中取出下一條指令。
• Decode: 解碼指令，確定需要執行的操作以及操作數。
• Execute: 執行指令的操作。
• Store: 將指令執行的結果寫回記憶體或暫存器。

此題考驗對常見網路協定（TCP, UDP, DNS, HTTP, FTP）特性與運作方式的理解。

• A. UDP builds up reliable connections.
  UDP (User Datagram Protocol) 是一種無連接的協定，它不提供可靠性保證，例如封包序號、確認應答、重傳機制等。TCP (Transmission Control Protocol) 則是提供可靠連接的協定。因此，此敘述是錯誤的。

• B. DNS queries are transmitted through UDP.
  DNS (Domain Name System) 主要使用 UDP 協定來傳遞查詢請求和回應。

此題考驗對物聯網 (IoT) 的基本概念、特性與應用範疇的理解。

• A. For security purpose, IoT devices should be deployed in internal network.
  這是一個常見的安全建議。將 IoT 設備部署在內部網路（或透過防火牆隔離的 DMZ 區域）可以限制其直接暴露於外部網路的風險，降低被攻擊的可能性。這有助於提高安全性。此敘述是正確的。

• B. All IoT devices have connectivity.
  物聯網的核心概念是「連接」與「物體」。IoT 設備通過網路（有線或無線）互相連接，並與雲端或伺服器通信，以收集、交換和處理數據。如果沒有連接性，就無法實現物聯網的功能。此敘述是正確的。

• C. Bluetooth earphones are IoT devices.

此題考驗對無線網路（特別是 Wi-Fi，即 802.11 標準）相關概念的理解。

• A. Wireless networks have the exposed node problem.
  Exposed Node Problem（暴露節點問題）是指一個節點 A 正在與節點 B 通信，而另一個節點 C 雖然與 B 不在同一通信範圍內，但與 A 在同一通信範圍內，卻因為 A 和 B 的通信而無法與 C 通信。這與隱藏節點問題相反，是無線網路中可能存在的一種衝突情況。雖然隱藏節點問題更為人熟知，但暴露節點問題也是無線網路的潛在問題。此敘述是正確的。

• B. Wireless networks have the hidden node problem.
  Hidden Node Problem（隱藏節點問題）是無線網路（尤其是在共享介質上）的一個經典問題。當節點 A 和節點 C 都與節點 B 通信，但 A 和 C 之間無法直接通信時，A 發送數據給 B 可能會與 C 發送數據給 B 發生碰撞，因為 A 和 C 聽不到對方的傳輸，無法協調。此敘述是正確的。

核心觀念

• 二元樹的遍歷：
  • 中序 (Inorder)：左子樹 → 根 → 右子樹
  • 後序 (Postorder)：左子樹 → 右子樹 → 根
  • 先序 (Preorder)：根 → 左子樹 → 右子樹
• 樹的唯一還原：給定中序與後序（或先序）序列，可唯一建構二元樹。重建方法：後序最後一個節點即為根，根在中序中的位置將左、右子樹的節點數目決定，進而將後序切分為左、右子樹的後序子序列，遞迴重建。

---

解題方法

1. 找根節點

   • 後序遍歷的最後一個字元即為整棵樹的根。
   • postorder = G O O O B K O **D** → 根 = D。

2. 分割中序

   • 在中序 GOODBOOK 中找根 D，位置在第 4 個字元。
   • 左子樹中序 = GOO，右子樹中序 = BOOK.

3. 切割後序（根已移除）

   • 左子樹節點數 = 3 → 取前 3 個字元作左子樹後序 → GOO。
   • 其餘 4 個字元作右子樹後序 → OBKO.

4. 遞迴重建左子樹

   • 後序 GOO 的最後一個字元為根 → O。
   • 中序 GOO 中最後一個 O（第 3 位）左側為 GO，右側空。
   • 左子樹後序切為 GO，再遞迴：根 = O，左子樹中序 G，左子樹後序 G → 左葉為 G。
   • 左子樹的先序 = O O G.

5. 遞迴重建右子樹

   • 後序 OBKO 最後一個字元為根 → O。
   • 中序 BOOK 中選取第 3 位的 O（左子樹 BO，右子樹 K）。

此題考驗對雜湊表 (Hash Table) 基本特性、時間複雜度及雜湊函數的理解。

• A. In the average cases, search in a hash table is O(1).
  在理想情況下，雜湊函數能將鍵均勻地分布到雜湊表中，且沒有或只有少量衝突。此時，查找操作（搜尋）平均時間複雜度為常數時間 $O(1)$。此敘述是正確的。

• B. In the average cases, insert in a hash table is O(1).
  與搜尋操作類似，在平均情況下，插入操作也只需計算雜湊值並將元素放入對應的桶 (bucket) 中，時間複雜度為 $O(1)$。此敘述是正確的。

此題考驗對 ARP (Address Resolution Protocol) 的功能、定位及其運作方式的理解。

• A. ARP is used to build up a mapping table of IP addresses to MAC addresses.
  ARP 的主要功能就是透過 ARP 請求和 ARP 回應，建立和維護一個 IP 位址與對應 MAC 位址之間的對應表。當一個主機知道目標主機的 IP 位址，但不知道其 MAC 位址時，就會發送 ARP 請求。此敘述是正確的。

• B. ARP is a network protocol at the network layer of the OSI model.
  ARP 協定工作在 OSI 模型中的網路層 (Network Layer) 和資料連結層 (Data Link Layer) 之間，用於將網路層的 IP 位址解析為資料連結層的 MAC 位址。嚴格來說，它被認為是介於這兩層之間，或者說是網路層的輔助協定，負責 IP 位址到 MAC 位址的解析。

此題考驗對惡意軟體 (malware) 的傳播途徑和安全風險的認識。

• A. A computer might be infected without connecting to a network.
  這是正確的。惡意軟體可以透過多種非網路途徑傳播，例如：USB 隨身碟、外接硬碟、光碟片，或者透過社交工程誘騙使用者執行帶有惡意程式的檔案。

• B. PDF files may contain malware.
  這是正確的。PDF 文件格式本身可以嵌入腳本 (scripts) 或利用 PDF 閱讀器的漏洞，從而攜帶惡意程式。使用者開啟惡意 PDF 文件時，可能觸發惡意程式的執行。

此題考驗對不同處理程序排程演算法（FIFO, Round-Robin）的特性與優缺點的理解。

• A. FIFO scheduling may result long waiting time.
  FIFO (First-In, First-Out) 或 FCFS (First-Come, First-Served) 排程演算法，是按照程序到達的順序執行。如果一個長作業先到達，它會阻塞後面所有到達的作業，導致後來的作業產生很長的等待時間。因此，此敘述是正確的。

• B. Round-robin scheduling has the shortest waiting time.
  Round-robin (RR) 排程為每個程序分配一個固定的時間片 (time quantum)。雖然 RR 旨在提供公平性並縮短平均等待時間，但它不保證擁有最短的等待時間。例如，在某些情況下，短作業可能被切斷多次，反而增加其總等待時間。

核心觀念

以陣列表示完整二元樹時，通常採用「根節點索引為 $1$」的編號方式：

• 根節點位於索引 $1$
• 節點 $i$ 的左子節點位於索引 $2i$
• 節點 $i$ 的右子節點位於索引 $2i+1$

因此，左子節點的位置公式為：

$$\operatorname{LeftChild}(i)=2i$$

解題方法

依照 1-based array indexing 的二元樹表示法，節點位置按照層序排列：

$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ldots$$

例如：

• 根節點 $1$ 的左子節點為 $2=2(1)$
• 根節點 $1$ 的右子節點為 $3=2(1)+1$
• 節點 $2$ 的左子節點為 $4=2(2)$
• 節點 $2$ 的右子節點為 $5=2(2)+1$

所以節點 $i$ 的左子節點索引為 $2i$。

選項分析

• A. $2i$：正確。
  在根節點索引從 $1$ 開始的陣列表示法中，這就是左子節點的位置公式。

此題考驗對邏輯學中「重言式」(Tautology) 的理解，以及判斷邏輯敘述真偽的能力。重言式是指無論其組成命題的真假值為何，整個複合敘述的值恆為真。

我們需要逐一檢驗每個選項，通常可以使用真值表 (Truth Table) 來判斷。令 $p$ 和 $q$ 為命題變數。

選項 A: $(p \land q) \rightarrow q$

$p$	$q$	$p \land q$	$(p \land q) \rightarrow q$
T	T	T	T $\rightarrow$ T = T
T	F	F	F $\rightarrow$ F = T
F	T	F	F $\rightarrow$ T = T
F	F	F	F $\rightarrow$ F = T
此敘述恆為真，是重言式。

選項 B: $q \rightarrow (p \land q)$

$p$	$q$	$p \land q$	$q \rightarrow (p \land q)$
T	T	T	T $\rightarrow$ T = T
T	F	F	F $\rightarrow$ F = T
F	T	F	T $\rightarrow$ F = F
F	F	F	F $\rightarrow$ F = T
此敘述在 $p=F, q=T$ 時為假，不是重言式。

選項 C: $p \lor (p \rightarrow q)$
我們知道 $p \rightarrow q$ 等價於 $\neg p \lor q$。

此題考驗對邏輯推論規則 (Inference Rules) 的「可靠性」(Soundness) 的理解。一個推論規則是可靠的，意味著如果前提 (Premise) 為真，則其結論 (Conclusion) 也必定為真。

我們逐一檢驗每個選項：

A. Premise: p, p→q; conclusion: q
這是一個經典的邏輯推論規則，稱為假言推理 (Modus Ponens)。
如果 $p$ 為真，且 $p \rightarrow q$ 為真，那麼根據蘊含的定義 ($p \rightarrow q$ 為真，當 $p$ 為真時，$q$ 必須為真)，結論 $q$ 必定為真。
此規則是可靠的。

B. Premise: p, q; conclusion: p∧q
這是一個邏輯推論規則，稱為合取引入 (Conjunction Introduction) 或 **合取規則 (Rule of Con

核心觀念

本題比較兩種資料結構中「搜尋」與「插入」的時間複雜度：

• 雙向鏈結串列（double-linked list）
• 二元搜尋樹（binary search tree, BST）

其中 $N$ 表示資料筆數。

判斷時間複雜度時，必須區分：

1. 是否需要走訪節點以尋找目標位置。
2. 找到位置後，實際修改指標所需的時間。
3. 最佳、平均與最壞情況的差異。
4. 二元搜尋樹是否平衡。

---

解題方法

先分析每種資料結構的高度與走訪方式：

• 雙向鏈結串列沒有索引，搜尋通常必須由頭節點逐一走訪。
• 二元搜尋樹每次比較後可往左子樹或右子樹前進，因此複雜度與樹高 $h$ 有關。
• BST 搜尋複雜度為 $O(h)$：
  • 平衡時，$h = O(\log N)$。
  • 完全退化成鏈結串列時，$h = O(N)$。

---

選項分析

A. The average time complexity of search in a double-linked list is $O(N)$。

正確。

雙向鏈結串列沒有提供隨機存取能力。搜尋某個值時，通常必須從頭節點開始逐一比較。

若目標值平均位於串列中間，平均約需檢查：

$$\frac{N+1}{2}$$

個節點，因此平均時間複雜度為：

$$\Theta(N)$$

所以寫成 $O(N)$ 是正確的。

雙向鏈結串列雖然可以由前端或尾端雙向移動，但仍無法像陣列一樣直接跳到第 $k$ 個位置，因此不會改善一般搜尋的漸近複雜度。

---

B. The worst time complexity of insertion in a double-linked list is $O(N)$。

正確。

在雙向鏈結串列中，已知插入位置的節點指標時，實際插入只需調整有限個指標，例如：

$$\text{new.prev},\quad \text{new.next},\quad \text{prev.next},\quad \text{next.prev}$$

這部分是：

$$\Theta(1)$$

然而，題目未指明插入位置已經以節點指標提供。若必須先搜尋第 $k$ 個位置，最壞情況可能走訪整個串列，時間為：

$$\Theta(N)$$

因此，將「尋找插入位置」與「完成插入」合併考量時，插入操作的最壞時間複雜度為：

$$O(N)$$

此題需要分析給定的 C 語言程式碼，並根據不同的輸入數字，判斷其輸出結果是否正確。程式碼的功能是判斷輸入數字 $n$ 的性質，並輸出「屬於 N」或「屬於 P」。

程式碼邏輯分析：

1. 讀取輸入: 程式首先提示使用者輸入一個數字 $n$。
2. 處理小於等於 1 的數字: 如果 $n \le 1$，程式直接輸出「The number belongs to N」並結束。
3. 迴圈檢查因數: 如果 $n > 1$，程式進入一個迴圈，從 $i=2$ 開始，一直到 $i \le \sqrt{n}$。
   • 在迴圈中，它檢查 $n$ 是否能被 $i$ 整除 ($n \% i == 0$)。
   • 如果找到一個 $i$ 可以整除 $n$，則將變數 $c$ 加一 ($c++$)，並立即跳出迴圈 (break)。
4. 判斷輸出:
   • 迴圈結束後，如果 $c$ 仍然是 0 (表示沒有找到任何能整除 $n$ 的因數，在 $2$ 到 $\sqrt{n}$ 的範圍內)，則輸出「The number belongs to P」。
   • 如果 $c$ 大於 0 (表示至少找到了一個因數)，則輸出「The number belongs to N」。

程式判斷的性質：

• 輸出「The number belongs to N」的條件：

  • $n \le 1$
  • $n > 1$ 且存在一個 $i$ ($2 \le i \le \sqrt{n}$) 使得 $n \% i == 0$。
    這個條件意味著 $n$ 不是一個質數 (prime number)，或者 $n$ 是 1 或 0。
  • 如果 $n$ 是質數，則它沒有小於等於 $\sqrt{n}$ 的因數（除了 1）。
  • 如果 $n$ 是合數 (composite number)，它至少有一個因數 $i$ 使得 $2 \le i \le \sqrt{n}$。
  • 因此，當 $n \le 1$ 或 $n$ 是合數時，輸出 N。

• 輸出「The number belongs to P」的條件：

  • $n > 1$ 且在 $2 \le i \le \sqrt{n}$ 的範圍內，找不到任何 $i$ 可以整除 $n$。
    這個條件非常接近質數的定義。一個大於 1 的整數，如果它只有 1 和它本身兩個因數，那麼它就是質數。如果找不到 $2 \le i \le \sqrt{n}$ 的因數，意味著 $n$ 的所有因數（除了 1）都大於 $\sqrt{n}$。這只有在 $n$ 是質數時才可能發生。
  • 例如，如果 $n=7$ (質數)，$\sqrt{7} \approx 2.64$。迴圈檢查 $i=2$。$7 \% 2 \ne 0$。迴圈結束。$c=0$，輸出 P。

核心觀念

本題考查 遞迴的終止條件、呼叫返回時的執行順序，以及 C 語言字串的陣列範圍。此外，C 語言區分大小寫，選項 A 的 If 與合法關鍵字 if 必須分開判定。

反向輸出字串的方法，是先保存目前字元，再遞迴處理下一個字元，最後於遞迴返回時輸出保存的字元：

temp = str[index];
reverse(str, index + 1, n);
printf("%c", temp);

由於 printf 位於遞迴呼叫之後，最後保存的字元會最先輸出，形成反向順序。

解題方法

先確認 n 的意義，再追蹤索引與輸出順序。

原字串 "MIS@NSYSU is the best" 有 21 個可見字元。C 語言的字串常值會在末尾附加終止字元 '\0'，因此陣列共有 22 個元素：

$$n=\frac{\operatorname{sizeof}(a)}{\operatorname{sizeof}(a[0])}=22$$

各位置的意義如下：

索引	內容
0 到 20	字串的 21 個可見字元
21	終止字元 '\0'
22	超出陣列範圍，不可讀取

正確的初始呼叫應為：

reverse(a, 0, n);

若終止條件採用合法的小寫寫法：

if (index == n) return;

則遞迴會依序保存 a[0] 到 a[21]，呼叫至 index == 22 時直接返回，不會讀取 a[22]，因此沒有越界。

返回時的輸出順序為：

$$a[21],a[20],\ldots,a[0]$$

第一個輸出的是 '\0'，接著才是反向排列的可見字元。一般終端機上可見的結果為：

tseb eht si USYSN@SIM

輸出 NUL 與陣列越界是不同問題：前者是輸出一個通常不可見的字元，後者才是非法存取。本題未明訂輸出不得包含 NUL，不能僅憑多輸出 NUL 就排除小寫 if 版本的 A。

選項分析

核心觀念

• Proof of Work（工作量證明）：利用計算上困難、驗證上簡易的隨機性問題，讓節點必須投入大量算力才能產生有效的區塊。
• 雜湊函數 $H(\cdot)$：必須具備抗碰撞、抗預映射、輸出均勻分布等特性，常用 SHA‑256。
• 難度目標 $T$（Target）：由系統根據前 $N$ 個區塊的產出時間自動調整，使得全網平均每 $t$ 秒（如 10 分鐘）產出一個區塊。
• Nonce：區塊標頭的隨機數字，節點透過改變它來搜尋滿足 $H(\text{header} \parallel \text{nonce}) \le T$ 的雜湊值。
• 「最長鏈規則」：全網只接受累計工作量最大的鏈（即區塊數最多或總難度最高的鏈）作為正式狀態。

---

解題方法（Proof of Work 的完整流程）

1. 收集待確認的交易

   • 節點從記憶池（mempool）挑選若干筆合法交易，組成交易集合 $\mathcal{T}$。
   • 生成 Merkle 樹，計算根雜湊 $M = \text{MerkleRoot}(\mathcal{T})$。

2. 組建區塊標頭

   • $H_{\text{prev}}$：前一個區塊的雜湊。
   • $M$：本區塊的 Merkle 根。
   • $t$：時間戳（timestamp）。
   • $d$：當前難度位元（difficulty bits）。
   • $n$（nonce）：初始設為 $0$。
   • 區塊標頭 $B_{\text{header}} = (H_{\text{prev}}, M, t, d, n)$。

3. 計算工作量證明

   • 重複以下步驟直至找到滿足條件的 nonce：
     $\text{hash} = H\bigl(B_{\text{header}}\bigr)$
     $\text{若 } \text{hash} \le T \text{（即前 } d \text{ 位為 0）則停止}$
     • 若不滿足，將 $n \leftarrow n+1$，重新組合標頭再雜湊。
   • 期望嘗試次數為 $2^{d}$，即每次嘗試成功機率 $p = \frac{T}{2^{256}}$。

河內塔 (Tower of Hanoi) 問題是一個經典的遞迴問題。目標是將 $n$ 個大小不同的圓盤從起始柱 (Source, S) 透過一個輔助柱 (Auxiliary, A) 移到目標柱 (Destination, D)，並遵守以下規則：

1. 一次只能移動一個圓盤。
2. 較大的圓盤不能放在較小的圓盤上面。

遞迴解決思路如下：
若要將 $n$ 個圓盤從 A 移到 C，可以使用輔助柱 B：

1. 將上面的 $n-1$ 個圓盤從 A 透過 C 移到 B。
2. 將第 $n$ 個（最大）圓盤從 A 移到 C。
3. 將 $n-1$ 個圓盤從 B 透過 A 移到 C。

基本情況是當 $n=1$ 時，直接將圓盤從 A 移到 C。

以下是使用 C 語言實現的遞迴函數：

TTL (Time To Live) 是 IP (Internet Protocol) 協定標頭 (header) 中的一個欄位，用於防止封包在網路上無限循環傳遞。

TTL 的主要功能與運作方式：

1. 防止封包無限循環：
   在網路傳輸過程中，封包可能會因為網路配置錯誤、路由迴圈等原因而陷入不斷轉發的迴圈，永遠無法到達目的地。TTL 欄位就是為了避免這種情況發生。

2. 設定生存時間：

   • TTL 欄位的值是一個 8 位元 (bit) 的整數，其最大值為 255。
   • 當封包從原始發送端發出時，發送端會設定一個初始的 TTL 值（通常由作業系統決定，例如 64, 128, 255 等）。
   • 每當封包經過一個路由器 (router) 時，該路由器會將 TTL 值減 1。

3. 封包的終結：

   • 當封包的 TTL 值減到 0 時，路由器會丟棄該封包，並且通常會向封包的來源主機發送一個 ICMP (Internet Control Message Protocol) 錯誤訊息（TTL exceeded in transit）。

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) 是一種用於早期有線乙太網路（特別是共享式集線器環境）的媒體存取控制 (MAC) 方法。它的目的是讓多個節點能夠在共享的傳輸介質（如同軸電纜）上進行通訊，同時盡量減少或處理傳輸衝突。

CSMA/CD 的步驟描述：

1. 載波偵聽 (Carrier Sense):

   • 在傳送資料之前，每個節點會先監聽網路介質，判斷是否有其他節點正在傳輸資料。
   • 如果介質是空閒的（沒有載波信號），則節點可以準備傳送。
   • 如果介質正忙，節點則必須等待，直到介質變為空閒。

2. 多重存取 (Multiple Access):

   • 多個節點可以同時監聽並在介質空閒時嘗試傳送資料。這意味著介質是被多個節點共享的。

3. 衝突偵測 (Collision Detection):

   • 儘管有載波偵聽，但由於網路延遲的存在，兩個或多個節點可能在幾乎同時判斷介質空閒並開始傳輸。這會導致傳輸的信號發生疊加，產生衝突 (collision)。
   • 在傳輸過程中，節點會持續監聽介質。如果偵測到傳輸的信號強度異常升高（高於預期），就表示發生了衝突。
   • 一旦偵測到衝突，傳輸的節點會立即停止傳輸，並發送一個「阻塞信號」(jam signal)，以確保網路上的所有節點都意識到衝突的發生。

4. 衝突後的處理 (Backoff Algorithm):

   • 在傳輸衝突後，每個發生衝突的節點都會進入一個隨機等待階段（稱為退避演算法 Backoff Algorithm），然後重新嘗試傳送。