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

此題考查數位影像的基本概念，特別是灰階影像的像素值範圍。

灰階影像（Grayscale Image）中的每個像素通常用一個數值來表示其亮度。這個數值的大小決定了像素的灰階程度，從最暗（通常是黑色）到最亮（通常是白色）。常見的灰階表示法有 8 位元、10 位元、12 位元等。

• 8 位元灰階：這是最常見的表示法。每個像素使用 8 個位元來儲存其亮度值。由於 8 個位元可以表示 $2^8 = 256$ 種不同的值，因此其範圍通常是從 0（黑色）到 255（白色）。
• 10 位元灰階：每個像素使用 10 個位元，範圍從 0 到 $2^{10}-1 = 1023$。

此題考查基本的二進位減法運算。

首先計算十進位的減法：
$26 - 7 = 19$

接著將十進位的數字 19 轉換為二進位表示。
我們可以使用除以 2 取餘數的方法：
$19 \div 2 = 9$ ... 餘 1
$9 \div 2 = 4$ ... 餘 1
$4 \div 2 = 2$ ... 餘 0
$2 \div 2 = 1$ ... 餘 0
$1 \div 2 = 0$ ... 餘 1

將餘數從下往上讀取，得到二進位表示為 $10011_2$。

選項分析：
A. $10000_2 = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 = 16$

此題考查十進位小數轉換為二進位小數。

我們將整數部分和小數部分分開轉換。

整數部分：70
使用除以 2 取餘數的方法：
$70 \div 2 = 35$ ... 餘 0
$35 \div 2 = 17$ ... 餘 1
$17 \div 2 = 8$ ... 餘 1
$8 \div 2 = 4$ ... 餘 0
$4 \div 2 = 2$ ... 餘 0
$2 \div 2 = 1$ ... 餘 0
$1 \div 2 = 0$ ... 餘 1
從下往上讀取餘數，得到整數部分的二進位表示為 $1000110_2$。

此題考查常見的數位影像檔案格式。

• GIF (Graphics Interchange Format)：一種點陣圖形檔案格式，支援動畫和透明背景，常用於網頁圖像。
• JPG (Joint Photographic Experts Group)：一種有損壓縮的點陣圖形檔案格式，常用於照片，能有效減小檔案大小。

此題考查計算機結構中關於指令集架構 (Instruction Set Architecture, ISA) 的知識。

MIPS (Microprocessor without Interlocked Pipeline Stages) 是一種 RISC (Reduced Instruction Set Computer) 架構的處理器。RISC 的核心思想是使用一套較少、較簡單、固定長度的指令，以流水線 (pipeline) 的方式提高處理器執行效率。

此題考查位元運算 (bitwise operation)，特別是位元 AND 運算。

首先，我們需要將兩個十進位數字 14 和 11 轉換為二進位表示：
$14_{10} = 8 + 4 + 2 = 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 1110_2$
$11_{10} = 8 + 2 + 1 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 1011_2$

此題考查作業系統的 CPU 排程演算法，特別是非先佔式最短作業優先 (Non-preemptive Shortest Job First, SJF)。

核心觀念：

• 非先佔式 (Non-preemptive)：一旦一個程序開始執行，它會一直執行到完成，不會被中斷。
• 最短作業優先 (SJF)：在有多個程序準備好執行時，選擇預計執行時間（Burst Time）最短的程序優先執行。
• 等待時間 (Waiting Time)：程序從到達系統到開始執行之間所花費的時間。
• 平均等待時間 (Average Waiting Time)：所有程序的等待時間總和除以程序的數量。

題目情境分析：
所有程序 P1, P2, P3 在時間 0 就到達了。
P1 的 Burst Time = 8
P2 的 Burst Time = 4
P3 的 Burst Time = 2

由於是 SJF 演算法，在時間 0 時，系統會比較這三個程序的 Burst Time，並選擇最短的 P3 開始執行。

執行順序與時間軸：

