115 年 國立中正大學資訊管理學系碩士班乙組《計算機概論》

此題考查二進位表示法與整數減法。首先計算十進位數字的減法，然後將結果轉換為二進位。

計算 37 - 12：
$37 - 12 = 25$

此題考查十進位帶小數的數字轉換為二進位表示法。轉換時，整數部分與小數部分需要分開處理。

整數部分 (51) 的轉換：
$51 \div 2 = 25$ 餘 1
$25 \div 2 = 12$ 餘 1
$12 \div 2 = 6$ 餘 0
$6 \div 2 = 3$ 餘 0
$3 \div 2 = 1$ 餘 1
$1 \div 2 = 0$ 餘 1
將餘數由下往上排列，得到整數部分的二進位表示為 110011。

此題考查計算機儲存裝置的存取速度。一般而言，儲存裝置的速度層級從快到慢大致為：暫存器 (Register) > 快取記憶體 (Cache) > 主記憶體 (Main Memory) > 硬碟 (Hard Disk)。

• 暫存器 (Register): 位於 CPU 內部，速度最快，用於存放 CPU 正在處理的資料和指令。

此題考查指令的分類，特別是控制指令。指令通常可以分為以下幾類：

• 資料傳輸指令 (Data Transfer Instructions): 如 LOAD, STORE, MOVE，用於在記憶體、暫存器和 CPU 之間傳輸資料。
• 算術邏輯指令 (Arithmetic/Logic Instructions): 如 ADD, SUB, AND, OR，用於執行算術和邏輯運算。

此題考查作業系統中的 CPU 排程演算法，特別是先進先出 (First-In-First-Out, FIFO) 或先到先服務 (First-Come, First-Served, FCFS) 的平均等待時間計算。

在 FIFO/FCFS 排程中，進程按照它們到達的順序執行，一旦開始執行，就不會被中斷。

我們需要計算每個進程的等待時間 (Waiting Time) 和周轉時間 (Turnaround Time)。
等待時間 = 開始執行時間 - 到達時間
周轉時間 = 完成時間 - 到達時間
完成時間 = 開始執行時間 + 執行時間

進程到達時間與執行時間：
P1: 到達時間 = 0, 執行時間 = 6
P2: 到達時間 = 1, 執行時間 = 3
P3: 到達時間 = 3, 執行時間 = 4

執行順序 (根據到達時間)： P1, P2, P3

時間軸分析：

• 時間 0: P1 到達，開始執行。
  • P1 開始執行時間 = 0
  • P1 等待時間 = 0 - 0 = 0
• 時間 1: P2 到達，P1 仍在執行。
• 時間 3: P3 到達，P1 仍在執行。
• 時間 6: P1 完成。
  • P1 完成時間 = 0 (開始) + 6 (執行) = 6
  • P1 周轉時間 = 6 - 0 = 6

此題延續上一題，計算平均周轉時間 (Average Turnaround Time)。周轉時間是指一個進程從提交給系統到執行完畢所經過的總時間。

周轉時間 (Turnaround Time) = 完成時間 (Completion Time) - 到達時間 (Arrival Time)

根據上一題的計算結果：
P1：到達時間 = 0, 執行時間 = 6, 開始執行時間 = 0, 完成時間 = 6
P1 周轉時間 = 6 - 0 = 6

此題考查 RAID (Redundant Array of Independent Disks) 技術，特別是哪種 RAID 等級使用了鏡像 (Mirroring) 技術。

• RAID 0 (Striping): 數據被分割成塊，並在多個硬碟之間分散寫入。提供高寫入和讀取速度，但沒有冗餘。
• RAID 1 (Mirroring): 數據被完整地複製到至少兩個硬碟上。提供高數據冗餘和讀取性能，但寫入性能可能受限於最慢的硬碟，且儲存空間利用率最低（通常為 50%）。

此題考查作業系統中死鎖 (Deadlock) 的必要條件。死鎖發生需要同時滿足四個必要條件，這四個條件是：互斥 (Mutual Exclusion)、佔有並等待 (Hold and Wait)、不可剝奪 (No Preemption) 和循環等待 (Circular Wait)。

