108 年 國立成功大學數據科學研究所《計算機概論》

本題考查計算機儲存裝置的特性，特別是資料的持久性。

• ROM (Read-Only Memory)：唯讀記憶體，其中儲存的資料在斷電後不會消失，通常用於儲存 BIOS 或韌體等關鍵程式。因此，ROM 屬於永久儲存。
• RAM (Random Access Memory)：隨機存取記憶體，是電腦的主記憶體，用於儲存目前執行中的程式和資料。RAM 是揮發性記憶體，斷電後資料會消失。

本題考查 CPU 內部結構與工作原理的相關敘述。

• S1. Registers in CPU is used to store intermediate data and instructions.
  CPU 中的暫存器 (Registers) 的主要功能是儲存正在處理的資料、指令以及運算的中繼結果。這是暫存器的核心功能之一。因此，S1 是正確的。

• S2. Program counter keeps track of the memory address of the instruction that is to be executed next.
  程式計數器 (Program Counter, PC) 是 CPU 中用來儲存下一條要執行的指令在記憶體中的位址。CPU 執行完當前指令後，會從 PC 中讀取下一個指令的位址來取得指令。因此，S2 是正確的。

• S3. Speed of CPU is also known as clock speed, which is the number of instructions executed by CPU in one second.
  CPU 的時脈速度 (Clock Speed)，通常以赫茲 (Hz) 為單位，表示 CPU 每秒鐘可以進行的週期數。時脈速度是影響 CPU 效能的重要因素，但它不是直接等於每秒執行的指令數 (Instructions Per Second, IPS)。CPU 的實際執行效能還取決於指令集架構、流水線深度、快取記憶體等。

本題考查計算機基本概念，包括二進制表示、變數操作、位元組大小和資料表示。題目要求找出「不正確」的敘述。

• (A) A computer stores all data in binary.
  電腦內部所有的資訊，包括數字、文字、圖片、聲音等，最終都是以二進制 (binary) 的形式儲存和處理的。這是計算機的基礎。因此，此敘述是正確的。

• (B) The statement age = age + 1 increases the value that is in the age variable by 1.
  在大多數程式語言中，age = age + 1 是一個賦值語句。它會先計算 age + 1 的值，然後將這個新的值存回 age 變數中，從而使 age 的值增加 1。這是常見的變數增量操作。因此，此敘述是正確的。

• (C) A byte can hold any number between 0 and 255.
  一個位元組 (byte) 通常由 8 個位元 (bit) 組成。

核心觀念

遞迴函式（recursive function）是指函式在執行過程中直接或間接呼叫自身，以處理可分解成相同型態子問題的問題。

一個正確的遞迴函式通常包含：

• 基底情況（base case）：直接給出答案，負責停止遞迴。
• 遞迴情況（recursive case）：將問題縮小，呼叫自身處理較小的子問題。
• 終止條件：每次遞迴都必須逐步接近基底情況，否則會造成無限遞迴。

遞迴執行時，每一次函式呼叫都會建立一個新的呼叫堆疊框架（call stack frame），其中保存參數、區域變數、返回位置等資訊。因此，遞迴的空間複雜度主要取決於遞迴深度，而不是單純取決於區域變數的數量。

解題方法

本題要求判斷「關於遞迴函式的特徵，哪一項不正確」。

判斷步驟如下：

1. 檢查選項是否符合遞迴函式的基本結構。
2. 檢查選項是否正確描述函式呼叫自身的特性。
3. 檢查選項對遞迴記憶體使用量的解釋是否精確。

選項分析

(A) One or multiple base cases and one or multiple recursive cases.

此敘述正確。

遞迴函式可以有一個或多個基底情況，也可以有一個或多個遞迴情況。例如，階乘函式可寫成：

$$n! = \begin{cases} 1, & n=0\\ n(n-1)!, & n>0 \end{cases}$$

其中 $n=0$ 是基底情況，$n>0$ 是遞迴情況。

某些問題具有多個基底情況，例如費氏數列：