1. 時間 0：P1, P2, P3 都到達。

   • Burst Times: P1=8, P2=4, P3=2。
   • SJF 選擇 P3 (Burst Time=2)。
   • P3 開始執行。

2. 時間 0 到 2：P3 執行。

   • P3 執行完畢。
   • P1 和 P2 都在等待。

3. 時間 2：P3 完成，CPU 可用。

   • 剩餘未執行的程序是 P1 (Burst Time=8) 和 P2 (Burst Time=4)。
   • SJF 選擇 Burst Time 較短的 P2。

此題考查作業系統的 CPU 排程演算法，延續上一題 SJF 排程的情境，計算平均週轉時間 (Average Turnaround Time)。

核心觀念：

• 週轉時間 (Turnaround Time, TAT)：程序從到達系統到執行完畢為止所花費的總時間。
• TAT = Completion Time - Arrival Time
• 或者，TAT = Burst Time + Waiting Time

延續上一題的執行順序與時間軸：

• P1: Arrival=0, Burst=8, Start=6, WT=6
• P2: Arrival=0, Burst=4, Start=2, WT=2
• P3: Arrival=0, Burst=2, Start=0, WT=0

計算週轉時間 (Turnaround Time, TAT)：

• P1：
  • Arrival Time = 0
  • Completion Time = Start Time + Burst Time = 6 + 8 = 14
  • TAT(P1) = Completion Time - Arrival Time = 14 - 0 = 14
  • (或 TAT(P1) = Burst Time + Waiting Time = 8 + 6 = 14)

此題考查物聯網 (Internet of Things, IoT) 裝置的電腦系統特性。

物聯網裝置通常是指嵌入在各種日常物品中，能夠透過網路收集、傳輸或處理數據的裝置。這些裝置的電腦系統通常具有以下特點：

• 體積小、功耗低：為了便於整合到各種物品中，並且長時間運作（例如電池供電），它們的硬體設計要求小巧且節能。
• 特定功能：通常設計來執行特定的任務，例如感測環境數據、控制家電、追蹤位置等。
• 嵌入式硬體和軟體：運行在專門設計的微控制器或微處理器上，並搭載專用的作業系統或韌體。

基於這些特點，最適合描述 IoT 裝置電腦系統的術語是「嵌入式系統」。

此題考查行動通訊技術的分類。

LTE (Long-Term Evolution) 是 4G 行動通訊技術的標準。它是一種無線寬頻技術，用於提供比 3G 更快的數據傳輸速度。

我們來分析各個選項：
A. PAN (Personal Area Network)：個人區域網路，範圍非常小，通常是幾公尺內，例如藍牙連接耳機與手機。
B. LAN (Local Area Network)：區域網路，通常指一個建築物或一個校園內的網路，例如家庭 Wi-Fi 或辦公室網路。

此題考查網路安全與連線技術。題目詢問哪種技術能為遠端使用者提供與原始網路的安全連接。

• HTTP (Hypertext Transfer Protocol)：超文本傳輸協定，用於在網際網路上的客戶端（如瀏覽器）和伺服器之間傳輸網頁內容。雖然有 HTTPS (HTTP Secure)，但 HTTP 本身不提供安全連接。
• FTP (File Transfer Protocol)：檔案傳輸協定，用於在客戶端和伺服器之間傳輸檔案。FTP 本身不提供加密，傳輸的資料是明文的，不安全。

此題考查網路協定與電子郵件系統的關聯性。

我們來分析各個選項：

• POP3 (Post Office Protocol version 3)：一種用於從郵件伺服器下載電子郵件到本地客戶端的協定。它與電子郵件系統直接相關。
• IMAP (Internet Message Access Protocol)：另一種用於存取和管理郵件伺服器上電子郵件的協定。它允許使用者在伺服器上直接操作郵件，並與 POP3 一樣，與電子郵件系統直接相關。
• TCP (Transmission Control Protocol)：傳輸控制協定。

這題考驗對物體追蹤技術的認識。