• 互斥 (Mutual Exclusion): 至少有一個資源是不能被共享的，一次只能被一個進程使用。
• 佔有並等待 (Hold and Wait): 進程至少佔有一個資源，並等待取得其他進程佔有的資源。
• 不可剝奪 (No Preemption): 資源不能被強制剝奪，只能由佔有它的進程主動釋放。

核心觀念

IPv4 的傳統 A、B、C 分級定址中，C 級網路的網路部分占 $24$ 位元，主機部分占 $8$ 位元。主機部分的每種位元組合都對應一個 IP 位址，因此一個 C 級網路共有 $2^8$ 個位址。

解題方法

主機欄位有 $8$ 位元，每一位元可為 $0$ 或 $1$，所以位址總數為：

這是網路中的 IP 位址總數。其中網路位址與廣播位址各保留一個，不能配置給一般主機，因此可用主機位址數為：

題目問的是網路中有多少個 IP 位址，故應計算總數，答案為 256。

選項分析

此題考查網路通訊協定，特別是應用層協定與電子郵件系統的關聯。

網路通訊模型 (如 OSI 模型或 TCP/IP 模型) 的應用層負責提供網路服務給使用者應用程式。電子郵件系統需要多個協定來完成郵件的傳送、接收和管理。

• HTTP (Hypertext Transfer Protocol): 主要用於萬維網 (World Wide Web)，傳輸網頁內容。
• DNS (Domain Name System): 用於將網域名稱轉換為 IP 位址。

此題考查 Wi-Fi 網路中的基本組件，特別是「基地台」的角色。

• Cell tower (基地台 - 行動通訊): 這是行動電話網路中的基站，用於覆蓋行動通訊訊號。
• Router (路由器): 負責連接不同的網路，並根據 IP 位址將數據封包從來源傳送到目的地。在家庭或小型辦公室中，路由器通常也整合了 Wi-Fi 功能，但其核心功能是路由。

此題考查嵌入式系統的作業系統。Raspberry Pi 是一款流行的單板電腦，其設計目標是低成本、高可用性，廣泛用於教育和嵌入式專案。

核心觀念
在演算法與計算複雜度的分析中，「多項式界」(polynomially bounded) 指的是隨著輸入規模 $n$ 增大，其增長速率可以用某個多項式 $\Theta(n^{k})$（$k$ 為非負常數）上界。若一個函數的增長速度超過所有多項式（例如指數函數、階乘函數），則稱它 不是多項式界。
常見的函數比較順序（漸進上界）如下：

$\log n \;\prec\; n^{c} \;\prec\; n^{\log n} \;\prec\; a^{n}\;(a>1) \;\prec\; n! \;\prec\; n^{n}$

其中「$\prec$」表示嚴格更慢的增長。

解題方法
判斷每個選項是否屬於多項式界，只需比較其增長率與一般的多項式形式 $n^{k}$。若能找到常數 $k$ 使得該函數在足夠大的 $n$ 下被 $c\cdot n^{k}$（$c>0$）所界定，即屬於多項式界；否則屬於非多項式界。
具體步驟：

1. 將選項寫成常見函數類型（對數、指數、階乘、多項式等）。
2. 利用已知的漸進比較，直接判斷其相對於多項式的關係。
3. 若不確定，可使用對數或斯特林公式將指數與階乘轉換為較易比較的形式。

選項分析

此題考查二元搜尋 (Binary Search) 的時間複雜度。二元搜尋是一種在已排序的陣列或列表中搜尋目標值的演算法。

二元搜尋的原理是每次將搜尋範圍縮小一半。

1. 檢查中間元素。
2. 如果中間元素就是要找的值，則搜尋成功。
3. 如果目標值比中間元素小，則在左半部繼續搜尋。

此題考查氣泡排序 (Bubble Sort) 的時間複雜度。氣泡排序是一種簡單的排序演算法，它重複地走訪要排序的列表，一次比較兩個元素，如果他們的順序錯誤就交換它們。走訪列表的工作是重複進行直到沒有再需要交換，也就是列表已經排序完成。

