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

本題主要考驗二進位表示法。題目要求將十進位數字 28 轉換成二進位。
十進位數字 28 的二進位轉換過程如下：
$28 \div 2 = 14$ 餘 0
$14 \div 2 = 7$ 餘 0
$7 \div 2 = 3$ 餘 1
$3 \div 2 = 1$ 餘 1
$1 \div 2 = 0$ 餘 1
將餘數由下往上排列，得到 $11100_2$。

題目選項為：
(A) 10000
(B) 10001
(C) 10010
(D) 10011

仔細檢查題目，題目是 "28-10"，這表示十進位數字 $28 - 10 = 18$。
我們需要將十進位數字 18 轉換成二進位。
$18 \div 2 = 9$ 餘 0
$9 \div 2 = 4$ 餘 1

本題考驗十進位小數轉換成二進位小數的方法。
對於整數部分 66，轉換方法同前一題：
$66 \div 2 = 33$ 餘 0
$33 \div 2 = 16$ 餘 1
$16 \div 2 = 8$ 餘 0
$8 \div 2 = 4$ 餘 0
$4 \div 2 = 2$ 餘 0
$2 \div 2 = 1$ 餘 0
$1 \div 2 = 0$ 餘 1
整數部分轉換為 $1000010_2$。

本題考驗計算機記憶體層級結構的存取速度。
計算機的記憶體層級結構通常包含暫存器 (register)、快取記憶體 (cache)、主記憶體 (main memory，又稱 RAM) 和輔助儲存 (如硬碟 hard disk)。
這些記憶體的特性如下：

1. 暫存器 (Register)：位於 CPU 內部，速度最快，容量最小。用於存放 CPU 正在處理的資料和指令。
2. 快取記憶體 (Cache)：位於 CPU 和主記憶體之間，速度比主記憶體快，但比暫存器慢。

本題考驗計算機系統中訊號處理與資源分配的技術。
我們逐一分析選項：
(A) Multiplexing (多工)：這是一種將多個獨立的訊號或資料流合併成一個單一的、共用的傳輸通道的技術。在通訊領域，它允許在同一條線上同時傳輸多個訊號。在計算機硬體中，例如匯流排上的多工，也是將多個裝置的資訊傳輸請求合併。這與題目描述「consolidate multiple signals into a single composite signal」非常符合。

(B) Pipelining (流水線)：這是一種處理器設計技術，將複雜的指令執行過程分解成一系列較小的、獨立的步驟（階段），並讓這些階段可以並行執行。

本題考驗非先佔式最短作業優先 (Non-preemptive Shortest Job First, SJF) 的排程演算法，以及平均等待時間的計算。

SJF 演算法的規則是：當 CPU 空閒時，從就緒佇列中選擇預計執行時間（Burst Time）最短的那個行程來執行。在非先佔式 SJF 中，一旦行程開始執行，它就會一直執行到完成，不會被中斷。

我們來模擬 SJF 排程的執行過程：

• 時間 0: P1 到達，就緒佇列中有 P1。CPU 空閒，選擇 P1 執行。
• 時間 1: P2 到達，就緒佇列中有 P2。P1 正在執行。
• 時間 2: P3 到達，就緒佇列中有 P2 和 P3。P1 仍在執行。
• 時間 8: P1 完成。此時就緒佇列中有 P2 (Burst Time 5) 和 P3 (Burst Time 2)。
  SJF 規則：選擇 Burst Time 最短的行程。P3 的 Burst Time 是 2，P2 的 Burst Time 是 5。因此，選擇 P3 執行。
• 時間 10: P3 完成 (從時間 8 開始執行，執行 2 個時間單位)。此時就緒佇列中只剩下 P2。選擇 P2 執行。
• 時間 15: P2 完成 (從時間 10 開始執行，執行 5 個時間單位)。所有行程都已完成。

本題考驗平均週轉時間 (Average Turnaround Time) 的計算，延續上一題的排程結果。
週轉時間 (Turnaround Time) 是指一個行程從到達系統到執行完畢所花費的總時間。
Turnaround Time = Completion Time - Arrival Time

我們需要先計算每個行程的完成時間 (Completion Time)。
從上一題的模擬過程可知：

• P1 完成時間：8
• P3 完成時間：10
• P2 完成時間：15

接著計算每個行程的週轉時間：

• P1:
  • Arrival Time = 0
  • Completion Time = 8
  • Turnaround Time (P1) = 8 - 0 = 8

本題考驗 RAID (Redundant Array of Independent Disks) 磁碟陣列的空間效率。空間效率是指在儲存資料的同時，有多少比例的儲存空間被用於容錯（如備援資料）。

我們逐一分析各個 RAID 等級的空間效率：

• RAID 0 (Striping): 數據被分散儲存在多個磁碟上，沒有任何備援。

  • 優點：讀寫效能高，可用空間最大。
  • 空間效率：100% (所有磁碟空間都用於儲存資料)。
  • 缺點：沒有容錯能力，任何一個磁碟損壞，所有資料都會遺失。

• RAID 1 (Mirroring): 每個磁碟上的資料都會被複製到另一個磁碟上，形成鏡像。

  • 優點：容錯能力高 (一個磁碟損壞，另一個磁碟上的資料仍可用)。讀取效能可能提升。
  • 空間效率：50% (一半的空間用於備援)。若使用 N 顆磁碟，實際可用空間約為 N/2 顆磁碟的大小。