$$F(n)= \begin{cases} 0, & n=0\\ 1, & n=1\\ F(n-1)+F(n-2), & n\ge 2 \end{cases}$$

因此，遞迴函式可包含一個或多個基底情況，以及一個或多個遞迴情況。

(B) The function calling itself at some point.

此敘述正確。

遞迴的核心定義就是函式在執行過程中呼叫自身。例如：

factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

在此程式中，factorial 呼叫了自身，因此形成遞迴。

本題考查非對稱加密（公鑰加密）的基本原理。非對稱加密系統使用一對金鑰：公鑰 (public key) 和私鑰 (private key，也稱為秘密金鑰 secret key)。這兩個金鑰是數學上相關聯的，但私鑰是保密的，公鑰可以公開。

非對稱加密有兩種主要用途：

1. 機密性 (Confidentiality)：確保只有預期的接收者能夠讀取訊息。
2. 身份驗證 (Authentication) 和不可否認性 (Non-repudiation)：證明訊息的來源，並確保發送者無法否認發送了該訊息。

其基本規則是：用一把金鑰加密的訊息，必須用另一把配對的金鑰來解密。

• 加密訊息以確保機密性：
  如果 Alice 想發送一個機密訊息給 Bob，Alice 會使用 Bob 的公鑰來加密訊息。Bob 收到加密訊息後，只能使用他自己的私鑰來解密，從而讀取訊息。這樣，即使其他人截獲了訊息，也無法解密，因為只有 Bob 擁有對應的私鑰。
  對應的敘述是：「A message encrypted by the public key can only be decrypted by the secret key.」 (公鑰加密的訊息，只能用私鑰解密)。

本題考查網際網路中常見的網路服務及其所使用的傳輸層協定。TCP (Transmission Control Protocol) 是傳輸控制協定，提供可靠的、面向連接的服務。UDP (User Datagram Protocol) 則提供不可靠的、無連接的服務。

我們逐一分析各選項：

• (A) World Wide Web (WWW)：全球資訊網，主要使用 HTTP (Hypertext Transfer Protocol) 或 HTTPS 協定。HTTP/HTTPS 是建立在 TCP 之上的，提供可靠的網頁傳輸。因此，WWW 使用 TCP。

• (B) FTP software：檔案傳輸協定 (File Transfer Protocol)。

核心觀念

本題考查線性搜尋（linear search）與二元搜尋（binary search）的適用條件及時間複雜度。

• 線性搜尋依序比較資料，時間複雜度為：

  $O(n)$

• 二元搜尋每次將搜尋範圍縮小為原來的一半，時間複雜度為：

  $O(\log n)$

二元搜尋的必要條件是：資料必須已經排序。因此，只有在資料「已排序」時，才能直接使用二元搜尋與線性搜尋比較效率。

當資料量 $n$ 很大時，$O(n)$ 與 $O(\log n)$ 的差距會非常明顯；資料量很小时，兩者的實際差距通常較小。

解題方法

判斷本題可分成兩個步驟：

1. 確認資料是否已排序，因為二元搜尋只能用於已排序資料。
2. 在可使用二元搜尋的情況下，判斷資料量是否很大，因為資料量越大，二元搜尋相對於線性搜尋的優勢越明顯。

因此，最符合「線性搜尋相較於二元搜尋非常沒效率」的條件是：

• 資料已排序；
• 資料量很大。

這正是「Large and sorted arrays」。

選項分析

(A) Small and sorted arrays

資料已排序，因此可以使用二元搜尋。雖然二元搜尋的理論複雜度較低，但資料量很小時，線性搜尋最多只需檢查少量元素，實際差距通常不大。

因此，此選項不是最適合的答案。

(B) Small and unsorted arrays

核心觀念

二元樹三種走訪定義如下：

• Preorder（前序）：根 → 左子樹 → 右子樹
• Inorder（中序）：左子樹 → 根 → 右子樹
• Postorder（後序）：左子樹 → 右子樹 → 根

由圖可知：$A$ 為根，左子樹以 $B$ 為根、右子樹以 $C$ 為根；$D$ 的子節點為 $H$，$G$ 的左右子節點分別為 $I、J$。