• A. beacon (信標)：通常指藍牙信標 (Bluetooth Beacon)，是一種小型無線發射器，可以定期廣播其識別碼。行動裝置可以偵測到這些信標，進而實現基於位置的服務或追蹤。
• B. Bluetooth (藍牙)：一種短距離無線通訊技術，可用於設備之間的連接和數據傳輸。它也可以用於定位和追蹤，例如透過藍牙信標或藍牙設備之間的訊號強度。
• C. RFID (Radio-Frequency Identification)：無線射頻識別。這是一種自動識別技術，透過無線電波識別和追蹤附有 RFID 標籤的物體。RFID 標籤包含一個微晶片和天線，可以儲存並發送資訊，廣泛用於物品追蹤、庫存管理、門禁系統等。

此題考查網路安全工具，特別是封包側錄 (packet sniffing) 工具。

• Packet Sniffer (封包側錄器)：是一種軟體或硬體工具，用於攔截、記錄網路上的數據封包，並對其進行分析。這對於網路故障排除、效能監控、安全分析都非常有用。
• A. Trojan horse (木馬程式)：一種惡意軟體，偽裝成合法程式，但實際上會執行惡意操作，例如竊取資訊、建立後門等。它不是封包側錄工具。

此題考查排序演算法「快速排序」(Quick Sort) 的時間複雜度。

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

1. 選擇一個基準點 (pivot)。
2. 分割 (partition)：將陣列重新排序，使得所有小於基準點的元素都在基準點的左側，所有大於基準點的元素都在基準點的右側。這個分割操作會將基準點放到其最終排序位置。
3. 遞迴排序：遞迴地對基準點左側和右側的子陣列進行排序。

時間複雜度分析：

• 最佳情況 (Best Case)：當每次分割都能將陣列平均分成兩半時，時間複雜度為 $O(n \log n)$。
• 平均情況 (Average Case)：在隨機選擇基準點或使用一些策略來選擇基準點（如三數取中法）時，分割點通常能接近平均分成兩半。

這題考驗對 Verilog 這門語言的分類。

Verilog 是一種硬體描述語言 (Hardware Description Language, HDL)。它用於描述數位系統的電子電路設計，例如 FPGA 和 ASIC。

• A. machine language (機器語言)：由二進位碼組成，是電腦 CPU 直接執行的語言。Verilog 不是機器語言。
• B. formal language (形式語言)：形式語言是由一套嚴格定義的規則（語法和語義）所組成的符號系統。Verilog 具有嚴格的語法和語義，因此屬於形式語言。

此題考查 C++ 程式碼的邏輯與輸出結果。

程式碼分析：

1. int arr[10];：宣告一個包含 10 個整數的陣列 arr。陣列索引從 0 到 9。

2. for(int i=0; i<10; ++i) arr[i]=i*i;：
   這個迴圈會將陣列 arr 的每個元素初始化為其索引的平方。

   • arr[0] = 0*0 = 0
   • arr[1] = 1*1 = 1
   • arr[2] = 2*2 = 4
   • arr[3] = 3*3 = 9
   • arr[4] = 4*4 = 16
   • arr[5] = 5*5 = 25
   • arr[6] = 6*6 = 36
   • arr[7] = 7*7 = 49
   • arr[8] = 8*8 = 64
   • arr[9] = 9*9 = 81
     迴圈結束後，i 的值會是 10 (因為 i<10 的條件變為 false)。

3. if(i%3==0) cout << arr[i] << " ";：
   這個 if 語句檢查 i 是否能被 3 整除。
   關鍵點：這個 if 語句在第一個 for 迴圈之後執行。
   在第一個 for 迴圈結束時，變數 i 的值是 10。
   因此，if(i%3==0) 實際上是 if(10%3==0)，即 if(1==0)，這個條件是false。
   所以，這個 if 語句內的 cout << arr[i] << " "; 不會被執行。

4. cout << endl;：
   這行程式碼會輸出一個換行符，結束當前的輸出列。