• RAID 3 (Striping with Parity): 數據分散儲存在 N-1 顆磁碟上，而第 N 顆磁碟用於儲存奇偶校驗 (Parity) 資訊。奇偶校驗資訊可以重建損壞磁碟上的資料。

  • 優點：提供容錯能力。
  • 空間效率：$(N-1)/N \times 100\%$。

本題考驗作業系統中行程調度與時間管理相關的事件。

當作業系統的調度器 (dispatcher) 分配一個時間片 (time slice) 給一個行程時，它會啟動一個硬體計時器 (timer circuit)。當這個計時器到達預設的時間片長度時，它會產生一個訊號，通知 CPU 或作業系統時間片已經用完。這個訊號的目的是為了讓作業系統能夠收回 CPU 的使用權，並將 CPU 分配給下一個就緒的行程，以實現多工處理。

這個由硬體計時器產生的、通知 CPU 發生某事件（如時間片用完、I/O 完成等）的訊號，在作業系統中通常稱為中斷 (interrupt)。

本題考驗 IPv4 位址分級系統中，Class B 網路的位址數量。

IPv4 位址是一個 32 位元的二進位數字，通常表示為四個十進位數字，每個數字代表一個位元組 (8 位元)，中間用點分隔。例如：192.168.1.1。

IPv4 位址根據其第一個位元組的值被劃分為不同的類別 (Class A, B, C, D, E)。

• Class A: 第一個位元組為 1-126。網路位址佔 8 位元，主機位址佔 24 位元。
• Class B: 第一個位元組為 128-191。網路位址佔 16 位元，主機位址佔 16 位元。
• Class C: 第一個位元組為 192-223。網路位址佔 24 位元，主機位址佔 8 位元。
• Class D 用於多點傳播 (multicast)。
• Class E 用於實驗。

