113 年 國立臺灣大學生醫電子與資訊學研究所丙組《計算機概論（B）》

此題考驗對 5G 技術基本特性的了解。5G 的主要目標確實是提供更快的速度（extreme broadband）、更高的可靠性（ultra-robust）、更低的延遲（low latency

此題在考察 GPU（Graphics Processing Unit）的特性與應用。GPU 最初是為圖形處理而設計，其架構擅長大規模並行計算，這使得它在遊戲、影音編輯等領域非常重要。

此題考查對 JPEG 影像壓縮格式的理解。JPEG（Joint Photographic Experts Group）是一種廣泛使用的圖像壓縮標準，但它是一種有損壓縮（lossy compression）方法，旨在以犧

此題在檢查對 OSI（Open Systems Interconnection）七層模型順序的記憶。OSI 模型從最低層（最接近硬體）到最高層（最接近使用者）的正確順序是：

1. Physical Layer (實體層)
2. Data Link Layer (資料鏈結層)
3. Network Layer (網路層)
4. Transport Layer (傳輸層)
5. Session Layer (交談層)

此題在考察人工智能（AI）、機器學習（ML）和深度學習（DL）之間的包含關係。
人工智慧（AI）是一個廣泛的領域，目標是創建能夠執行通常需要人類智能的任務的系統。
機器學習（ML）是 AI 的一個子集，專注於開發能夠從數據中學習並改進其性能的演算法，而無需明確編程。
深度學習（DL）是機器學習的一個子集，它利用深度神經網路（具有多個層）來學習數據的表示。

此題考查布林代數化簡。我們需要化簡給定的布林表達式 $CD1+D(CAA+BB)$。
首先，我們利用布林代數的基本性質：

1. $X \cdot 1 = X$ (恆等律)
2. $X+X = X$ (冪等律)
3. $X \cdot X = X$ (冪等律)
4. $X+0 = X$ (零律)
5. $X \cdot 0 = 0$ (零律)
6. $X+1 = 1$ (吸收律)
7. $X \cdot 1 = X$ (吸收律)
8. $X+X' = 1$ (補碼律)
9. $X \cdot X' = 0$ (補碼律)
10. $X+(X \cdot Y) = X$ (吸收律)
11. $X \cdot (X+Y) = X$ (吸收律)
12. $(X+Y)' = X' \cdot Y'$ (德摩根定律)
13. $(X \cdot Y)' = X' + Y'$ (德摩根定律)
14. $X+Y = Y+X$ (交換律)
15. $X \cdot Y = Y \cdot X$ (交換律)
16. $X+(Y+Z) = (X+Y)+Z$ (結合律)
17. $X \cdot (Y \cdot Z) = (X \cdot Y) \cdot Z$ (結合律)
18. $X \cdot (Y+Z) = X \cdot Y + X \cdot Z$ (分配律)
19. $X+(Y \cdot Z) = (X+Y) \cdot (X+Z)$ (分配律)

核心觀念

Huffman coding 是一種依照字元出現頻率建立「最佳前綴碼」的方法：

1. 每次選出頻率最低的兩個節點合併。
2. 重複合併，直到形成一棵二元樹。
3. 字元的 Huffman code 長度，就是該字元在樹中的深度。
4. 傳送總位元數為：

頻率越高的字元通常會分配到越短的編碼。

解題方法

字元頻率如下：

依照 Huffman 演算法，依序合併最低頻率的節點：

此時剩下的頻率為 $2,3,4$，再合併：

最後合併：

因此樹的結構可表示為：

• $s$ 位於根節點的一側，碼長為 $1$。
• $e$ 位於頻率 $5$ 的節點下，碼長為 $2$。
• $c$ 與 $u$ 位於更深層，碼長皆為 $3$。

一組可能的 Huffman code 為：

此題考查對堆疊（Stack）操作的理解以及 C++ 程式碼的執行流程。我們需要逐步跟蹤程式碼的執行，並記錄變數 x 和 y 的值以及堆疊的狀態。

程式碼逐行分析：

1. stackType<int> stack;：宣告一個名為 stack 的整數型別堆疊。
2. int x, y;：宣告整數變數 x 和 y。
3. x = 5;：x 被賦值為 5。
4. y = 3;：y 被賦值為 3。
5. stack.push(4);：將 4 壓入堆疊。堆疊：[4]
6. stack.push(x);：將 x (即 5) 壓入堆疊。堆疊：[4, 5]
7. stack.push(x + 1);：將 x+1 (即 5+1=6) 壓入堆疊。堆疊：[4, 5, 6]
8. y = stack.top();：stack.top() 返回堆疊頂端的元素（即 6），並將其賦值給 y。