總結輸出：
由於 if(i%3==0) 條件在 for 迴圈結束後，i 的值為 10，不滿足 i%3==0，因此 cout << arr[i] << " "; 這行輸出語句沒有被執行。程式碼只會執行到 cout << endl;，這會輸出一個空行。

然而，如果題目中的 if 語句是寫在第一個 for 迴圈裡面（例如，原本是想這樣寫：

int arr[10];
for(int i=0; i<10; ++i) {
  arr[i]=i*i;
  if(i%3==0) { // <--- 這裡
    cout << arr[i] << " ";
  }
}
cout << endl;

），那麼輸出就會是：
當 i=0, 0%3==0, 輸出 arr[0]=0

此題考查軟體開發生命週期 (Software Development Life Cycle, SDLC) 的傳統階段。

傳統的 SDLC 模型（如瀑布模型 Waterfall Model）通常包含以下幾個主要階段：

1. Requirement Analysis (需求分析)：定義軟體的功能、效能、限制等。
2. Design (設計)：根據需求，設計軟體的架構、資料庫、使用者介面等。
3. Implementation (實作/編碼)：根據設計，編寫程式碼。
4. Testing (測試)：驗證軟體是否符合需求，找出並修復錯誤。
5. Deployment (部署)：將軟體安裝到使用者環境中。

核心觀念

• 樹（Tree）：一種無環的連通圖，每個節點最多有一個父節點。
• 葉節點（Leaf node）：在樹中沒有子節點的節點（即 out‑degree 為 0），根節點若沒有子節點亦視為葉節點。
• 兄弟節點（Siblings）：指同屬於同一個父節點的兩個節點。

本題考查對「父子關係」與「兄弟關係」的互相推導，以及葉節點的辨識。

---

解題方法

1. 先根據「B 與 C 為兄弟」推出 B、C 共享同一父節點。
2. 由題目僅給出四個節點 A、B、C、D，且已知 B、C 的父節點必須在 {A、D} 中（A 已是 B 的子節點，無法同時為父節點）。因此唯一可能的父節點是 D。
3. 再根據「A 的父節點是 B」可得 B 為 A 的直接父節點，亦即 B 有子節點 A。
4. 整理得到的樹結構：

      D
    /   \
   B     C
   |
   A

此題延續上一題，要求找出樹的根節點。

根據上一題的分析，我們構建的樹結構如下：
D (根節點)
/
B C
/
A

• B 和 C 是兄弟節點，它們有共同的父節點。
• A 的父節點是 B。

此題考查數據分析與知識發現的相關術語。

• A. database constructing (資料庫建構)：指建立和設計資料庫的過程，包括資料庫模式設計、資料表創建、索引建立等。這不是發現模式的技術。
• B. data robbing (資料搶奪)：這不是一個標準的電腦科學術語，通常不被使用。若有，可能指非法獲取數據，與發現模式無關。

此題考查圖形學和計算相關的 API。題目要求找出一個跨語言、跨平台的 API，用於渲染 2D 和 3D 向量圖形。

• A. OpenCV (Open Source Computer Vision Library)：開源計算機視覺庫。OpenCV 主要用於圖像處理、影片分析和計算機視覺任務，雖然它可能涉及圖形渲染，但其核心功能不是專門用於「渲染 2D 和 3D 向量圖形」的 API。
• B. OpenGL (Open Graphics Library)：開放圖形函式庫。

此題考查機器學習中的強化學習 (Reinforcement Learning, RL) 模型。

• A. actor-critic (演員-評論家)：演員-評論家模型是一種常見的強化學習演算法架構。它結合了策略梯度方法（演員，負責學習策略）和價值函數方法（評論家，負責評估策略的好壞），通常能獲得較好的學習效果。
• B. LSTM (Long Short-Term Memory)：長短期記憶網路。LSTM 是一種特殊的循環神經網路 (RNN)，擅長處理序列數據，常用於自然語言處理、語音識別等任務。它本身不是強化學習的「模型」，而是可以用於構建強化學習中的「演員」或「評論家」的神經網路架構。