解題方法

依照走訪規則逐一列出：

1. 前序：

$$A \rightarrow B \rightarrow D \rightarrow H \rightarrow E \rightarrow C \rightarrow F \rightarrow G \rightarrow I \rightarrow J$$

因此為 ABDHECFGIJ。

2. 後序：

左子樹 $B$ 的後序為：

$$H \rightarrow D \rightarrow E \rightarrow B$$

右子樹 $C$ 的後序為：

$$F \rightarrow I \rightarrow J \rightarrow G \rightarrow C$$

最後才訪問根節點 $A$，所以完整後序為：

核心觀念

本題考查三個資料結構與圖論觀念：

1. Binary Search Tree（BST）的高度

   • 高度取決於樹的形狀。
   • 平衡 BST 高度為 $\Theta(\log n)$。
   • 最差情況可能退化成鏈狀，高度為 $\Theta(n)$。

2. Minimum Spanning Tree（MST）與最短路徑

   • MST 的目標是讓所有頂點連通，且所有選用邊的總權重最小。
   • MST 不保證任兩點間的路徑距離最短。
   • 最短路徑問題與 MST 是不同的最佳化問題。

3. Breadth-First Search（BFS）的時間複雜度

   • BFS 會按照距離根節點的層次逐層探索。
   • 一般圖的 BFS 複雜度為 $O(V+E)$。
   • 在含有 $n$ 個節點的樹中，BFS 最差可能造訪全部 $n$ 個節點，因此為 $O(n)$。

解題方法

逐一檢查選項敘述是否符合上述定義與複雜度，再判斷「All of above are incorrect」是否成立。

選項分析

(A) Every binary search tree with $n$ nodes has height $O(\log n)$

此敘述錯誤。

BST 只要求：

• 左子樹所有鍵值小於根節點；
• 右子樹所有鍵值大於根節點。

BST 不一定平衡。若依序插入 $1,2,3,\ldots,n$，會形成退化的右斜樹：

$$1 \rightarrow 2 \rightarrow 3 \rightarrow \cdots \rightarrow n$$

此時樹高為：

$$h=n-1=\Theta(n)$$

因此，只有在 BST 維持平衡時，樹高才是 $O(\log n)$；一般 BST 的最差高度為 $\Theta(n)$。

(B) Let $T$ be a minimum spanning tree of graph $G$. Then, for any pair of nodes $s$ and $t$, the shortest path from $s$ to $t$ in $G$ is the path from $s$ to $t$ in $T$.

此敘述錯誤。

本題考查資料庫系統的基本概念，包括 DBMS 的功能、候選鍵、外鍵和主鍵的定義。題目要求找出「正確」的敘述。

• S1. Database management system (DBMS) is a software used for management, maintenance and retrieval of data stored in a database.
  這是對 DBMS 功能的標準定義。DBMS 是一種軟體，用於建立、維護、管理和存取資料庫中的資料。它提供了資料的儲存、查詢、更新、安全性、並行控制等功能。因此，S1 是正確的。

• S2. Candidate key is a set of one or more attributes that uniquely identifies tuple within a relation.
  候選鍵 (Candidate Key) 是指能夠唯一識別關係（表格）中每個元組（行）的屬性（欄位）的集合。每個候選鍵都滿足唯一性約束。主鍵 (Primary Key) 是從候選鍵中選出的一個。因此，S2 是正確的。

• S3. Foreign key is a non-key attribute, whose values are derived from the primary key of some other
  table is known as foreign key.
  外鍵 (Foreign Key) 是指一個關係中的一個或多個屬性，其值必須是另一個關係（通常是本身）的主鍵或其他候選鍵中的值。

Quick Sort 演算法

Quick Sort 是一種基於分治法 (Divide and Conquer) 的排序演算法。它的基本思想是：