氣泡排序的過程是：
外層迴圈：需要進行 $n-1$ 次走訪（或最多 $n$ 次）。
內層迴圈：在每次走訪中，需要比較相鄰的元素，並進行交換。在第一次走訪中，需要進行 $n-1$ 次比較；第二次走訪，需要 $n-2$ 次比較；

此題考查 C++ 程式碼的執行結果，特別是迴圈和條件判斷的應用。

程式碼初始化變數 product 為 1。
然後進入一個 for 迴圈，變數 i 從 1 開始，每次遞增 1，直到 i 大於 7 為止。
在迴圈內部，有一個 if 條件判斷 i % 2 == 1，這表示只有當 i 是奇數時，才會執行 product *= i; 這行程式碼，也就是將 product 的值乘以當前的 i。

我們逐步追蹤 product 的值：

• i = 1: $1 \% 2 == 1$ (True)。product = 1 * 1 = 1。
• i = 2: $2 \% 2 == 0$ (False)。

核心觀念

這題考查 for 迴圈的執行順序、變數作用範圍，以及 break 的使用規則。

在 C++ 中，for 迴圈若沒有大括號，緊接著的單一敘述才是迴圈本體。以 for 初始化區宣告的變數 i，作用範圍也只涵蓋該迴圈。

解題方法

依題目原文，for 迴圈本體只有這一行：

arr[i] = i*i;

迴圈結束後，i 已超出作用範圍，因此後面的 if(i%2==1) 和 if(i==7) 都會因為 i 未宣告而無法編譯。此外，break 位於迴圈外，也不符合 C++ 語法規則。因此，程式照原文無法執行，沒有列印值。

若依選項推定，題目原意是在 for 迴圈中執行賦值、判斷奇偶並於 i == 7 時跳出，則應將這些敘述包在迴圈的大括號內。此時：

• i 從 $0$ 逐次增加。
• 每次先設定 arr[i] = i^2。
• 當 i 為奇數時列印 arr[i]。
• 當 i == 7 時，先列印該次數值，再執行 break。

列印值依序為：

選項分析

此題考查程式語言的分類。C# (C Sharp) 是一種現代、物件導向的程式語言，由 Microsoft 開發。

分析選項：
(A) Machine language (機器語言): 這是電腦 CPU 能直接理解和執行的二進位指令碼。C# 不是機器語言。
(B) Formal language (形式語言): 這是用嚴格的語法規則定義的語言，電腦科學中用來描述語法結構。所有程式語言都是形式語言，但這個分類太廣泛，不是 C# 的特色分類。

核心觀念
本題屬於演算法分析的「漸進式複雜度」比較。

• 漸進符號：$O(\cdot)$、$\Theta(\cdot)$、$\Omega(\cdot)$，僅關心輸入規模 $n$ 趨近無限大時的成長階層。
• 階乘與對數函數的關係：階乘 $k!$ 的增長速度遠快於任何多項式或指數函數（只要指數底不大於 $k$ 本身）。
• 對數的疊加：$\log\log n$、$\log n$ 皆屬於對數階層，成長極慢，且 $\log\log n < \log n$ 在 $n>e$ 時皆成立。

解題方法
將四個選項皆寫成 $O(\cdot)$ 形式，直接比較其漸進增長階層：

1. $100!$ 為固定常數（不含 $n$），但在「複雜度」的語境下，若把 $n$ 視為任意正整數，$100!$ 仍是一個 常數，即 $O(1)$。然而，題目意圖是把「$100!$」視為與 $n$ 無關的極大常數，用以測試受測者是否能辨識「常數」與「變動函式」的差別。
2. $n\log\log n$ 的複雜度為 $O\bigl(n\log\log n\bigr)$。
3. $n\log n$ 的複雜度為 $O\bigl(n\log n\bigr)$。
4. $n$ 的複雜度為 $O(n)$。

比較時，先觀察 量級：