核心觀念

本題考查作業系統中的「死結」（deadlock）及其必要條件。

死結是指一組程序彼此等待對方所持有的資源，導致所有程序都無法繼續執行。根據 Coffman 條件，死結成立必須同時具備以下四項必要條件：

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

可表示為：

其中 $P_i \rightarrow P_j$ 表示程序 $P_i$ 正在等待程序 $P_j$ 所持有的資源。

這四項條件必須同時存在，缺少任一項便不會形成典型死結。

解題方法

直接套用死結的四個必要條件：

• 資源必須具有互斥性；
• 程序必須在持有資源的同時等待其他資源；
• 已分配的資源不能被強制搶回；
• 程序間必須形成循環等待。

題目選項 A 至 D 分別對應這四項條件。D 選項使用 Circular set，在此題語意中應理解為程序或資源形成循環等待集合，即標準術語 circular wait。

因此四項條件全部包含，答案為 E。

選項分析

(A) Mutual exclusion

此題考查十進制數轉換為二進制數。我們需要將十進制數 32 轉換為二進制表示。

轉換方法：
重複除以 2，直到商為 0，記錄每次的餘數，然後將餘數倒序排列。

1. $32 \div 2 = 16$ 餘 $0$
2. $16 \div 2 = 8$ 餘 $0$
3. $8 \div 2 = 4$ 餘 $0$
4. $4 \div 2 = 2$ 餘 $0$
5. $2 \div 2 = 1$ 餘 $0$
6. $1 \div 2 = 0$ 餘 $1$

將餘數倒序排列：$100000$。
所以，十進制數 32 的二進制表示是 $100000_2$。

核心觀念

Fibonacci 數列的定義為：每一項等於前兩項之和。常見初始條件是

因此其遞迴公式為

題目雖標示 $n\geq 1$，但遞迴式本身需要使用 $F(n-2)$，所以實際套用範圍應從 $n\geq 2$ 開始。

解題方法

觀察 Fibonacci 數列：

例如：

可見第 $n$ 項由前一項 $F(n-1)$ 與前兩項 $F(n-2)$ 相加得到，因此正確遞迴公式是

選項分析

(A) $F(n)=F(n+1)+F(n+2)$

錯誤。右側使用的是第 $n$ 項之後的兩項，方向與 Fibonacci 遞迴定義相反。以 $n=1$ 檢查：

核心觀念

本題考查最小成本生成樹（Minimum Cost Spanning Tree, MST）。

生成樹必須：

• 連接圖中的所有頂點；
• 恰好選取 $V-1$ 條邊；
• 不形成 cycle；
• 所有可能的生成樹中，總邊權重最小。

可使用 Kruskal 演算法：將邊依權重由小到大排列，依序選取不會形成環的邊。

解題方法

圖中共有 $5$ 個頂點，因此生成樹必須選取：

依邊權重排序：

依序選邊：

1. 選權重 $1$：連接上方頂點與左上頂點。
2. 選權重 $2$：連接左下頂點與右下頂點。
3. 選權重 $3$：連接左上頂點與右下頂點。
4. 選權重 $4$ 會與既有邊形成 cycle，因此跳過。

核心觀念

本題考查二元樹的後序走訪（postorder traversal）。

後序走訪順序為：

解題方法

依圖可讀出二元樹結構：

• 根節點為 $0$
• $0$ 的左子樹根為 $1$，右子樹根為 $2$
• $1$ 的左子樹為 $3$、右子樹為 $4$
• $3$ 的左子節點為 $6$、右子節點為 $7$
• $2$ 的右子樹根為 $5$
• $5$ 的左子節點為 $8$、右子節點為 $9$

依照「左、右、根」順序：

1. 節點 $1$ 的子樹：

   • $3$ 的後序為 $6,7,3$
   • 再訪問 $4$
   • 最後訪問 $1$

   得到：

   $67341$

2. 節點 $2$ 的子樹：

   • $5$ 的後序為 $8,9,5$
   • 最後訪問 $2$

   得到：

   $8952$

核心觀念

本題考查二元樹的中序走訪（inorder traversal），規則為：

必須對每個子樹遞迴套用相同順序。

解題方法

依圖中的二元樹：

• 根節點為 $0$
• $0$ 的左子樹以 $1$ 為根，右子樹以 $2$ 為根
• $1$ 的左、右子樹分別為 $3$、$4$
• $3$ 的左、右子樹分別為 $6$、$7$
• $2$ 的右子樹為 $5$，而 $5$ 的左、右子樹分別為 $8$、$9$

左子樹 $1$ 的中序走訪：

根節點 $0$ 接在左子樹之後：