1. 分治 (Divide)：選擇一個基準元素 (pivot)，將數列分割成兩個子數列：一個包含所有小於或等於 pivot 的元素，另一個包含所有大於 pivot 的元素。這個分割過程稱為「partitioning」。
2. 遞迴 (Conquer)：遞迴地對兩個子數列進行 Quick Sort。
3. 合併 (Combine)：由於分割過程已經將元素放在了正確的位置，所以不需要額外的合併步驟。

演算法步驟：

1. 選擇基準元素 (Pivot Selection)：
   從數列中選擇一個元素作為基準。常見的選擇策略有：

   • 選擇第一個元素。
   • 選擇最後一個元素。
   • 選擇中間的元素。
   • 隨機選擇一個元素。
   • 三數取中法 (median-of-three)：選擇第一個、中間和最後一個元素的 median 作為 pivot。

2. 分割 (Partitioning)：
   這個步驟是 Quick Sort 的核心。目標是重新排列數列，使得所有小於或等於 pivot 的元素都位於 pivot 的左邊，所有大於 pivot 的元素都位於 pivot 的右邊。分割完成後，pivot 就處於它最終排序後的位置。
   常見的分割方法有 Lomuto partition scheme 和 Hoare partition scheme。這裡以 Lomuto partition scheme 為例：

   • 將 pivot 移到數列的最後（如果 pivot 不是最後一個元素）。
   • 初始化一個指標 i，指向數列開頭的前一個位置（例如，i = low - 1）。
   • 遍歷數列從 low 到 high-1 的元素（j 指標）。
   • 如果 array[j] 小於或等於 pivot，則將 i 加一，然後交換 array[i] 和 array[j]。
   • 遍歷結束後，將 pivot（原先放在最後的元素）與 array[i+1] 交換。此時 array[i+1] 就是 pivot，並且它處於最終排序的位置。
   • 返回 i+1 作為 pivot 的最終索引。

3. 遞迴排序 (Recursive Sorting)：
   對分割後左邊的子數列（索引從 low 到 pivot_index - 1）遞迴呼叫 Quick Sort。
   對分割後右邊的子數列（索引從 pivot_index + 1 到 high）遞迴呼叫 Quick Sort。

範例說明：

假設我們要排序的數列是：[7, 2, 1, 6, 8, 5, 3, 4]

1. 第一次呼叫 QuickSort([7, 2, 1, 6, 8, 5, 3, 4], low=0, high=7)
   • 選擇 Pivot：我們選擇最後一個元素 4 作為 pivot。
   • Partitioning (Lomuto scheme, pivot=4)：
     • 數列：[7, 2, 1, 6, 8, 5, 3, 4] (pivot 在最後)
     • i = -1
     • j=0, array[0]=7 > 4。
     • j=1, array[1]=2 <= 4。 i 變為 0。交換 array[0] 和 array[1]。數列：[2, 7, 1, 6, 8, 5, 3, 4]。
     • j=2, array[2]=1 <= 4。 i 變為 1。交換 array[1] 和 array[2]。數列：[2, 1, 7, 6, 8, 5, 3, 4]。
     • j=3, array[3]=6 > 4。
     • j=4, array[4]=8 > 4。
     • j=5, array[5]=5 > 4。
     • j=6, array[6]=3 <= 4。 i 變為 2。交換 array[2] 和 array[6]。數列：[2, 1, 3, 6, 8, 5, 7, 4]。
     • 遍歷結束。i = 2。
     • 將 pivot 4 (在 array[7]) 與 array[i+1] (即 array[3]=6) 交換。
     • 數列變為：[2, 1, 3, 4, 8, 5, 7, 6]。
     • pivot 4 的最終位置是索引 3。

作業系統相關問題詳解

(1) 飢餓 (Starvation) 與死鎖 (Deadlock) 的區別