• $n\log\log n$ < $n\log n$ （因 $\log\log n < \log n$）。
• $n$ < $n\log\log n$（因 $\log\log n>1$ 對於足夠大的 $n$），同理 $n$ < $n\log n$。

因此在四個函式中，最高的增長速率是 $n\log n$。

選項分析

核心觀念

• 遞迴樹法：將遞迴式 $T(n)=2T(n/2)+f(n)$ 以樹狀結構展開，計算每一層的總工作量，再把各層相加得到總時間。
• 漸進和：$\displaystyle\sum_{i=1}^{m}\frac1i = \Theta(\log m)$（調和級數）。
• 主定理延伸：當 $f(n)=\Theta\!\left(\dfrac{n}{\log n}\right)$ 與 $n^{\log_b a}=n$ 同階但低了一個 $\log n$ 因子時，總成本會多出一層 $\log\log n$ 的因子。

解題方法

以遞迴樹法展開：

第 $i$ 層（$i=0,1,\dots ,\log_2 n-1$）：

• 子問題大小：$\displaystyle \frac{n}{2^{i}}$
• 子問題個數：$2^{i}$
• 每個子問題的非遞迴代價：$\displaystyle f\!\left(\frac{n}{2^{i}}\right)=\frac{n/2^{i}}{\log (n/2^{i})}$

因此第 $i$ 層的總代價：

樹高為 $\log_2 n$，令 $m=\log n$（底數不影響漸進等價），則總和為

此題考查遞迴關係式 (Recurrence Relation) 的求解。給定的遞迴關係式為：
$T(n) = 2T(n/2) + \log n$

這個遞迴關係式非常接近主定理 (Master Theorem) 的形式。
我們將其與主定理的標準形式 $T(n) = aT(n/b) + f(n)$ 進行比較。
在這裡，$a=2$, $b=2$, $f(n) = \log n$。

首先計算 $n^{\log_b a}$:
$n^{\log_2 2} = n^1 = n$。

現在我們需要比較 $f(n) = \log n$ 與 $n^{\log_b a} = n$ 的成長速度。
$\log n$ 的成長速度遠慢於 $n$。

核心觀念

• 度（Degree）：在樹（Tree）中，節點的度指與該節點相連的邊數。根節點的度等於其子節點數，其他節點的度＝子節點數＋1（與父節點相連）。
• 葉節點（Leaf）：度為 0 的節點。
• 二元樹（Binary Tree）：每個節點最多有兩個子節點。
• 樹的度數與葉節點的關係：對任意一棵樹，若記 $N$ 為節點總數，$n_1$ 為度為 1 的節點數，$n_2$ 為度為 2 的節點數，$L$ 為葉節點數，則有
  $N = L + n_1 + n_2$
  以及樹的邊數等於 $N-1$。在二元樹中，每條邊連接父子兩端，故
  $\text{總邊數}= \underbrace{L}_{\text{葉子無子}} + \underbrace{n_1}_{\text{度1節點有1子}} + 2\underbrace{n_2}_{\text{度2節點有2子}} = N-1$

解題方法

1. 設 $L$ 為葉節點數，已知 $N=15$、$n_1=4$，未知 $n_2$。
2. 由二元樹的邊數公式
   $L + n_1 + 2n_2 = N-1 = 14$
3. 代入已知值：
   $L + 4 + 2n_2 = 14 \quad\Rightarrow\quad L + 2n_2 = 10$
4. 再利用節點總數關係 $N = L + n_1 + n_2$：
   $15 = L + 4 + n_2 \quad\Rightarrow\quad L + n_2 = 11$
5. 從第 3、4 步得到兩個方程式

用第二式減第一式：
$(L+n_2) - (L+2n_2) = 11-10 \;\Rightarrow\; -n_2 = 1 \;\Rightarrow\; n_2 = -1$
這顯示直接使用上述兩式會產生矛盾，原因在於度 1 的節點在二元樹中必然是內部節點，而葉節點不計入 $n_1$。因此應直接使用樹的 度數與葉節點的通式
$L = n_0 = 1 + n_2$
其中 $n_0=L$。