核心觀念

本題測驗計算複雜度理論（Computational Complexity Theory）中的問題分類，特別是 P 問題（Polynomial time） 與 NP-complete 問題（NP-完全問題） 的判定：

1. P 類別（Polynomial Time）：可以在確定型杜林機（Deterministic Turing Machine）上，於多項式時間內被解決的問題集合。
2. NP 類別（Nondeterministic Polynomial Time）：其解可以在多項式時間內被驗證（Verify）的決定性問題集合。
3. NP-complete（NPC）：同時滿足以下兩個條件的問題：
   • 該問題屬於 NP。
   • 該問題屬於 NP-hard（即 NP 中的所有問題皆可在多項式時間內歸約至該問題）。
   • 目前尚未發現能在多項式時間內解決 NPC 問題的確定型演算法。

---

解題方法

判定各選項所屬的複雜度類別：

1. 檢視各選項演算法或問題是否存在已知可在多項式時間（如 $O(V + E)$、$O(V^3)$ 等）內求得解答的確定型演算法。
2. 若存在多項式時間演算法，則屬於 P 問題（非 NP-complete）。
3. 若問題目前已知無多項式時間解法，且為經典的 NP-complete 問題，即為所求。

---

選項分析

• A. depth-first-search problem（深度優先搜尋問題）：錯誤。

  • DFS 是圖論中最基礎的走訪演算法。若使用鄰接串列（Adjacency List）表示圖形，其時間複雜度為 $O(|V| + |E|)$，屬於多項式時間可解的 P 問題。

• B. breadth-first-search problem（廣度優先搜尋問題）：錯誤。

  • BFS 同樣為線性時間走訪演算法，使用鄰接串列時時間複雜度為 $O(|V| + |E|)$，亦可在多項式時間內完成，屬於 P 問題。

這題考驗對不同進位制數字的轉換，特別是將八進位數轉換為十進位數。

題目給定的數字是 $(45)_8$，表示一個八進位數。
八進位的每一位代表 $8$ 的冪次。從右往左，權重分別是 $8^0, 8^1, 8^2, \ldots$。

此題考查不同進位制的數字轉換，特別是從八進位轉換為十六進位。

核心概念：
八進位 (Octal) 使用 8 個數字 (0-7)。
十六進位 (Hexadecimal) 使用 16 個數字 (0-9, A-F)。
其中，A 代表 10, B 代表 11, C 代表 12, D 代表 13, E 代表 14, F 代表 15。

直接從八進位轉換為十六進位比較複雜，通常的做法是：

1. 將八進位數轉換為二進位數。
2. 將二進位數轉換為十六進位數。

步驟 1：將八進位數 $(45)_8$ 轉換為二進位數。
八進位的一個數字可以對應三個二進位數字（因為 $2^3 = 8$）。

• 8 進位的 4 對應二進位的 100 ($2^2 \times 1 + 2^1 \times 0 + 2^0 \times 0 = 4$)。
• 8 進位的 5 對應二進位的 101 ($2^2 \times 1 + 2^1 \times 0 + 2^0 \times 1 = 5$)。

將它們組合起來，得到二進位數：
$(45)_8 = (100 \ 101)_2$

步驟 2：將二進位數 $(100101)_2$ 轉換為十六進位數。
十六進位的一個數字可以對應四個二進位數字（因為 $2^4 = 16$）。
我們從二進位數的最右邊開始，每四位一組進行分組。如果最左邊不足四位，則在前面補 0。

這題考驗對 IPv4 位址結構的理解，特別是網路 ID (Network ID) 和主機 ID (Host ID) 的劃分。

IPv4 位址結構：
一個 IPv4 位址由 32 位元組成，通常表示為四個十進位數，每個數代表 8 位元 (一個位元組)，中間用點分隔。例如：140.123.1.1。
IP 位址的劃分方式取決於其類別 (Classful IP Addressing) 或無類別域際路由選擇 (CIDR)。在沒有額定子網路遮罩 (Subnet Mask) 的情況下，我們通常會根據 IP 位址的第一個位元組來判斷其類別。