• 死鎖 (Deadlock)：

  • 定義：當兩個或多個進程（或執行緒）互相等待對方釋放資源，而同時又持有對方所需的資源時，就會發生死鎖。這些進程將永遠等待下去，無法繼續執行。
  • 產生條件 (Coffman conditions)：通常需要同時滿足以下四個條件：
    1. 互斥 (Mutual Exclusion)：資源不能被共享，一次只能被一個進程使用。
    2. 持有並等待 (Hold and Wait)：一個進程至少持有一個資源，並且正在等待另一個進程持有的資源。
    3. 非搶佔 (No Preemption)：資源不能被強制從持有者手中搶奪，只能由持有者主動釋放。
    4. 循環等待 (Circular Wait)：存在一個進程鏈 $P_0, P_1, ..., P_n$，其中 $P_0$ 等待 $P_1$ 持有的資源，$P_1$ 等待 $P_2$ 持有的資源，...，$P_n$ 等待 $P_0$ 持有的資源。
  • 特徵：進程之間形成循環依賴，導致所有相關進程都無法推進。

• 飢餓 (Starvation)：

  • 定義：在一個資源分配系統中，一個或多個進程由於某些策略（例如，優先權調度）或資源爭用，而長時間無法獲得所需的資源，即使資源可用，也無法被調度執行。
  • 產生原因：常見於優先權調度的系統中，低優先權的進程可能永遠無法獲得 CPU 時間，因為總是有高優先權的進程在運行。也可能因為資源分配策略（如死鎖預防或避免措施）導致某些進程被長期排除。
  • 特徵：進程可能一直處於等待狀態，但與死鎖不同的是，飢餓的進程並非與其他進程形成循環等待，而是因為某些調度或資源分配的「不公平」而無法獲得資源。理論上，如果所有高優先權進程都執行完畢，低優先權進程就有機會獲得資源，但實際情況可能因為系統的持續負載而使其長時間得不到執行。

• 主要區別：

  • 死鎖是進程之間互相等待，形成循環依賴，所有被捲入的進程都無法推進。
  • 飢餓是進程因資源分配策略或資源爭用，長時間無法獲得資源，但並非與其他進程形成直接的循環等待。飢餓進程可能一直處於等待狀態，而死鎖進程則處於一種「卡住」的狀態。
  • 死鎖通常是可以被檢測和解除的（例如，通過資源分配圖），而飢餓則可能難以完全避免，尤其是在基於優先權的系統中。

【答案】死鎖是進程間互相等待資源形成的循環依賴，導致所有相關進程停止；飢餓是進程因資源分配策略等原因長期無法獲得資源，處於持續等待狀態。

(2) 進程 (Process) 與執行緒 (Thread) 的區別

進程和執行緒都是作業系統中執行的單元，但它們在資源擁有權、獨立性和通信方式上有所不同。

特徵	進程 (Process)	執行緒 (Thread)
定義	一個獨立運行的程式實例，擁有自己的記憶體空間和資源。	進程內的一個執行路徑，與同一進程內的其他執行緒共享記憶體空間。
資源擁有權	每個進程擁有獨立的記憶體空間（代碼、數據、堆疊、堆）。	同一進程內的執行緒共享該進程的代碼、數據、堆和部分系統資源。每個執行緒有自己的程式計數器、暫存器和堆疊。
獨立性	進程之間是獨立的，一個進程的崩潰不會影響其他進程。	同一進程內的執行緒不獨立，一個執行緒的崩潰可能導致整個進程崩潰。
創建開銷	創建進程的開銷較大（需要分配資源、建立 PCB 等）。	創建執行緒的開銷較小（只需要分配堆疊和暫存器狀態）。

人工智慧與資料科學相關問題詳解

(1) 圖靈測試 (Turing Test)

• 提出者：由英國數學家艾倫·圖靈 (Alan Turing) 在 1950 年提出。
• 目的：圖靈測試是一個用於評估機器是否能表現出與人類無法區分的智能行為的標準。它試圖回答一個問題：「機器能否思考？」。
• 測試方法：
  1. 測試包含三方：一個測試者 (human interrogator)、一個人類被試者 (human respondent) 和一個機器被試者 (machine respondent)。
  2. 測試者透過文字訊息（例如，鍵盤輸入和螢幕顯示）與人類被試者和機器被試者進行對話。測試者無法知道哪個是被試者是人類，哪個是機器。
  3. 測試者的任務是透過提問，分辨出哪個是被試者是人類，哪個是機器。
  4. 如果測試者無法可靠地區分出機器和人類，那麼這台機器就被認為通過了圖靈測試，表現出了與人類相當的智能。