此題考查循環神經網路 (Recurrent Neural Network, RNN) 的相關模型。RNN 是一種用於處理序列數據的神經網路。

分析選項：

• LSTM (Long Short-Term Memory): LSTM 是一種特殊的 RNN，它設計用於解決傳統 RNN 在處理長序列時遇到的梯度消失或梯度爆炸問題，能夠更好地捕捉長距離依賴關係。它是 RNN 的一種變體。
• BiLSTM (Bidirectional LSTM): BiLSTM 是雙向 LSTM。它結合了兩個 LSTM，一個順向處理序列，另一個逆向處理序列，然後將兩者的輸出結合起來。它仍然是基於 LSTM 的，因此也是 RNN 的一種。

此題考查深度學習模型與強化學習 (Reinforcement Learning, RL) 的關聯。

• VLM (Vision-Language Model): VLM 是一種結合了視覺 (Computer Vision) 和語言 (Natural Language Processing) 的深度學習模型，例如 CLIP, ViLT 等。它們通常用於圖像字幕生成、視覺問答等任務，這些任務可以看作是「監督學習」或「自監督學習」的範疇，不直接屬於強化學習的範疇。雖然 RL 有時會用來訓練 VLM 達成特定目標，但 VLM 本身不是一個 RL 演算法或模型架構。
• Dueling DQN (Dueling Deep Q-Network): DQN 是一種基於 Q-learning 的深度強化學習演算法，用於離散動作空間。

此題考查深度學習 (Deep Learning) 相關的軟體套件。

• scikit-learn: 這是 Python 中一個非常流行的機器學習庫，提供了許多經典的機器學習演算法（如 SVM, Random Forest, KMeans 等），也包含一些神經網路的實現，但它不是專門為深度學習設計的，且其深度學習功能相對有限。
• torch (PyTorch): PyTorch 是由 Facebook (現 Meta) 開發的一個開源機器學習框架，廣泛用於深度學習研究和應用。

此題考查強化學習 (Reinforcement Learning, RL) 相關的軟體套件。

• gym (OpenAI Gym): OpenAI Gym 是一個用於開發和比較強化學習演算法的工具包。它提供了一個標準化的介面，讓使用者可以輕鬆地與各種模擬環境互動（如遊戲、機器人模擬等），並在此環境中訓練 RL 代理 (agent)。

此題考查計算的數學模型 (Mathematical Model of Computation)。

• von Neumann architecture: 這是電腦硬體的一種架構模型，描述了如何組織 CPU、記憶體、輸入/輸出設備等。它是一個硬體架構模型，不是純粹的數學模型。

核心觀念

本題考判斷問題是否為 NP-complete（NP 完全）。一個問題要是 NP 完全，必須同時符合：

1. 屬於 NP：給定一個候選解，可以在多項式時間內驗證它是否正確。
2. NP-hard（NP 困難）：所有 NP 問題都能在多項式時間內歸約到它。

本題以標準複雜度理論分類作答，採用通常的假設 $P \ne NP$。因此，若一個非平凡問題已知可在多項式時間內求解，就不會分類為 NP 完全。

解題方法

先辨認各問題的已知複雜度：

• 2-SAT 可用強連通分量演算法在多項式時間內求解。
• 3-SAT 是經典 NP 完全問題。
• Subset Sum 與 Partition 的決策版本都是 NP 完全問題。

因此，題目問「哪個不是 NP 完全問題」，應選可在多項式時間內求解的 2-SAT。

選項分析

• (A) 2-SAT problem：正確答案。
  2-SAT 的每個子句最多包含兩個文字，例如 $(x_1 \lor \neg x_2)$。可將變數及其否定轉成蘊含圖的頂點，並以強連通分量演算法判斷是否有矛盾，時間複雜度為 $O(V+E)$，因此屬於 $P$。在標準假設 $P \ne NP$ 下，2-SAT 不是 NP 完全問題。

核心觀念 – NP 與 NP‑Complete