題目問的是 Class B 網路的 IP 位址數量。
Class B 網路的位址格式是：NNNNNNNN.NNNNNNNN.HHHHHHHH.HHHHHHHH，其中 N 代表網路位址 (Network Address)，H 代表主機位址 (

核心觀念
本題測驗的是「局域網 (LAN) 之傳輸媒介與設備」的概念，特別是 兩個同類型的匯流排 (bus) 網路之間的連接方式。必須了解以下定義：

• 匯流排 (Bus) 網路：所有節點共享同一條傳輸線，訊號以電壓或光脈衝在整條線路上同時傳送。常見範例為早期的 10BASE‑2 (Thin Ethernet)、10BASE‑5 (Thick Ethernet)。
• 中繼器 (Repeater)：在同種傳輸媒介之間放大或重建訊號，延伸傳輸距離，不改變訊號的類型。對匯流排而言，可將兩段匯流排直接相連，使訊號延伸。
• 交換器 (Switch)：在 乙太網路 (Ethernet) 中屬於 多埠橋接 (bridge) 裝置，將 MAC 位址 作為依據進行帧轉發。交換器的介面多為 星型拓撲，每一埠連接單一節點或另一個交換器。
• 無線存取點 (Access Point, AP)：將有線以太網路轉換為 無線 (Wi‑Fi)，提供無線客戶端連接。其功能屬於 第 2 層 (資料鏈結層)，不直接連接兩條有線匯流排。

解題方法
判斷每個選項的功能是否能「連接兩條匯流排」：

1. 判斷裝置類型：若裝置能接受同樣的物理層信號（同樣的匯流排規格）且僅做訊號放大/重建，則可直接用於連接兩條匯流排。
2. 檢視協定層級：若裝置在第 2 層或更高層提供橋接、路由或無線轉換功能，則它的介面通常是 星形或點對點，不適合作為純粹的匯流排延伸。
3. 排除不相容的介面：交換器與 AP 均使用 星型(多埠) 或 無線 介面，需額外的橋接或路由才能連接兩條匯流排，故不直接符合題意。

選項分析

本題考驗網頁瀏覽與伺服器之間傳遞資訊的機制。

題目描述的現象是：網站傳送一小塊資料，由使用者的網頁瀏覽器儲存在使用者電腦上，目的是為了記住狀態資訊（stateful information）。這種機制常見於網站追蹤使用者行為、記住登入狀態、購物車內容等。

我們來分析各選項：
(A) Etag (Entity Tag)：Etag 是一種 HTTP 回應標頭，用於驗證快取資源。伺服器會為每個資源產生一個唯一的 Etag，當瀏覽器再次請求該資源時，會將 Etag 傳送給伺服器，伺服器根據 Etag 判斷資源是否已變更，從而決定是返回新資源還是告知瀏覽器使用快取。Etag 屬於 HTTP 協定的一部分，用於快取驗證，而不是用於儲存使用者狀態資訊。

本題考驗網路協定層級的知識，特別是應用層協定。LINE 是一個即時通訊應用程式，其核心功能是語音和視訊通話，以及文字訊息傳遞。

我們來分析各選項：
(A) HTTP (Hypertext Transfer Protocol)：HTTP 是用於傳輸網頁內容的應用層協定，是 World Wide Web 的基礎。雖然 LINE 的某些功能（例如傳送圖片、檔案）可能透過 HTTP 或類似的協定進行，但其核心的即時通訊和語音/視訊傳輸並非主要依賴 HTTP。

(B) SMTP (Simple Mail Transfer Protocol)：SMTP 是用於傳送電子郵件的應用層協定。LINE 並非電子郵件服務。

(C) SNMP (Simple Network Management Protocol)：SNMP 是用於網路設備管理和監控的應用層協定。它與 LINE 的通訊功能無關。

核心觀念

• Polynomially bounded（多項式上界）指函式 $f(n)$ 在足夠大的 $n$ 時，存在常數 $k>0$ 與常數 $c>0$ 使

$f(n)\le c\cdot n^{\,k}\quad(\forall n\ge n_{0})$

也就是 $f(n)=O(n^{k})$。

• 多項式函式本身（如 $n^{2}$）必然滿足此條件；
• 對數函式 $\log n$ 雖不是多項式，但因為 $\log n = O(n^{k})$（任意正整數 $k$ 都成立），仍屬於「多項式上界」的類別。
• 指數函式 $2^{n}$ 的增長速度遠快於任何多項式，無法被任何 $n^{k}$ 上界。

解題方法

1. 先確認每個選項的漸進增長階層。
2. 判斷其是否能被某個 $n^{k}$（$k$ 為常數）所上界。
3. 若能則屬於 polynomially bounded，若不能則不屬。

選項分析

本題考驗快速排序 (Quick Sort) 的時間複雜度，特別是其最壞情況下的時間複雜度。

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

1. 選擇一個基準元素 (pivot)：從數列中選擇一個元素作為基準。
2. 分割 (Partition)：重新排列數列，使得所有小於基準的元素都排在基準前面，所有大於基準的元素都排在基準後面。這個分割操作會將基準元素放到其最終的排序位置。
3. 遞迴 (Recurse)：遞迴地對基準元素前後的兩個子數列進行快速排序。

平均時間複雜度:
在理想情況下，每次分割都能將數列均勻地分成兩個大小大致相等的子數列。此時，遞迴關係式為 $T(n) = 2T(n/2) + O(n)$，其時間複雜度為 $O(n\log n)$。

最壞時間複雜度:
快速排序的最壞情況發生在每次分割都產生極端不平衡的子數列時。例如：

• 當數列已經是排序好的（或逆序的），並且每次都選擇第一個或最後一個元素作為基準。

本題考驗插入排序 (Insertion Sort) 的平均時間複雜度。

插入排序是一種簡單的排序演算法，其工作方式類似於整理撲克牌。它將數列分成已排序部分和未排序部分。每次從未排序部分取出一個元素，並將其插入到已排序部分的正確位置。

演算法步驟:

1. 將數列的第一個元素視為已排序部分。
2. 從第二個元素開始，逐一取出未排序部分的元素。
3. 將取出的元素與已排序部分的元素從後往前比較，找到其正確的插入位置。
4. 將該元素插入到正確位置，並將後面的元素向後移動。
5. 重複步驟 2-4，直到所有元素都插入到已排序部分。

時間複雜度分析:

• 最佳情況: 當輸入數列已經是排序好的時候。此時，對於每個元素，只需要與已排序部分的最後一個元素比較一次，然後插入。總共需要進行 $n-1$ 次比較和 $n-1$ 次移動。時間複雜度為 $O(n)$。

本題考驗 C++ 程式碼的執行與輸出結果。程式碼計算了從 1 加到 8 的總和。

程式碼解析：

1. sum=0;: 初始化一個整數變數 sum 為 0。
2. for(int i=1; i<=8; ++i): 這是一個 for 迴圈，初始化變數 i 為 1。迴圈的條件是 i <= 8，也就是當 i 小於或等於 8 時，迴圈會繼續執行。每次迴圈結束後，i 的值會增加 1 (++i)。
3. sum+=i;: 在迴圈的每一次迭代中，將當前 i 的值加到 sum 變數中。
4. cout << sum << endl;: 迴圈結束後，將 sum 的最終值輸出到標準輸出，並換行。

迴圈執行的過程如下：

• i = 1: sum = 0 + 1 = 1
• i = 2: sum = 1 + 2 = 3
• i = 3: sum = 3 + 3 = 6
• i = 4: sum = 6 + 4 = 10

本題考驗 C++ 程式碼的執行邏輯，特別是陣列初始化、迴圈以及 continue 語句的用法。

程式碼解析：

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

2. for(int i=0; i<10; ++i) arr[i]=0;: 這個迴圈將陣列 arr 的所有元素初始化為 0。

   • arr[0] = 0
   • arr[1] = 0
   • ...
   • arr[9] = 0

3. for(int i=0; i<10; ++i): 這是第二個 for 迴圈，也遍歷陣列的索引 0 到 9。

4. if (i==5) continue;: 在這個迴圈內部，有一個條件判斷。如果 i 的值等於 5，則執行 continue 語句。

   • continue 語句的作用是立即終止當前這次迴圈的迭代，並跳到下一次迭代的開始（即執行 ++i）。
   • 因此，當 i 等於 5 時，continue 會被執行，這意味著 arr[i]=i*i; 這一行程式碼在 i=5 的時候不會被執行。

5. arr[i]=i*i;: 在迴圈的每次迭代中，如果 continue 沒有被執行，則將 i 的平方賦值給 arr[i]。

讓我們追蹤迴圈的執行過程，特別是 arr[5] 的值：

核心觀念

• 迴圈 (for loop)：for(int i=0; i<10; ++i) 逐次將 i 從 0 增至 9。
• 陣列索引：arr[i] = i*i 把每個索引的值設定為 i 的平方。
• 模運算 (%)：i % 3 == 1 判斷 i 除以 3 的餘數是否為 1，等同於「i ≡ 1 (mod 3)」。
• 迴圈提前結束 (break)：if(i==5) break; 當 i 等於 5 時立即跳出迴圈。

解題方法

1. 先完成陣列初始化：
   $\text{arr}[i] = i^2,\quad i=0,1,\dots,9$
   得到陣列內容
   $[0,1,4,9,16,25,36,49,64,81]$
2. 在同一個迴圈內檢查兩個條件（程式題目實務上會加上大括號，使 if 皆屬於迴圈內）：
   • 條件一：i % 3 == 1 時輸出 arr[i]，即當 i = 1,4,7,…。
   • 條件二：i == 5 時執行 break，迴圈於 i = 5 前結束。
3. 逐次執行迴圈（直到 break）：

本題考驗物件導向程式設計 (Object-Oriented Programming, OOP) 的基本概念，特別是類別之間的關係。

題目描述的是一個類別 (class) 能夠「包含 (encompass)」另一個類別的屬性 (properties) 的能力。這通常意味著新類別可以繼承或包含現有類別的特徵。

我們來分析各個選項：
(A) Encapsulation (封裝)：封裝是指將資料（屬性）和操作這些資料的方法（行為）綁定在一起，形成一個獨立的單元（物件）。它也涉及資訊隱藏，即將內部實現細節對外部隱藏。封裝本身不是指一個類別包含另一個類別的屬性，而是將一個類別的成員組織在一起。

(B) Polymorphism (多型)：多型是指「多種形態」。在 OOP 中，它允許不同的物件對相同的訊息做出不同的響應。例如，一個父類別的指標可以指向子類別的物件，並通過虛函數調用子類別的方法。多型強調的是行為的靈活性，而不是一個類別包含另一個類別的屬性。

本題考驗函數參數傳遞的兩種主要方式：傳值 (call by value) 和傳址 (call by reference)，以及相關概念。

當一個函數被呼叫時，它需要接收來自呼叫者 (calling program unit) 的參數。參數傳遞的方式決定了函數內部如何存取和修改這些參數。

(A) Call by value (傳值)：
在傳值呼叫中，函數接收的是參數值的「副本」。當參數被傳遞給函數時，呼叫者傳遞的是變數的值。函數內部對這些參數的任何修改，都只會影響到函數內的副本，而不會影響到呼叫者中的原始變數。
例如：

void func(int x) {
  x = x + 10; // 這裡修改的是 x 的副本
}
int main() {
  int a = 5;
  func(a); // 傳遞 a 的值 5
  // a 的值仍然是 5
  return 0;
}

(B) Call by reference (傳址 / 傳引用)：
在傳址呼叫（或傳引用呼叫，取決於語言的具體實現，例如 C++ 的引用或 C 的指標）中，函數接收的是參數的「記憶體位址」。這意味著函數內部可以直接存取和修改呼叫者中的原始變數。
例如 (使用 C++ 引用)：

void func(int& x) { // 這裡 x 是對原始變數的引用
  x = x + 10; // 這裡修改的是原始變數
}
int main() {
  int a = 5;
  func(a); // 傳遞 a 的引用
  // a 的值變為 15
  return 0;
}

或者使用 C 風格的指標：

本題考驗程式開發過程中可能出現的錯誤類型。

題目問的是「在程式執行過程中發生的問題」。

我們來分析各選項：
(A) Compile error (編譯錯誤)：編譯錯誤發生在程式編譯階段（將原始碼轉換為機器碼的過程）。這些錯誤通常是由於程式碼不符合編譯器的語法規則或語義規則造成的，例如拼寫錯誤、缺少分號、類型不匹配等。編譯器在發現這些錯誤時，會停止編譯並報告錯誤訊息。編譯錯誤發生在程式「執行前」。

(B) Syntax error (語法錯誤)：語法錯誤是編譯錯誤的一種。它指程式碼違反了程式語言的語法規則。例如，缺少括號、關鍵字拼寫錯誤等。語法錯誤同樣發生在編譯階段，在程式執行前。

本題考驗遞迴關係式的求解，這是一個典型的分治演算法的時間複雜度分析。

給定的遞迴關係式為：
$T(n) = 2T(n/2) + 1$
基本情況：$T(0)=0$, $T(1)=1$

我們可以使用遞迴樹法 (Recursion Tree Method) 或主定理 (Master Theorem) 來求解。

方法一：遞迴樹法
想像一個遞迴樹，根節點代表 $T(n)$。

• 第一層 (根節點)：成本為 1。有 1 個節點。
• 第二層：有 2 個節點，每個節點代表 $T(n/2)$。每個節點的成本是 1。總成本是 $2 \times 1 = 2$。
• 第三層：有 4 個節點，每個節點代表 $T(n/4)$。每個節點的成本是 1。總成本是 $4 \times 1 = 4$。
• 第 $k$ 層：有 $2^{k-1}$ 個節點，每個節點代表 $T(n/2^{k-1})$。每個節點的成本是 1。總成本是 $2^{k-1} \times 1 = 2^{k-1}$。

樹的深度是多少？
當問題規模縮小到基本情況時，遞迴停止。假設 $n$ 是 2 的冪次方，$n = 2^h$，則 $h = \log_2 n$。
當 $n/2^{k-1} = 1$ 時，遞迴停止。
$n = 2^{k-1}$
$\log_2 n = k-1$
$k = \log_2 n + 1$。
所以樹的高度大約是 $\log_2 n$。

總成本是所有層級成本的總和：
$T(n) = \sum_{k=1}^{\log_2 n} 2^{k-1} \times 1$ (假設成本是 1，因為 $2T(n/2)+1$ 中的 $+1$ 是常數成本)
這是一個等比級數：$1 + 2 + 4 + ... + 2^{\log_2 n - 1}$。
這個級數的和是 $\frac{2^{\log_2 n} - 1}{2-1} = 2^{\log_2 n} - 1 = n - 1$。

所以，$T(n) = n - 1$。
其漸進複雜度是 $O(n)$ 或 $\Theta(n)$。

本題考驗遞迴關係式的求解，同樣使用主定理 (Master Theorem)。

給定的遞迴關係式為：
$T(n) = 2T(n/2) + \log n$
基本情況：$T(0)=0$, $T(1)=1$

我們使用主定理，形式為 $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$。

主定理的比較：

1. 如果 $f(n) = O(n^{\log_b a - \epsilon})$ 對某個 $\epsilon > 0$，則 $T(n) = \Theta(n^{\log_b a})$。
   在這裡，$f(n) = \log n$。$n^{\log_b a} = n$。
   $\log n$ 的成長速度比 $n$ 慢得多。
   我們可以找到一個 $\epsilon > 0$ (例如 $\epsilon = 0.5$)，使得 $\log n = O(n^{1-0.5}) = O(n^{0.5})$。
   所以，適用主定理的第一種情況。
   $T(n) = \Theta(n^{\log_b a}) = \Theta(n^1) = \Theta(n)$。

2. 如果 $f(n) = \Theta(n^{\log_b a})$，則 $T(n) = \Theta(n^{\log_b a} \log n)$。

本題考驗對不同函數複雜度成長率的比較。我們要找出其中成長最慢（即複雜度最低）的函數。

我們需要比較四個選項的複雜度：
(A) $100!$：這是一個常數。即使 $100!$ 是一個非常大的數字，它相對於變數 $n$ 來說，是一個固定值，不隨 $n$ 的變化而變化。因此，其複雜度是 $O(1)$。

(B) $2^{\log n}$：
根據指數與對數的性質，$a^{\log_b c} = c^{\log_b a}$。
所以，$2^{\log n} = n^{\log_2 2} = n^1 = n$。
因此，$2^{\log n}$ 的複雜度是 $O(n)$。

核心觀念

• Binary Search Tree（BST）之 中序(inorder) 產生遞增序列。
• 後序(postorder)：左子樹 → 右子樹 → 根節點。
• 先序(preorder)：根節點 → 左子樹 → 右子樹。
• 已知 inorder 與 postorder，可唯一還原原樹，進而得到 preorder。

解題方法

1. 找根節點：postorder 的最後一個元素必為整棵樹的根。
   $\text{根}=9$

2. 切分 inorder：在 inorder 中以根 $9$ 為分界，左側為左子樹的 inorder，右側為右子樹的 inorder。

   • 左子樹 inorder：$1,3,5,7$
   • 右子樹 inorder：$11,13$

3. 切分 postorder：根已去除，剩餘序列依左、右子樹的節點數量分割。

   • 左子樹節點數 = $|1,3,5,7|=4$ → 左子樹 postorder 為前 4 個：$1,5,3,7$
   • 右子樹 postorder 為剩下的：$13,11$

4. 遞迴還原左子樹

   • 根 = 左子樹 postorder 最後一個 $7$。
   • inorder 於 $7$ 切分：左 $1,3,5$、右 $∅$。
   • 左子樹 postorder：$1,5,3$（3 個），右子樹 postorder：$∅$。
   • 再遞迴左子樹
     • 根 = $3$（postorder 最後）， inorder 切分：左 $1$、右 $5$。
     • 左子樹 postorder = $1$，右子樹 postorder = $5$。
     • 因皆為單節點，左子樹為 $1$，右子樹為 $5$。
   • 合併得到左子樹的 preorder：$\boxed{7,3,1,5}$。

核心觀念

• 二元樹 (binary tree)：每個節點最多有兩個子節點。
• 節點的 degree：指子節點的個數，亦即「出度」。
• 樹的基本性質：在一棵有 $N$ 個節點的樹中，邊的數目恆為 $N-1$。
• 度數與邊的關係：若把所有節點的 degree 加總，得到的總和即為樹的邊數。

解題方法
設

• $n_0$：度數為 $0$ 的節點（葉子）
• $n_1$：度數為 $1$ 的節點（題目已給 $3$）
• $n_2$：度數為 $2$ 的節點

1. 節點總數

2. 邊的總數（同時等於所有 degree 的總和）

3. 從 (2) 求 $n_2$：
   $n_1 + 2n_2 = 15 \;\Longrightarrow\; n_2 = \frac{15 - n_1}{2} = \frac{15-3}{2}=6$

4. 代入 (1) 計算 $n_0$：
   $n_0 = 16 - n_1 - n_2 = 16 - 3 - 6 = 7$

5. 也可直接使用推導的通用公式
   $n_0 = \frac{N - n_1 + 1}{2}$
   代入 $N=16,\;n_1=3$ 得

本題考驗關聯式資料庫 (Relational Database) 的基本術語。

關聯式資料庫的基本結構是一個「關聯 (Relation)」，它通常以表格 (Table) 的形式呈現。
一個關聯 (Relation) 由以下幾個部分組成：

• Schema (綱目)：定義了關聯的結構，包括欄位名稱和資料型別。
• Rows (列 / 記錄 / 資料元組)：代表關聯中的一筆資料記錄。每一列的數據對應於關聯中的一個實體。
• Columns (欄)：代表關聯中的一個屬性或欄位。每一欄儲存了某種類型的資料，並且在每一列中都有一個值。

題目問的是「a column in a relation is called ____」。
我們來分析各選項：

本題考驗關聯式代數 (Relational Algebra) 的基本操作，特別是從關聯（表格）中提取欄位（屬性）的操作。

在關聯式代數中，有幾個基本的操作符號，用於從一個或多個關聯中查詢和操作資料。

我們來分析各選項：
(A) SELECT (選擇)：SELECT 操作用於從一個關聯中選擇滿足特定條件的「列 (Rows / Tuples)」。它過濾數據，但保留所有欄位。例如，選擇所有學生成績大於 90 的記錄。

本題考驗對常見軟體及其用途的認識，特別是辨識哪些不是動畫軟體。

我們來分析各選項：
(A) 3ds Max: Autodesk 3ds Max 是一款非常著名的 3D 電腦圖形軟體，廣泛用於製作 3D 模型、動畫、視覺特效和遊戲開發。它絕對是動畫軟體。

(B) TensorFlow: TensorFlow 是由 Google 開發的一個開源機器學習框架。它主要用於構建和訓練神經網路模型，進行數據分析、預測等機器學習任務。

本題考驗對深度學習模型類型的認識，特別是循環神經網路 (Recurrent Neural Network, RNN) 的變體。

我們來分析各選項：
(A) LSTM (Long Short-Term Memory)：LSTM 是一種特殊的循環神經網路 (RNN) 架構，它被設計來解決傳統 RNN 在處理長序列時遇到的梯度消失 (vanishing gradient) 或梯度爆炸 (exploding gradient) 問題。LSTM 能夠有效地學習長距離的依賴關係，因此廣泛應用於自然語言處理、語音識別、時間序列分析等領域。LSTM 是一種 RNN 模型。

(B) VGG16: VGG16 是一個深度卷積神經網路 (Convolutional Neural Network, CNN) 模型，由牛津大學視覺幾何團隊 (Visual Geometry Group) 在 ImageNet 圖像識別挑戰賽中提出。它以其簡單而深的架構（16 層）聞名，主要用於圖像識別和分類任務。

核心觀念

強化學習讓智能體根據環境狀態選擇動作，並依據獎勵調整策略。深度強化學習以神經網路表示價值函數或策略；DQN、DDPG、PPO 都是強化學習演算法。

GRU（門控循環單元）則是一種循環神經網路架構，常用來處理文字、語音等序列資料。它本身是神經網路的組件，不是強化學習演算法；不過，GRU 可以用來建構強化學習智能體的網路。

解題方法

辨認各選項的類別：若名稱代表強化學習演算法，便不符合題幹「不是用於強化學習」；若代表一般神經網路架構，則符合題意。因此答案是 GRU。

選項分析

本題考驗對機器學習 (Machine Learning, ML) 主要分支的分類。

機器學習的主要分支通常包括：

1. 監督式學習 (Supervised Learning)：模型從帶有標籤的數據中學習，目標是預測輸入的輸出。常見演算法有線性迴歸、邏輯迴歸、支持向量機 (SVM)、決策樹、神經網路等。
2. 非監督式學習 (Unsupervised Learning)：模型從沒有標籤的數據中學習，目標是發現數據中的結構或模式。常見演算法有聚類 (Clustering，如 K-Means)、降維 (Dimensionality Reduction，如 PCA)、關聯規則挖掘等。
3. 強化學習 (Reinforcement Learning, RL)：模型（稱為 Agent）通過與環境互動來學習，目標是最大化累積獎勵。Agent 在環境中採取動作，接收獎勵或懲罰，並根據這些反饋來調整其策略。常見演算法有 Q-learning、SARSA、Policy Gradient、DQN、PPO 等。

本題考驗可計算性理論 (Computability Theory) 中的概念，特別是可計算問題 (Computable Problem) 與不可計算問題 (Non-computable Problem)。

一個問題被稱為「可計算的」，如果存在一個演算法（圖靈機）可以在有限的時間內解決它的所有實例。
一個問題被稱為「不可計算的」，如果不存在這樣的演算法。

我們來分析各選項：
(A) Traveling Salesman Problem (TSP, 旅行商問題)：TSP 是指找到訪問一系列城市並返回起點的最短路徑。TSP 是一個 NP-hard 問題，但它是可計算的。存在演算法（例如動態規劃、近似演算法，甚至暴力搜索）可以在有限時間內找到近似解或精確解（對於小規模問題）。其複雜度很高，但不是不可計算。

本題考驗計算複雜性理論中 NP-complete 問題的定義和例子。

首先，我們需要理解 NP-complete 的概念：

• NP (Non-deterministic Polynomial time)：指可以在非確定性圖靈機上於多項式時間內解決的問題類別。
• P (Polynomial time)：指可以在確定性圖靈機上於多項式時間內解決的問題類別。
• NP-hard: 指一個問題的難度不低於 NP 中的任何問題。如果一個問題是 NP-hard，那麼任何 NP 問題都可以轉換 (reduce) 到它，並在多項式時間內解決。
• NP-complete (NPC)：指一個問題既屬於 NP，又是 NP-hard。NP-complete 問題是 NP 中「最難」的問題。如果一個 NP-complete 問題能夠在多項式時間內解決，那麼 P = NP。

我們來分析各選項：
(A) Depth-first-search (DFS, 深層優先搜尋)：DFS 是一種圖遍歷演算法，用於遍歷圖或樹結構。對於一個有 $V$ 個頂點和 $E$ 條邊的圖，DFS 的時間複雜度是 $O(V+E)$，這是一個多項式時間複雜度。因此，DFS 問題（即執行 DFS）屬於 P 類問題，不是 NP-complete。

本題考驗對 NP-complete 問題的辨識，要求選出一個「不是」NP-complete 的問題。

我們逐一分析選項：
(A) All-Pairs Shortest Path Problem (APSP, 所有點對最短路徑問題)：如前一題所述，對於邊權為非負的圖，APSP 問題有高效的多項式時間演算法（如 Floyd-Warshall, $O(V^3)$）。因此，APSP 問題屬於 P 類問題，不是 NP-complete。

(B) 0/1 Knapsack Problem (0/1 背包問題)：如前一題所述，0/1 背包問題是一個經典的 NP-complete 問題。

本題考驗不同進位制之間的轉換。題目要求將十六進位數 $(6F)_{16}$ 轉換為八進位和十進位。

步驟 1: 將十六進位數 $(6F)_{16}$ 轉換為十進位數
十六進位數的位值是 16 的冪次方。
$(6F)_{16} = 6 \times 16^1 + F \times 16^0$
其中，F 在十六進位中代表十進位的 15。
$(6F)_{16} = 6 \times 16 + 15 \times 1$
$(6F)_{16} = 96 + 15$
$(6F)_{16} = 111_{10}$

本題考驗 C/C++ 程式語言的 do-while 迴圈用法，以及計算連續整數乘積的方法。

題目要求使用 do-while 迴圈來計算從 1 到 10 的整數乘積。
乘積的計算是 $1 \times 2 \times 3 \times \dots \times 10$。

do-while 迴圈的結構是：

do {
  // 迴圈體
  // 至少執行一次
} while (condition);

我們需要初始化一個變數來儲存乘積，初始值應為 1 (乘法的單位元素)。
同時，我們需要一個變數來迭代從 1 到 10。

程式碼範例如下：

#include <iostream>

int main() {
    long long product = 1; // 使用 long long 以避免整數溢位，因為 10! 較大
    int i = 1;

    do {
        product *= i; // 將當前 i 的值乘到 product 中
        i++;          // 遞增 i
    } while (i <= 10); // 當 i 小於等於 10 時，繼續迴圈

    std::cout << "The product of integers from 1 to 10 is: " << product << std::endl;

    return 0;
}

程式碼解釋:

1. long long product = 1;: 初始化一個 long long 型別的變數 product 為 1。使用 long long 是因為 10! (10 的階乘) 是 $3,628,800$，這可能會超過標準 int 型別的範圍。
2. int i = 1;: 初始化一個整數變數 i 為 1，作為計數器。
3. do { ... } while (i <= 10);: 這是一個 do-while 迴圈。
   • 迴圈體內的 product *= i; 將 product 的當前值與 i 的值相乘，並將結果存回 product。
   • i++; 將 i 的值加 1。

本題考驗插入排序 (Insertion Sort) 的執行過程，並要求寫出每一步迭代的結果。

插入排序的步驟是：將數列分成已排序和未排序兩部分，然後從未排序部分依次取出元素，插入到已排序部分的正確位置。

給定數據：6, 5, 2, 3, 4, 1

迭代 1：處理第一個元素 (6)

• 已排序部分：[6]
• 未排序部分：[5, 2, 3, 4, 1]
• (此時，數列可以看作是 [6])

迭代 2：處理第二個元素 (5)

• 取出 5。
• 將 5 與已排序部分的元素 (6) 比較。5 < 6，所以 6 需要後移。
• 將 5 插入到 6 的前面。
• 已排序部分：[5, 6]
• 數列狀態：[5, 6, 2, 3, 4, 1]

迭代 3：處理第三個元素 (2)

• 取出 2。
• 將 2 與已排序部分的元素 (6, 5) 比較。
• 2 < 6，6 後移。數列變為 [5, 6, 2]。
• 2 < 5，5 後移。數列變為 [2, 5, 6]。
• 將 2 插入到最前面。
• 已排序部分：[2, 5, 6]
• 數列狀態：[2, 5, 6, 3, 4, 1]

迭代 4：處理第四個元素 (3)

• 取出 3。
• 將 3 與已排序部分的元素 (6, 5, 2) 比較。
• 3 < 6，6 後移。數列變為 [2, 5, 6, 3]。
• 3 < 5，5 後移。數列變為 [2, 3, 5, 6]。
• 3 > 2，停止比較。將 3 插入到 2 的後面。
• 已排序部分：[2, 3, 5, 6]
• 數列狀態：[2, 3, 5, 6, 4, 1]

迭代 5：處理第五個元素 (4)

• 取出 4。
• 將 4 與已排序部分的元素 (6, 5, 3, 2) 比較。
• 4 < 6，6 後移。數列變為 [2, 3, 5, 6, 4]。
• 4 < 5，5 後移。數列變為 [2, 3, 4, 5, 6]。
• 4 > 3，停止比較。將 4 插入到 3 的後面。
• 已排序部分：[2, 3, 4, 5, 6]
• 數列狀態：[2, 3, 4, 5, 6, 1]

本題考驗二元樹的高度 (height) 與節點數 (number of nodes) 之間的關係。

二元樹的高度定義為：

• 空樹的高度為 -1。
• 只有一個節點（根節點）的樹的高度為 0。
• 對於非空樹，其高度是其所有葉節點到根節點路徑中的最大長度（邊數）。也定義為根節點到最深葉節點的層數減 1。

最小高度 (Minimal Height):
為了使二元樹的高度最小，樹應該盡可能「滿」或「平衡」。
一個高度為 $h$ 的滿二元樹，其節點數為 $2^{h+1}-1$。
反過來，一個具有 $N$ 個節點的二元樹，其最小高度 $h_{min}$ 滿足：
$2^{h_{min}+1}-1 \ge N$
$2^{h_{min}+1} \ge N+1$
$h_{min}+1 \ge \log_2(N+1)$
$h_{min} \ge \log_2(N+1) - 1$
最小高度 $h_{min} = \lfloor \log_2 N \rfloor$。

對於 $N=32$：
$h_{min} = \lfloor \log_2 32 \rfloor = \lfloor 5 \rfloor = 5$。
注意: 這裡的高度定義是以節點數來計算。如果高度是以邊數定義，則滿二元樹節點數為 $2^{h+1}-1$，最小高度 $h_{min} = \lfloor \log_2 N \rfloor$。
如果高度是以層數定義 (根為第 1 層)，則高度為 $\lceil \log_2(N+1) \rceil$。
如果高度是以邊數定義 (根到最深葉節點的邊數)，則高度為 $\lfloor \log_2 N \rfloor$。

通常，樹的高度是以邊數定義，即根到最深葉節點的最長路徑上的邊數。

• 單節點樹：高度 0。
• 節點數 2 或 3：高度 1。
• 節點數 4 到 7：高度 2。
• 節點數 8 到 15：高度 3。
• 節點數 16 到 31：高度 4。

對於 $N=32$ 個節點：
要使高度最小，樹應該盡可能平衡。
如果高度是 $h$，則節點數 $N$ 滿足 $2^h \le N \le 2^{h+1}-1$ (如果根節點層數為 0)。
或者 $2^{h+1}-1 \ge N$ (如果滿二元樹的節點數)。

本題考驗對人工智慧 (Artificial Intelligence, AI)、機器學習 (Machine Learning, ML) 和深度學習 (Deep Learning, DL) 這三個概念之間關係的理解。

這三者之間的關係通常被描述為一個嵌套結構，其中 AI 是最大的範疇，ML 是 AI 的一個子集，而 DL 則是 ML 的一個子集。

1. 人工智慧 (Artificial Intelligence, AI):

   • AI 是最廣泛的概念。它的目標是創造能夠模擬人類智慧的系統，使機器能夠執行通常需要人類智慧的任務，例如學習、解決問題、感知、理解語言、做決策等。
   • AI 是一個非常廣泛的領域，涵蓋了許多不同的方法和技術，包括邏輯推理、知識表示、規劃、自然語言處理、機器人學、機器學習等等。

2. 機器學習 (Machine Learning, ML):

   • ML 是 AI 的一個子領域。它專注於開發能夠讓電腦系統從數據中「學習」的演算法，而無需進行明確的程式設計。
   • ML 的核心思想是通過分析數據來識別模式，並利用這些模式來做出預測或決策。
   • ML 提供了讓 AI 系統具備學習能力的技術。例如，透過訓練一個 ML 模型來識別圖片中的貓。

3. 深度學習 (Deep Learning, DL):

   • DL 是 ML 的一個子領域。它使用深度神經網路 (Deep Neural Networks, DNNs)，即具有多個隱藏層的神經網路，來學習數據的表示。