• 意義：圖靈測試提供了一個操作性的定義來衡量機器智能，儘管它主要關注的是行為（能否模仿人類對話），而不是機器的內部工作原理。它推動了早期人工智慧的研究。
• 局限性：圖靈測試並非完美，它可能被認為過於關注語言能力，而忽略了其他形式的智能（如視覺、運動、創造力）。此外，一個機器也可能透過欺騙或預設的回答來通過測試，而不真正具備思考能力。

【答案】圖靈測試是一種評估機器是否能表現出與人類無法區分的智能行為的測試，由測試者透過文字對話來判斷被試者是人還是機器。

(2) 邏輯迴歸 (Logistic Regression)

• 定義：邏輯迴歸是一種用於二元分類 (binary classification) 問題的監督式機器學習演算法。儘管名稱中包含「迴歸」，但它實際上是用於分類任務。
• 基本思想：
  1. 它使用一個邏輯函數 (logistic function)，也稱為Sigmoid 函數，將線性模型的輸出映射到一個介於 0 和 1 之間的概率值。
  2. 這個概率值代表樣本屬於某個類別（通常是正類，表示為 1）的可能性。
• 模型：
  假設我們有一個輸入特徵向量 $x = [x_1, x_2, ..., x_n]$。邏輯迴歸模型首先計算一個線性組合：
  $z = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ... + \beta_n x_n$
  其中 $\beta_0, \beta_1, ..., \beta_n$ 是模型的參數（權重）。
  然後，將 $z$ 輸入 Sigmoid 函數 $\sigma(z)$:
  $P(Y=1|x) = \sigma(z) = \frac{1}{1 + e^{-z}} = \frac{1}{1 + e^{-(\beta_0 + \sum_{i=1}^n \beta_i x_i)}}$
  這個 $P(Y=1|x)$ 就是樣本 $x$ 屬於類別 1 的概率。樣本屬於類別 0 的概率則是 $P(Y=0|x) = 1 - P(Y=1|x)$。
• 決策邊界：通常，當 $P(Y=1|x) \ge 0.5$ 時，將樣本分類為類別 1；否則分類為類別 0。這個閾值 0.5 對應於 $z=0$，即 $\beta_0 + \sum \beta_i x_i = 0$，這是一個線性決策邊界。

此題提供了一個 SQL 的 CREATE TABLE 語句，定義了一個名為 G 的表格，用於儲存學生的成績資訊。

表格 G 的結構如下：

• sid (INT)：學生的 ID，用作主鍵的一部分。
• class (CHAR(20))：課程名稱。
• grade (INT)：學生成績分數，範圍在 0 到 100 之間。
• PRIMARY KEY (sid, dept)：定義了表格的主鍵。主鍵由 sid 和 dept 兩個屬性組成。

然而，這個 CREATE TABLE 語句存在一個明顯的矛盾和錯誤：

1. dept 屬性未定義：在 CREATE TABLE G (...) 的定義中，列出了 sid, class, grade 三個屬性。但在 PRIMARY KEY (sid, dept) 中，卻引用了一個名為 dept 的屬性，但 dept 這個屬性並沒有在表格的欄位定義中出現。這將導致 SQL 語句執行失敗，因為 dept 這個欄位不存在。
2. dept 屬性應該是 class 嗎？：從中文註解來看，class 對應「class name」。而 sid 是「ID of student」。grade 是「grade score」。
   如果主鍵是 (sid, dept)，那麼 dept 應該是代表某種課程或班級的識別碼。
   如果 dept 實際上是指 class，那麼主鍵應該是 (sid, class)。
   如果 dept 是指「學系」(Department)，那麼表格 G 應該還包含一個 dept 欄位。

假設 dept 應該是 class，那麼表格定義變為：

CREATE TABLE G (
    sid INT,
    class CHAR(20),
    grade INT,
    PRIMARY KEY (sid, class)
);