• NP（Nondeterministic Polynomial time）是指給定一個「是」的答案，能在多項式時間內由驗證者檢查其正確性。
• NP‑Complete 必須同時滿足兩個條件：
  1. 屬於 NP（即是決策問題，答案「Yes」能在多項式時間驗證）。
  2. NP‑Hard（所有 NP 問題皆可在多項式時間歸約到此問題）。
• 常見的判斷技巧：先看問題是否決策化（例如「是否存在…」），再檢視是否已知為 NP‑Complete；若是多項式時間可解的優化問題（如最短路徑），則不在 NP‑Complete 範疇。

解題方法 – 逐一檢驗選項是否符合 NP‑Complete 定義

1. 確認每個選項是決策問題（Yes/No）或可改寫為決策問題。
2. 判斷該問題是否已知屬於 P（多項式時間可解），若是則不可能是 NP‑Complete（因為 P ⊆ NP 且若 P = NP‑Complete 則 P = NP，已不符合常見複雜度分類假設）。
3. 判斷是否 不可判定（如 Halting Problem），若不可判定則不屬於 NP。

選項分析

核心觀念

在無向圖中，若一組頂點彼此兩兩相鄰，這些頂點所形成的子圖稱為完全子圖（complete subgraph），也稱為團（clique）。尋找圖中的團，稱為團問題（clique problem）。

「極大」與「最大」有細微差異：

• 極大團（maximal clique）：無法再加入其他頂點而仍保持完全子圖。
• 最大團（maximum clique）：所有團之中頂點數最多者。

兩者都屬於團問題的範疇。

解題方法

題目問「尋找極大完全子圖」的問題名稱。先抓住「完全子圖」這個關鍵詞：頂點集合中的每一對頂點都必須有邊相連。這正是團的定義，因此對應團問題。

選項分析

此題考查十進位數字轉換為不同進位制的數字。

方法： 採用除法取餘法。不斷將十進位數除以目標進制，記錄餘數，直到商為 0。將餘數從下往上排列即為目標進制的表示。

(a) 轉換為八進位 (Octal, 8進制):

將 $(75)_{10}$ 除以 8：
$75 \div 8 = 9$ 餘 3
$9 \div 8 = 1$ 餘 1
$1 \div 8 = 0$ 餘 1

核心觀念

本題考查遞迴式的漸近分析，適合使用 Akra–Bazzi 定理：

若

先求唯一的 $p$ 使得

則

本題兩小題皆有 $g(n)=n$。

（a）$T(n)=T(n/5)+T(4n/5)+n$

解題方法

令

依 Akra–Bazzi 定理，求 $p$：

代入 $p=1$：

因此

接著計算積分：

代回 Akra–Bazzi 公式：

遞迴樹直觀理解

每個遞迴節點的額外成本等於其輸入規模。每一層所有子問題規模總和為

因此每一層的總成本為 $\Theta(n)$。遞迴深度為 $\Theta(\log n)$，故總成本為

（b）$T(n)=T(n/6)+T(5n/7)+n$

解題方法

令

求 $p$：

先觀察 $p$ 的範圍。當 $p=0$ 時：

當 $p=1$ 時：

此題考查遞迴函數的執行流程和輸出結果。我們需要模擬函數的調用過程，追蹤變數 N 的值和 print 語句的執行順序。

初始調用：func_1(1)

1. func_1(1):
   • print(1) -> 輸出 1
   • N < 100 (1 < 100) 為 True。
   • 調用 func_1(1 * 3)，即 func_1(3)。
     • func_1(3):
       • print(3) -> 輸出 3
       • N < 100 (3 < 100) 為 True。
       • 調用 func_1(3 * 3)，即 func_1(9)。
         • func_1(9):
           • print(9) -> 輸出 9
           • N < 100 (9 < 100) 為 True。
           • 調用 func_1(9 * 3)，即 func_1(27)。
             • func_1(27):
               • print(27) -> 輸出 27
               • N < 100 (27 < 100) 為 True。
               • 調用 func_1(27 * 3)，即 func_1(81)。
                 • func_1(81):
                   • print(81) -> 輸出 81
                   • N < 100 (81 < 100) 為 True。
                   • 調用 func_1(81 * 3)，即 func_1(243)。