IP 位址類別：

• Class A: 1.0.0.0 to 126.255.255.255。網路 ID 佔第一個位元組，主機 ID 佔後三個位元組。預設子網路遮罩為 255.0.0.0。
• Class B: 128.0.0.0 to 191.255.255.255。網路 ID 佔前兩個位元組，主機 ID 佔後兩個位元組。預設子網路遮罩為 255.255.0.0。
• Class C: 192.0.0.0 to 223.255.255.255。網路 ID 佔前三個位元組，主機 ID 佔最後一個位元組。預設子網路遮罩為 255.255.255.0。

分析給定的 IP 位址 140.123.1.1：

• 第一個位元組是 140。
• 140 落在 128 到 191 的範圍內，所以這是一個 Class B 的 IP 位址。

根據 Class B 的規則：

• 網路 ID (Network ID)：佔 IP 位址的前兩個位元組。
  • 網路 ID = 140.123.0.0
• 主機 ID (Host ID)：佔 IP 位址的後兩個位元組。
  • 主機 ID = 1.1

核心觀念

本題考查：

• C 語言函式的撰寫。
• 變數初始化與迴圈控制。
• 整數次方的計算。
• 演算法時間複雜度分析。

對於非負整數 $e$，有：

$$b^e=\underbrace{b\times b\times\cdots\times b}_{e\text{ 次}}$$

其中：

$$b^0=1$$

題目未指定負指數的回傳型別與處理方式；以下採用一般考試中的合理假設：$e\ge 0$，並以 long long 儲存結果。

解題方法

使用「快速冪」或「平方倍增法」。其核心依據為：

若 $e$ 為偶數：

$$b^e=(b^2)^{e/2}$$

若 $e$ 為奇數：

$$b^e=b\times b^{e-1}$$

每次將指數除以 $2$，因此迴圈次數為 $O(\log e)$。

例如計算 $b^{13}$：

$$13=1101_2$$

計算過程會依序處理指數的二進位位元：

• 指數為奇數時，將目前的 base 乘入 result。
• 每一輪將 base 平方。
• 將指數除以 $2$。

參考程式碼

這題考驗根據前序 (Preorder) 和中序 (Inorder) 遍歷重建二元搜尋樹 (Binary Search Tree, BST)，並找出其層序 (Level Order) 和後序 (Postorder) 遍歷。

已知資訊：

• Preorder: 7, 3, 1, 5, 11, 9, 13, 15
• Inorder: 1, 3, 5, 7, 9, 11, 13, 15

核心原理：

1. 前序遍歷 (Preorder Traversal): 節點順序是「根 -> 左子樹 -> 右子樹」。
2. 中序遍歷 (Inorder Traversal): 節點順序是「左子樹 -> 根 -> 右子樹」。
3. 後序遍歷 (Postorder Traversal): 節點順序是「左子樹 -> 右子樹 -> 根」。
4. 層序遍歷 (Level Order Traversal): 按層次從上到下、從左到右遍歷節點。
5. 二元搜尋樹 (BST) 性質： 對於任意節點，其左子樹中所有節點的值都小於該節點的值，其右子樹中所有節點的值都大於該節點的值。

重建 BST 的步驟：

1. 找到根節點： 前序遍歷的第一個元素永遠是樹的根節點。

   • 根節點 = 7。

2. 分割中序遍歷： 在中序遍歷序列 1, 3, 5, 7, 9, 11, 13, 15 中找到根節點 7。

   • 7 左邊的元素 (1, 3, 5) 組成左子樹的中序遍歷。
   • 7 右邊的元素 (9, 11, 13, 15) 組成右子樹的中序遍歷。