這樣，sid 和 class 的組合就能唯一識別一個學生的某門課的成績。

假設 dept 是一個獨立的欄位，那麼表格定義應該是：

CREATE TABLE G (
    sid INT,
    class CHAR(20),
    dept VARCHAR(50), -- 假設學系名稱
    grade INT,
    PRIMARY KEY (sid, dept) -- 或者 PRIMARY KEY (sid, class, dept) 取決於業務邏輯
);

但題目給出的 SQL 語句是確定的，我們只能根據原語句來討論。

本題主要考查兩大部分：表達式的二元樹表示法，以及中序表達式轉換為後序表達式。這兩者都與表達式的結構和求值順序有關，是計算機科學中處理表達式的基礎概念。

(1) (3%) Draw a Binary Tree for the expression: $A * B – (C + D) * (P / Q)$

解題過程：

我們要為表達式 $A * B – (C + D) * (P / Q)$ 繪製一個二元樹。二元樹的葉節點通常代表運算元（變數或常數），而內部節點則代表運算子。樹的結構反映了運算式的運算順序，優先級較高的運算或括號內的運算會位於較低的層級。

1. 找出最高優先級的運算子： 在表達式 $A * B – (C + D) * (P / Q)$ 中，括號內的運算 (C + D) 和 (P / Q) 具有最高的優先級。
2. 處理括號內的運算：
   • (C + D)：運算子是 +，運算元是 C 和 D。在樹中，+ 會是父節點，C 和 D 分別是其左右子節點。
   • (P / Q)：運算子是 /，運算元是 P 和 Q。在樹中，/ 會是父節點，P 和 Q 分別是其左右子節點。
3. 處理乘法運算： 表達式可以看作是 (A * B) – ((C + D) * (P / Q))。
   • A * B：運算子是 *，運算元是 A 和 B。在樹中，* 會是父節點，A 和 B 分別是其左右子節點。
   • (C + D) * (P / Q)：這個部分的運算子是 *，它的左子運算式是 (C + D) 的結果，右子運算式是 (P / Q) 的結果。在樹中，這個 * 會是父節點，其左子樹是代表 (C + D) 的樹，右子樹是代表 (P / Q) 的樹。
4. 處理減法運算： 最後是減法運算 –。它的左子運算式是 A * B 的結果，右子運算式是 (C + D) * (P / Q) 的結果。
   • 在樹中，- 會是根節點。
   • - 的左子樹是代表 A * B 的二元樹。
   • - 的右子樹是代表 (C + D) * (P / Q) 的二元樹，其中 * 是這個子樹的根節點。

綜合以上步驟，我們可以繪製出二元樹。

• 根節點是 -。
• - 的左子節點是 * (代表 $A * B$)。
  • 這個 * 的左子節點是 A。
  • 這個 * 的右子節點是 B。
• - 的右子節點是 * (代表 $(C + D) * (P / Q)$)。
  • 這個 * 的左子節點是 + (代表 $C + D$)。
    • 這個 + 的左子節點是 C。
    • 這個 + 的右子節點是 D。
  • 這個 * 的右子節點是 / (代表 $P / Q$)。
    • 這個 / 的左子節點是 P。
    • 這個 / 的右子節點是 Q。

繪製二元樹：

      -
     / \
    *   *
   / \ / \
  A  B +  /
      / \ / \
     C  D P  Q

【答案】

      -
     / \
    *   *
   / \ / \
  A  B +  /
      / \ / \
     C  D P  Q

(2) (3%) Translate infix expression, $A * (B + D) / E – F * (G + H / K)$, into its equivalent postfix expression.

解題過程：

我們將使用「堆疊（stack）」的方法來將中序表達式轉換為後序表達式。後序表達式（也稱為逆波蘭表示法）的特點是運算子緊跟在其運算元之後，不需要括號來界定運算順序。

轉換規則如下：