此題考查氣泡排序 (Bubble Sort) 的執行過程。氣泡排序通過重複地走訪列表，一次比較兩個相鄰的元素，如果它們的順序錯誤就交換它們。這個過程會不斷重複，直到列表排序完成。

原始數據：6, 2, 7, 4, 3, 5, 1

第一輪 (Iteration 1):
比較並交換相鄰元素，將最大的元素「冒泡」到最後。

• (6, 2) -> 2, 6, 7, 4, 3, 5, 1 (交換)
• (6, 7) -> 2, 6, 7, 4, 3, 5, 1 (不交換)
• (7, 4) -> 2, 6, 4, 7, 3, 5, 1 (交換)
• (7, 3) -> 2, 6, 4, 3, 7, 5, 1 (交換)
• (7, 5) -> 2, 6, 4, 3, 5, 7, 1 (交換)
• (7, 1) -> 2, 6, 4, 3, 5, 1, 7 (交換)
  結果：2, 6, 4, 3, 5, 1, 7 (7 已到正確位置)

第二輪 (Iteration 2):
比較到倒數第二個元素。

• (2, 6) -> 2, 6, 4, 3, 5, 1, 7 (不交換)
• (6, 4) -> 2, 4, 6, 3, 5, 1, 7 (交換)
• (6, 3) -> 2, 4, 3, 6, 5, 1, 7 (交換)
• (6, 5) -> 2, 4, 3, 5, 6, 1, 7 (交換)
• (6, 1) -> 2, 4, 3, 5, 1, 6, 7 (交換)
  結果：2, 4, 3, 5, 1, 6, 7 (6 已到正確位置)

第三輪 (Iteration 3):
比較到倒數第三個元素。

• (2, 4) -> 2, 4, 3, 5, 1, 6, 7 (不交換)
• (4, 3) -> 2, 3, 4, 5, 1, 6, 7 (交換)
• (4, 5) -> 2, 3, 4, 5, 1, 6, 7 (不交換)
• (5, 1) -> 2, 3, 4, 1, 5, 6, 7 (交換)
  結果：2, 3, 4, 1, 5, 6, 7 (5 已到正確位置)

核心觀念

• Binary Search Tree (BST)：左子樹所有節點的值均小於根節點，右子樹所有節點的值均大於根節點。
• 遍歷序列
  • Inorder（左‑根‑右）對 BST 會得到遞增序列。
  • Postorder（左‑右‑根）最後一個元素必為樹的根。
  • Preorder（根‑左‑右）與 Level order（層序）可由已建好的樹直接產生。
• 利用 Inorder 與 Postorder 重建唯一二元樹：給定兩種遍歷且節點值互不相同時，樹唯一確定。

解題方法

1. 找出根節點

   • Postorder 序列的最後一個元素是根：4。

2. 在 Inorder 中切分左右子樹

   • Inorder = 1 2 3 4 5 6 7 8
   • 4 左側 1 2 3 為左子樹的 Inorder，右側 5 6 7 8 為右子樹的 Inorder。

3. 對左子樹遞迴

   • 左子樹的 Postorder 為前 3 個元素（與左 Inorder 長度相同）：1 3 2。
   • 根 = 2（最後一個）。
   • 在左 Inorder 1 2 3 中，2 左側 1 為左子樹，右側 3 為右子樹。
   • 左子樹的左子樹 Postorder 為 1 → 根 1，只有單一節點。
   • 左子樹的右子樹 Postorder 為 3 → 根 3，只有單一節點。

4. 對右子樹遞迴

   • 右子樹的 Postorder 為剩下的 4 個元素：6 5 8 7（與右 Inorder 長度相同）。
   • 根 = 7（最後一個）。
   • 在右 Inorder 5 6 7 8 中，7 左側 5 6 為左子樹，右側 8 為右子樹。
   • 左子樹（節點 5、6）
     • Postorder 對應前 2 個：6 5。根 = 5。
     • 在 Inorder 5 6 中，5 左無，右為 6。
     • 6 為右子節點（單一）。