3. 分割前序遍歷：

   • 前序遍歷的剩餘部分是 3, 1, 5, 11, 9, 13, 15。
   • 左子樹的節點數量等於左子樹中序遍歷的節點數量。左子樹有 3 個節點 (1, 3, 5)。
   • 所以，前序遍歷中緊隨根節點之後的 3 個元素 (3, 1, 5) 屬於左子樹的前序遍歷。
   • 前序遍歷中剩餘的元素 (11, 9, 13, 15) 屬於右子樹的前序遍歷。

遞迴處理左子樹：

• Preorder (Left): 3, 1, 5
• Inorder (Left): 1, 3, 5
  • 根節點 = 3。
  • 在中序 1, 3, 5 中，3 左邊是 1 (左子樹)，右邊是 5 (右子樹)。
  • 前序 3, 1, 5 中，3 後面的 1 個元素 (1) 是左子樹前序。
  • 前序 3, 1, 5 中，3 後面的 1 個元素 (5) 是右子樹前序。
  • 左子樹 of 3: Preorder: 1, Inorder: 1 -> 節點 1。
  • 右子樹 of 3: Preorder: 5, Inorder: 5 -> 節點 5。
  • 所以，以 3 為根的左子樹結構是：

      3
     / \
    1   5
    

遞迴處理右子樹：

• Preorder (Right): 11, 9, 13, 15
• Inorder (Right): 9, 11, 13, 15
  • 根節點 = 11。
  • 在中序 9, 11, 13, 15 中，11 左邊是 9 (左子樹)，右邊是 13, 15 (右子樹)。
  • 前序 11, 9, 13, 15 中，11 後面的 1 個元素 (9) 是左子樹前序。
  • 前序 11, 9, 13, 15 中，11 後面的 3 個元素 (13, 15) 是右子樹前序。
  • 左子樹 of 11: Preorder: 9, Inorder: 9 -> 節點 9。
  • 右子樹 of 11: Preorder: 13, 15, Inorder: 13, 15

核心觀念

• k‑means（k‑means clustering）：屬於非監督式學習，目的是將資料集合 $\{x_1,\dots ,x_n\}$ 分成 $k$ 個簇，使得每個簇內的樣本到該簇中心的平方距離總和最小。其目標函數為
  $J = \sum_{j=1}^{k}\sum_{x_i\in C_j}\|x_i-\mu_j\|^{2}$
  其中 $\mu_j$ 為第 $j$ 個簇的質心，$C_j$ 為屬於第 $j$ 簇的樣本集合。
• KNN（k‑Nearest Neighbours）：屬於監督式學習（分類或迴歸），對於一個測試樣本 $x$，找出訓練資料中與 $x$ 最近的 $k$ 個樣本，根據這 $k$ 個鄰居的標籤（投票或平均）決定 $x$ 的預測結果。其核心運算是距離度量（如歐氏距離）與鄰居選取。

---

解題方法（說明差異的切入點）

1. 學習階段（Training Phase）

   • k‑means：在訓練階段執行迭代更新（Assignment 步驟 + Update 步驟），直至簇分配不再變化或目標函數收斂。訓練完畢後只留下 $k$ 個質心。
   • KNN：在訓練階段僅儲存全部訓練資料與其標籤，沒有參數學習或模型建構的過程。

2. 預測階段（Prediction / Inference）

   • k‑means：將測試樣本指派至最近的質心，得到其所屬簇（即分類結果）。計算僅涉及與 $k$ 個質心的距離，時間複雜度為 $O(kd)$（$d$ 為特徵維度）。
   • KNN：必須遍歷全部訓練樣本以計算距離，找出最近的 $k$ 個鄰居，時間複雜度為 $O(nd)$（$n$ 為訓練樣本數），儲存需求為 $O(nd)$。

3. 模型性質

   • k‑means：產生 聚類模型（質心），屬於 無監督，不需要標籤。
   • KNN：產生 最近鄰模型（完整資料庫），屬於 監督，需要標籤。

4. 適用情境

   • k‑means：適合探索資料結構、資料壓縮、先行分群等；不適合直接用於已有標籤的分類任務。