1. 遍歷中序表達式的每個符號。
2. 如果符號是運算元（變數或常數），則直接輸出到後序表達式。
3. 如果符號是左括號 (，則將其壓入堆疊。
4. 如果符號是右括號 )，則將堆疊中的運算子依序彈出並輸出，直到遇到左括號為止。然後將左括號從堆疊中彈出但不輸出。
5. 如果符號是運算子：
   • 檢查堆疊頂端的運算子。
   • 如果堆疊為空，或者堆疊頂端的運算子是左括號，則將當前運算子壓入堆疊。
   • 否則，如果當前運算子的優先級 高於或等於 堆疊頂端的運算子，則將當前運算子壓入堆疊。
   • 否則（即當前運算子的優先級 低於 堆疊頂端的運算子），則將堆疊頂端的運算子彈出並輸出，然後重複此步驟，直到滿足上述條件之一（堆疊為空、堆疊頂端是左括號、或當前運算子優先級高於或等於堆疊頂端運算子），最後再將當前運算子壓入堆疊。

運算子優先級定義：

• +, -：優先級較低
• *, /：優先級較高

表達式： $A * (B + D) / E – F * (G + H / K)$

我們將使用一個堆疊 S 和一個後序表達式結果字串 Output。

掃描符號	動作	S (堆疊)	Output
A	運算元，輸出。	[]	A
*	運算子。堆疊為空，壓入。	[*]	A
(	左括號，壓入。	[*, (]	A
B	運算元，輸出。	[*, (]	A B
+	運算子。堆疊頂端是 (，壓入。	[*, (, +]	A B
D	運算元，輸出。	[*, (, +]	A B D
)	右括號。彈出並輸出堆疊頂端的運算子 +，直到遇到 (。	[*]	A B D +
/	運算子。堆疊頂端是 *。/ 的優先級等於 *，故彈出 * 並輸出。然後將 / 壓入。	[/]	A B D + *
E	運算元，輸出。	[/]	A B D + * E
–	運算子。堆疊頂端是 /。– 的優先級低於 /，彈出 / 並輸出。堆疊頂端現在是空（因為 / 之後的 ( 已經被處理了，但是我們前面有個 * 沒彈出來），所以將 – 壓入。 (修正：前面掃描到 / 時，堆疊是 [*, (, +]，遇到 ) 後，堆疊變成 [*]。然後掃描 /，/ 優先級等於 *，彈出 *，輸出 A B D + *，堆疊變成 []。現在將 / 壓入堆疊。)

*   **重新梳理：**
    *   `A` -> Output: `A`
    *   `*` -> S: `[*]`
    *   `(` -> S: `[*, (]`
    *   `B` -> Output: `A B`
    *   `+` -> S: `[*, (, +]`
    *   `D` -> Output: `A B D`
    *   `)` -> 彈出 `+`，Output: `A B D +`。S: `[*, (]` -> 彈出 `(`。S: `[*]`
    *   `/` -> `/` 優先級等於 `*`。彈出 `*`，Output: `A B D + *`。S: `[]`。將 `/` 壓入。S: `[/]`
    *   `E` -> Output: `A B D + * E`
    *   `–` -> `–` 優先級低於 `/`。彈出 `/`，Output: `A B D + * E /`。S: `[]`。將 `–` 壓入。S: `[–]`

| F | 運算元，輸出。 | [–] | A B D + * E / F |
| * | 運算子。堆疊頂端是 –。* 的優先級高於 –，壓入。 | [–, *] | A B D + * E / F |
| ( | 左括號，壓入。 | [–, *, (] | A B D + * E / F |
| G | 運算元，輸出。 | [–, *, (] | A B D + * E / F G |
| + | 運算子。堆疊頂端是 (，壓入。 | [–, *, (, +] | A B D + * E / F G |
| H | 運算元，輸出。 | [–, *, (, +] | A B D + * E / F G H |
| / | 運算子。堆疊頂端是 +。/ 的優先級高於 +，壓入。 | [–, *, (, +, /] | A B D + * E / F G H |
| K | 運算元，輸出。 | [–, *, (, +, /] | A B D + * E / F G H K |
| ) | 右括號。彈出並輸出堆疊頂端的運算子 /。