111 年 國立政治大學資訊管理學系碩士班科技組《計算機概論》

本題考查二進位數字轉換為十進位以及位移運算的應用。
首先，將二進位數字 $D = 1011101_2$ 轉換為十進位：
$D = 1 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$

本題考查使用者空間(userspace)與核心空間(kernel space)的溝通機制，特別是系統呼叫(system call)的執行流程。

當一個 userspace 程式需要請求作業系統的服務（例如檔案讀寫、記憶體分配等），它不能直接存取核心資源，必須透過系統呼叫(system call)來完成。系統呼叫的過程如下：

1. 觸發系統呼叫：Userspace 程式執行一個特殊的指令（通常是軟體中斷指令，如 INT 或 SYSCALL），這個指令會觸發一個軟體中斷（Software Interrupt）。
2. 模式切換：CPU 從使用者模式(user mode)切換到核心模式(kernel mode)。

本題考查網路傳輸中的流水線(Pipeline)機制，特別是針對 Go-Back-N 協議的敘述。

流水線(Pipeline)機制：在通訊協定中，流水線機制允許傳送端在收到前一個封包的確認(ACK)之前，就傳送多個封包。這可以提高傳輸效率，減少等待 ACK 的時間。

Go-Back-N (GBN) 協議：

• 在 GBN 協議中，傳送端可以連續傳送多個封包（一個視窗大小為 N 的封包）。
• 接收端只需要按順序接收封包。如果接收到一個封包，它會回傳一個 ACK，表示該封包已成功接收，並且期望下一個封包。

本題考查無線網路標準 802.11ax 的技術特點，特別是 OFDMA 的應用。

802.11ax (Wi-Fi 6)：

• 頻段支援：802.11ax 確實支援 2.4GHz 和 5GHz 頻段，並且是首個支援 6GHz 頻段（Wi-Fi 6E）的標準。
• 核心技術：802.11ax 的一個關鍵創新是引入了正交頻分多址 (Orthogonal Frequency Division Multiple Access, OFDMA)。

OFDMA 與 OFDM 的比較：

• OFDM (Orthogonal Frequency Division Multiplexing)：將一個寬頻通道劃分為多個較窄的子載波，然後將資料分配到這些子載波上進行傳輸。OFDM 主要用於單向的資料傳輸（如基地台到終端）。

核心觀念

θ-join（條件連接）$A \bowtie_{A.N<B.Y} B$：把 A 的每一筆與 B 的每一筆配對，只保留滿足條件的組合。結果筆數＝符合條件的配對數。

原卷的兩個表格

B.Y 的值為 7 與 3。

逐筆比對 $A.N<B.Y$

本題考查 Dijkstra's Algorithm 的時間複雜度和訊息交換量。

Dijkstra's Algorithm：用於尋找帶有非負權重的圖中，從單一源點到所有其他頂點的最短路徑。

時間複雜度：
Dijkstra's Algorithm 的時間複雜度取決於資料結構的選擇。

• 使用鄰接矩陣 (Adjacency Matrix) 和簡單陣列：
  • 每次從集合 S (已找到最短路徑的節點集合) 中選取離源點最近的節點，需要遍歷所有未選取的節點，這需要 $O(N)$ 的時間。
  • 更新鄰近節點的最短路徑，也需要遍歷所有節點，這需要 $O(N)$ 的時間。
  • 這個過程重複 N 次（對於 N 個節點）。
  • 總時間複雜度為 $N \times (O(N) + O(N)) = O(N^2)$。
• 使用鄰接串列 (Adjacency List) 和二元堆 (Binary Heap)：
  • 建立堆：$O(N)$
  • 提取最小值的節點：$N$ 次，每次 $O(\log N)$，總計 $O(N \log N)$。
  • 更新節點的距離 (Decrease Key)：最多 $E$ 次，每次 $O(\log N)$，總計 $O(E \log N)$。
  • 總時間複雜度為 $O(N \log N + E \log N)$。如果圖是稀疏圖 ($E \approx N$)，則為 $O(N \log N)$。如果圖是稠密圖 ($E \approx N^2$)，則為 $O(N^2 \log N)$。
• 使用鄰接串列 (Adjacency List) 和費氏堆 (Fibonacci Heap)：
  • 總時間複雜度為 $O(N \log N + E)$。

本題考查對基本邏輯閘功能的理解。題目沒有具體指出是哪兩個邏輯閘，但從常識和考試的常見邏輯閘來看，我們可以推斷。
題目提到「若輸入皆為0的時候,其輸出皆為0」。這意味著對於輸入為 (0, 0) 的情況，輸出的邏輯值是 0。

我們來檢視常見的邏輯閘：

1. AND 閘 (AND Gate):

   • Truth Table:

     Input A	Input B	Output
     0	0	0
     0	1	0
     1	0	0
     1	1	1

   • 當輸入皆為 0 (0, 0) 時，AND 閘的輸出是 0。

2. OR 閘 (OR Gate):

   • Truth Table:

     Input A	Input B	Output
     0	0	0
     0	1	1
     1	0	1
     1	1	1

   • 當輸入皆為 0 (0, 0) 時，OR 閘的輸出是 0。

3. NAND 閘 (NAND Gate):

   • Truth Table:

     Input A	Input B	Output
     0	0	1
     0	1	1
     1	0	1
     1	1	0

   • 當輸入皆為 0 (0, 0) 時，NAND 閘的輸出是 1。

4. NOR 閘 (NOR Gate):

   • Truth Table:

     Input A	Input B	Output
     0	0	1
     0	1	0
     1	0	0
     1	1	0

   • 當輸入皆為 0 (0, 0) 時，NOR 閘的輸出是 1。

5. XOR 閘 (XOR Gate):

   • Truth Table:

     Input A	Input B	Output

本題考查 IP 位址的分類，特別是私人 IP 位址和 Class A 位址的定義。

IP 位址分類 (Classful Addressing)：
IP 位址最初被劃分為五種類別：Class A, B, C, D, E。

• Class A:
  • 網路位址部分：第一個位元組 (8 位元) 的最高位元固定為 0。
  • 範圍：$0.0.0.0$ 到 $127.255.255.255$。
  • 網路位址：第一個位元組。主機位址：後三個位元組。
  • 可用的網路數量：$2^7 = 128$ 個（但 0.x.x.x 和 127.x.x.x 有特殊用途）。
  • 每個網路可以包含的主機數量：$2^{24}$ 個。
• Class B:
  • 網路位址部分：前兩個位元組。最高兩個位元為 10。
  • 範圍：$128.0.0.0$ 到 $191.255.255.255$。
• Class C:
  • 網路位址部分：前三個位元組。最高三個位元為 110。
  • 範圍：$192.0.0.0$ 到 $223.255.255.255$。
• Class D:
  • 用於多點傳播 (Multicast)。
  • 範圍：$224.0.0.0$ 到 $239.255.255.255$。
• Class E:
  • 保留。
  • 範圍：$240.0.0.0$ 到 $255.255.255.255$。

私人 IP 位址 (Private IP Addresses)：
RFC 1918 定義了一組 IP 位址範圍，這些位址僅供內部網路使用，不能在網際網路上直接路由。

• Class A 範圍：$10.0.0.0$ 到 $10.255.255.255$ (共一個 Class A 網路)。
• Class B 範圍：$172.16.0.0$ 到 $172.31.255.255$ (共 16 個 Class B 網路)。
• Class C 範圍：$192.168.0.0$ 到 $192.168.255.255$ (共 256 個 Class C 網路)。

本題考查網路位址轉換 (NAT) 的服務與動態主機設定協定 (DHCP) 的關係。

NAT (Network Address Translation)：
NAT 是一種將內部網路的私有 IP 位址轉換為外部網路的公共 IP 位址的技術。這使得多個內部設備可以共享一個或一組公共 IP 位址來訪問網際網路。NAT 主要有以下幾種模式：

• Static NAT: 一對一的靜態映射。
• Dynamic NAT: 一個私有 IP 位址映射到一個來自公共 IP 位址池的可用公共 IP 位址。
• PAT (Port Address Translation) 或 NAT Overload: 一個公共 IP 位址可以通過不同的埠號 (Port Number) 來映射多個私有 IP 位址。這是最常見的 NAT 形式，通常用於家庭和小型企業路由器。

DHCP (Dynamic Host Configuration Protocol)：
DHCP 是一種網路協定，用於自動為網路上的設備分配 IP 位址、子網路遮罩、預設閘道、DNS 伺服器位址等網路組態資訊。

NAT 與 DHCP 的關係：
NAT 的核心功能是位址轉換，它需要公共 IP 位址來與外部網路通信。而 DHCP 的核心功能是自動分配 IP 位址。

• **NAT 本身並不直接依賴 DHCP 來運作。

本題考查圖的廣度優先搜尋 (BFS) 演算法，並要求判斷給定的 BFS 順序是否正確。

BFS (Breadth First Search)：
BFS 是一種圖遍歷演算法，它從一個起始節點開始，逐層地訪問節點。它首先訪問起始節點，然後訪問所有與起始節點直接相連的節點，接著訪問所有與這些節點相連但尚未訪問過的節點，以此類推。BFS 通常使用佇列 (Queue) 來實現。

題目給定的圖：
題目附帶了一個圖，其中包含節點 A 到 M。
我們需要找到「子樹 K」的 BFS 順序。這個表述有些奇怪，「子樹 K」通常是指以 K 為根的子樹，但 BFS 是對整個圖或連通分量的遍歷。
從圖形來看，K 節點似乎是屬於一個較大的圖結構。
圖形結構如下：
頂部：D, G, M
中間層：B, F, K
底部：A, C, E, H, J, L

節點之間的連線（根據圖形推測，可能有些連線不明確，但BFS的順序會依賴於圖的結構）：

• D 連接 B, G
• G 連接 D, M
• M 連接 G, K
• B 連接 D, A, C
• F 似乎沒有連線（或者連線不明確）
• K 連接 M, J, L
• A 連接 B
• C 連接 B, E
• E 連接 C
• H 似乎沒有連線（或者連線不明確）
• J 連接 K
• L 連接 K

題目提到「子樹 K 的 BFS 之順序」。這意味著我們應該以 K 為起始節點進行 BFS。
讓我們嘗試以 K 為起始節點進行 BFS。

BFS (起始節點 K)：

1. 起始節點：K
2. 第一層：訪問 K。將 K 加入佇列。
   • 佇列：[K]
3. 處理 K：從佇列中取出 K。訪問 K。將 K 的鄰居（尚未訪問過的）加入佇列。
   • K 的鄰居：M, J, L。
   • 訪問順序：K
   • 佇列：[M, J, L]
4. 處理 M：從佇列中取出 M。訪問 M。將 M 的鄰居（尚未訪問過的）加入佇列。
   • M 的鄰居：G。
   • 訪問順序：K, M
   • 佇列：[J, L, G]
5. 處理 J：從佇列中取出 J。訪問 J。將 J 的鄰居（尚未訪問過的）加入佇列。
   • J 的鄰居：無（根據圖，J 只連接到 K，K 已訪問）。
   • 訪問順序：K, M, J
   • 佇列：[L, G]
6. 處理 L：從佇列中取出 L。訪問 L。將 L 的鄰居（尚未訪問過的）加入佇列。
   • L 的鄰居：無（根據圖，L 只連接到 K，K 已訪問）。

本題考查網路封包傳輸中的檢查機制，特別是利用 One's Complement Sum 來計算 Checksum。

Checksum 的概念：
Checksum 是一種錯誤檢測方法，用於確保資料在傳輸過程中沒有被損壞。它通過對資料進行某種計算，生成一個較小的校驗值，並將其附加在資料後面。接收端收到資料後，會對接收到的資料執行相同的計算，並將計算結果與接收到的 Checksum 進行比較。如果兩者不匹配，則表示資料在傳輸過程中發生了錯誤。

One's Complement Sum (一次補碼加法)：
在網路協定（如 TCP, UDP, IP）中，常用的一種 Checksum 計算方法是 One's Complement Sum。其步驟如下：

1. 將所有 16 位元的資料段（或封包的特定部分）視為無號整數，進行一次補碼加法。
2. 在加法過程中，如果發生進位 (carry-out) 溢出到第 17 位，則將這個進位加回到最低位（第 1 位）。這個操作稱為「加一補碼」或「回卷」(wrap-around)。
3. 重複步驟 2，直到沒有進位為止。
4. 最終結果的 16 位元就是 Checksum。

題目給定的數據：
有四個 16 位元的二進位數字：

• $D_1 = 01100110\ 01100000_2$
• $D_2 = 01010101\ 01010101_2$

步驟 1：將二進位數字轉換為十進位，以便於計算

• $D_1 = 0110\ 0110\ 0110\ 0000_2$

  • $0110_2 = 6$
  • $0110_2 = 6$
  • $0110_2 = 6$
  • $0000_2 = 0$
  • $D_1 = 6 \times 2^{12} + 6 \times 2^8 + 6 \times 2^4 + 0 \times 2^0$ (這是一種方式，但直接轉換更方便)
  • $D_1 = (0 \times 2^{15} + 1 \times 2^{14} + 1 \times 2^{13} + 0 \times 2^{12} + 0 \times 2^{11} + 1 \times 2^{10} + 1 \times 2^9 + 0 \times 2^8 + 0 \times 2^7 + 1 \times 2^6 + 1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 0 \times 2^0)$
  • 直接轉換：
    $0110\ 0110\ 0110\ 0000_2$
    $= (2^{14} + 2^{13} + 2^{10} + 2^9 + 2^6 + 2^5)$
    $= 16384 + 8192 + 1024 + 512 + 64 + 32 = 26208_{10}$

• $D_2 = 0101\ 0101\ 0101\ 0101_2$

  • $0101_2 = 5$
  • $D_2 = (0 \times 2^{15} + 1 \times 2^{14} + 0 \times 2^{13} + 1 \times 2^{12} + 0 \times 2^{11} + 1 \times 2^{10} + 0 \times 2^9 + 1 \times 2^8 + 0 \times 2^7 + 1 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0)$
  • 直接轉換：
    $0101\ 0101\ 0101\ 0101_2$
    $= (2^{14} + 2^{12} + 2^{10} + 2^8 + 2^6 + 2^4 + 2^2 + 2^0)$

本題考查網路傳輸中的頻寬延遲乘積 (Bandwidth-Delay Product) 與實際傳輸時間的計算，並比較不同傳輸方式的效率。

核心概念：

• 頻寬 (Bandwidth, B)：資料傳輸的速率，單位通常是 bps (bits per second)。
• 延遲 (Latency, L)：資料從源點傳送到目的地所需的時間，主要由傳播延遲 (propagation delay) 和處理延遲 (processing delay) 等組成。
• 傳播延遲 (Propagation Delay)：信號在傳輸介質中傳播所需的時間。計算公式為 $T_{prop} = \frac{距離}{傳播速度}$。
• 頻寬延遲乘積 (Bandwidth-Delay Product, BDP)：$B \times L$。它代表在一個鏈路上，在一個往返延遲(RTT)或單程延遲(L)的時間內，能夠傳輸的最大資料量。對於一個 TCP 連接，BDP 決定了所需的緩衝區大小，以達到最大吞吐量。
• 傳輸時間 (Transmission Time)：傳輸一個資料量 (Data Size) 所需的時間。計算公式為 $T_{trans} = \frac{Data Size}{Bandwidth}$。
• 總傳輸時間 (Total Transfer Time)：通常是傳輸時間加上延遲時間，或者更精確地，考慮到流水線機制，則需要更詳細的計算。在某些情況下，可以簡化為 $T_{total} = T_{prop} + T_{trans}$ (對於單個封包且無流水線)。但對於大量資料，流水線效應會降低總時間。

題目數據：

• 資料量 (Data Size): 40 terabytes (TB)
• 光纖頻寬 (Bandwidth, B): 1 Gbps = $1 \times 10^9$ bps
• 光纖傳播速度 (Propagation Speed): $2.5 \times 10^8$ m/s
• 距離 (Distance): 4370 km = $4.370 \times 10^6$ m (注意：題目也給了英里，但公里更常用於計算)

FedEx Overnight Delivery：

• 運輸時間 (Transport Time): 24 小時

計算步驟：

1. 計算光纖傳輸時間

• a. 計算傳播延遲 ($T_{prop}$)：
  $T_{prop} = \frac{Distance}{Propagation Speed}$
  $T_{prop} = \frac{4.370 \times 10^6\ m}{2.5 \times 10^8\ m/s} = 0.01748\ s$

• b. 計算資料量 (Data Size) 的單位轉換：
  1 TB = $1024$ GB = $1024^2$ MB = $1024^3$ KB = $1024^4$ Bytes
  1 Byte = 8 bits
  Data Size = 40 TB = $40 \times 1024^4$ Bytes
  Data Size (in bits) = $40 \times 1024^4 \times 8$ bits
  $1024 = 2^{10}$
  Data Size = $40 \times (2^{10})^4 \times 8$ bits = $40 \times 2^{40} \times 2^3$ bits = $40 \times 2^{43}$ bits
  $40 \times 2^{43} \approx 40 \times (1.1 \times 10^{13}) \approx 4.4 \times 10^{14}$ bits
  更精確計算：$2^{10} = 1024 \approx 10^3$
  $40 TB = 40 \times 1024 \times 1024 \times 1024 \times 1024$ Bytes
  $40 TB = 40 \times (2^{10})^4$ Bytes = $40 \times 2^{40}$ Bytes
  $40 TB = 40 \times 2^{40} \times 8$ bits = $320 \times 2^{40}$ bits
  $2^{10} \approx 10^3$
  $2^{40} = (2^{10})^4 \approx (10^3)^4 = 10^{12}$
  Data Size $\approx 320 \times 10^{12}$ bits = $3.2 \times 10^{14}$ bits

  使用精確值：
  $40 TB = 40 \times (1024)^4$ Bytes $= 40 \times (1.0995 \times 10^{12})$ Bytes $\approx 4.398 \times 10^{13}$ Bytes
  $4.398 \times 10^{13}$ Bytes $\times 8$ bits/Byte $\approx 3.518 \times 10^{14}$ bits

• c. 計算傳輸時間 ($T_{trans}$)：
  $T_{trans} = \frac{Data Size (bits)}{Bandwidth (bps)}$
  $T_{trans} = \frac{3.518 \times 10^{14}\ bits}{1 \times 10^9\ bps} = 3.518 \times 10^5\ s$
  $3.518 \times 10^5\ s = 351800\ s$
  轉換為小時：$351800\ s / 3600\ s/hr \approx 97.72\ hours$

• d. 計算總傳輸時間 (考慮流水線)
  在這種情況下，資料量遠大於頻寬延遲乘積，並且有專用的光纖，可以假設流水線效應非常顯著，傳輸時間主要由 $T_{trans}$ 主導。
  BDP = $B \times T_{prop} = (1 \times 10^9\ bps) \times 0.01748\ s = 1.748 \times 10^7$ bits
  BDP $\approx 17.48$ Megabits (Mb)
  資料總量 $\approx 3.518 \times 10^{14}$ bits = $351800$ Gb = $351.8$ Tb

本題考查作業系統如何管理記憶體，使得大型程式能在實體記憶體不足的情況下執行，主要涉及虛擬記憶體 (Virtual Memory) 的概念。

核心觀念：

1. 虛擬記憶體 (Virtual Memory)：作業系統為每個程序提供一個獨立的、連續的、更大的虛擬位址空間，而實際的實體記憶體（RAM）可能較小且不連續。虛擬記憶體允許程式使用比實際 RAM 更多的記憶體。
2. 分頁 (Paging)：虛擬位址空間被劃分為固定大小的區塊，稱為「頁面 (Pages)」。實體記憶體也被劃分為相同大小的區塊，稱為「頁框 (Page Frames)」。
3. 頁面置換 (Page Replacement)：當程式需要訪問的頁面不在實體記憶體中時（發生「頁面錯誤」Page Fault），作業系統會將該頁面從輔助儲存（如硬碟上的交換空間 Swap Space）載入到一個空閒的頁框中。如果沒有空閒頁框，作業系統會選擇一個目前不在使用中的頁面，將其寫回硬碟（如果被修改過），然後將新頁面載入到該頁框。
4. 記憶體管理單元 (MMU - Memory Management Unit)：硬體元件，負責將程式使用的虛擬位址轉換為實體位址。
5. 頁表 (Page Table)：作業系統維護的資料結構，儲存了虛擬頁面到實體頁框的映射關係。MMU 查詢頁表來進行位址轉換。
6. 交換空間 (Swap Space)：硬碟上的一塊區域，用於儲存暫時不在實體記憶體中的頁面。
7. 程序管理 (Process Management)：作業系統為每個程序維護獨立的虛擬位址空間和頁表。

執行流程說明：

1. 程式載入與執行：
   當使用者啟動一個 12 GB 的程式時，作業系統並不會一次性將整個程式載入到 8 GB 的實體記憶體中。
   相反，程式的代碼和資料會先儲存在硬碟上。作業系統會為該程式創建一個虛擬位址空間（例如，可能是一個 12 GB 或更大的虛擬空間）。

2. 分頁與頁表建立：
   作業系統將程式的虛擬位址空間劃分為頁面 (Pages)。同時，實體記憶體被劃分為頁框 (Page Frames)。作業系統會為該程式建立一個頁表 (Page Table)，記錄每個虛擬頁面映射到哪個實體頁框。

3. 首次執行與頁面錯誤 (Page Fault)：

   • 當程式開始執行時，CPU 根據指令中的虛擬位址，通過 MMU 嘗試查找對應的實體位址。
   • MMU 查詢程式的頁表。如果程式執行的某一部分（例如某個函數或資料結構）所在的虛擬頁面不在實體記憶體中（對應的頁表項可能標示為無效或指向交換空間），就會發生頁面錯誤 (Page Fault)。
   • 頁面錯誤會觸發一個中斷，將 CPU 控制權交給作業系統的頁面錯誤處理程序。

4. 頁面調入 (Page In)：

   • 頁面錯誤處理程序會識別出需要哪個虛擬頁面。
   • 作業系統會在硬碟的交換空間 (Swap Space) 中找到這個頁面。
   • 如果實體記憶體中有空閒的頁框，作業系統會將該頁面從硬碟載入到一個空閒頁框。
   • 如果實體記憶體已滿，作業系統會根據某種頁面置換算法（如 LRU - Least Recently Used）選擇一個當前不常用的頁面，將其寫回交換空間（如果它被修改過），然後將所需的頁面載入到騰出的頁框中。
   • 更新該程式的頁表，將虛擬頁面映射到新的實體頁框。
   • 恢復程式執行，CPU 重新嘗試訪問該虛擬位址，此時 MMU 就能成功找到實體位址。

5. 程式執行與記憶體管理：

   • 程式在執行過程中，只有當前需要使用的程式碼和資料所在的頁面才需要被載入到實體記憶體中。
   • 當程式訪問的虛擬頁面不在 RAM 中時，就會發生頁面錯誤，作業系統會將所需的頁面從硬碟調入。
   • 當 RAM 不足時，作業系統會將暫時不用的頁面換出到硬碟的交換空間，以騰出空間給其他需要的頁面。
   • 這個過程（稱為「請求分頁」(Demand Paging) 和「頁面置換」(Page Replacement)）使得程式可以「看起來」擁有比實際 RAM 更大的記憶體空間。

6. Context Switch 與記憶體：

   • 當作業系統在不同程序之間進行Context Switch時，它會保存當前程序的 CPU 狀態，並載入下一個

本題考查非對稱式加密 (Asymmetric Encryption) 的應用，特別是結合數位簽章 (Digital Signature) 的概念。題目中的圖示雖然簡略，但可以推斷出 Sender (S) 使用了某種加密方式，並且提到了 "R's Public Key" 和 "S's Private Key"。

圖示分析：

• Sender (S)：
  • 有兩個輸入：1101101 和 1100001。這可能是原始訊息 (Message) 或其雜湊值 (Hash)。
  • 有兩個密鑰：S's Private Key。
  • 有兩個操作：Encrypt (被標記了兩次，可能表示加密或簽章)。
• Receiver (R)：
  • 接收到一個輸出。
  • 有兩個密鑰：R's Public Key。

常見的非對稱式加密應用場景：

1. 機密性 (Confidentiality)：確保只有預期的接收者才能讀取訊息。
   • 流程：Sender 用 Receiver 的 Public Key 加密訊息。Receiver 用自己的 Private Key 解密。
   • 圖示對應：Sender 加密時應使用 R's Public Key，Receiver 解密時應使用 R's Private Key。
2. 鑑別性 (Authentication)：驗證訊息的來源是否為聲稱的發送者。
   • 流程：Sender 用自己的 Private Key 對訊息（或其雜湊值）進行「簽章」(Sign)。Receiver 用 Sender 的 Public Key 來驗證簽章。
3. 完整性 (Integrity)：確保訊息在傳輸過程中未被篡改。
   • 流程：通常與鑑別性結合，通過對訊息的雜湊值進行簽章來實現。
4. 不可否認性 (Non-repudiation)：發送者無法否認自己發送了該訊息。
   • 流程：通過數位簽章實現，因為只有發送者擁有其私鑰。

題目圖示的推測：
圖示中 Sender 使用了 S's Private Key 進行 Encrypt 操作，並且 Receiver 使用 R's Public Key。
這種組合（Sender 用自己的 Private Key，Receiver 用 Sender 的 Public Key）通常用於實現鑑別性 (Authentication) 和不可否認性 (Non-repudiation)，即數位簽章 (Digital Signature)。

數位簽章的流程：

1. 產生雜湊值 (Hashing)：Sender 對原始訊息 (Message, M) 計算其雜湊值 (Hash, H)。
   $H = Hash(M)$
   雜湊函數的特性：輸入相同，輸出必相同；輸入微小改變，輸出劇烈改變；難以從雜湊值反推原始訊息。
   在圖示中，1101101 和 1100001 可能是訊息 M，也可能是訊息 M 的雜湊值 H。
   假設 1101101 是訊息 M，那麼 Sender 會先計算 $H = Hash(1101101)$。
2. 私鑰加密 (簽章)：Sender 使用自己的私鑰 (S's Private Key) 對雜湊值 H 進行加密，生成數位簽章 (Digital Signature, S)。
   $S = Encrypt(H, S's\ Private\ Key)$
   圖示中的 Encrypt 操作，使用 S's Private Key，很可能就是這個步驟。
3. 傳送：Sender 將原始訊息 M 和數位簽章 S 一起傳送給 Receiver。
4. 接收與驗證：
   • Receiver 收到訊息 M 和簽章 S。
   • 驗證雜湊值：Receiver 使用與 Sender 相同的雜湊函數，計算接收到的訊息 M 的雜湊值 $H'$。
     $H' = Hash(M)$
   • 公鑰解密：Receiver 使用 Sender 的公鑰 (S's Public Key) 對接收到的數位簽章 S 進行解密，得到一個雜湊值 $H_{decrypted}$。
     $H_{decrypted} = Decrypt(S, S's\ Public\ Key)$
     (注意：題目圖示中 Receiver 只有 R's Public Key，但卻是 S's Private Key 加密，所以 Receiver 需要 S's Public Key 來驗證。)
   • 比較：Receiver 比較 $H'$ 和 $H_{decrypted}$。
     • 如果 $H' = H_{decrypted}$，則簽章有效，表示：
       • 鑑別性 (Authentication)：訊息確實來自擁有 S's Private Key 的 Sender。
       • 完整性 (Integrity)：訊息 M 在傳輸過程中沒有被篡改（因為雜湊值匹配）。
       • 不可否認性 (Non-repudiation)：Sender 無法否認發送了該訊息。
     • 如果 $H' \neq H_{decrypted}$，則簽章無效。

題目圖示的可能解讀：
圖示中 Sender 有兩個輸入 1101101 和 1100001，以及一個 Encrypt 操作使用 S's Private Key。
這可能表示：

• 1101101 是原始訊息 M。
• 1100001 可能是訊息 M 的雜湊值 H，或者 Sender 進行了某種組合。
• Encrypt 使用 S's Private Key 是對雜湊值 H 進行簽章。

如果題目圖示是這樣理解：
Sender 對訊息 M (例如 1101101) 計算雜湊值 H (1100001 可能是 H 的值或計算過程的一部分)，然後用 S's Private Key 加密 H，得到數位簽章。
Receiver 收到 M 和簽章，用 S's Public Key 解密簽章得到 H_decrypted，同時自己計算 M 的雜湊值 H'。比較 H' 和 H_decrypted。
這裡 Receiver 提供的 R's Public Key 似乎與簽章驗證無關，除非是為了加密訊息本身。

另一種可能性：結合機密性與鑑別性
如果 Sender 希望傳送的訊息既保密又來源可信，可以結合兩種操作：

1. 加密訊息：Sender 用 R's Public Key 加密訊息 M，得到密文 C。
2. 數位簽章：Sender 對原始訊息 M (或其雜湊值 H) 使用 S's Private Key 簽章，得到簽章 S。
3. 傳送：將密文 C 和簽章 S 一起傳送給 Receiver。
4. 接收與驗證：
   • Receiver 用 R's Private Key 解密 C 得到 M。
   • Receiver 用 S's Public Key 驗證 S (基於 M)。

然而，題目圖示的 Encrypt 操作是同時與 1101101, 1100001 和 S's Private Key 相關聯，而 R's Public Key 則在 Receiver 端。這更傾向於單純的數位簽章流程。

題目圖示的簡化與可能的誤導：
圖示中的 FX 和 1101101, 1100001 的關係不明。

本題考查類神經網路 (Neural Networks) 在訓練過程中常見的兩個問題：過度擬合 (Overfitting) 和資料不平衡 (Imbalanced Data)，以及對應的處理方法。

一、Overfitting (過度擬合)

定義：
過度擬合是指模型在訓練資料上表現非常好（例如，訓練誤差很低），但在未見過的測試資料上表現卻很差。這是因為模型過於複雜，學習到了訓練資料中的雜訊或特定模式，而未能學習到資料的普遍規律。

處理方法：

1. 增加訓練資料量 (More Training Data)：

   • 如果可能，獲取更多樣化的訓練資料。更多的資料可以幫助模型學習到更普遍的規律，減少對特定訓練樣本的依賴。

2. 簡化模型 (Simplify Model)：

   • 減少神經網路的層數或單元數 (Number of Layers/Units)：較淺或較窄的網路模型通常具有較低的擬合能力。
   • 使用更簡單的架構：例如，對於某些問題，使用線性模型而不是複雜的神經網路。

3. 正則化 (Regularization)：

   • L1/L2 正則化 (L1/L2 Regularization)：在模型的損失函數中加入權重（Weights）的 L1 或 L2 範數作為懲罰項。這會傾向於使權重變小，從而簡化模型。
     • L1 正則化：$\lambda \sum |w_i|$
     • L2 正則化：$\lambda \sum w_i^2$
   • Dropout：在訓練過程中，隨機「丟棄」一部分神經元（及其連接）。這可以防止神經元之間過度依賴，迫使網路學習更魯棒的特徵。每次訓練迭代都會隨機選擇不同的神經元被丟棄。
   • Early Stopping (提前停止)：監控模型在驗證集上的性能。當驗證集上的性能開始下降（即使訓練集上的性能仍在提高）時，就停止訓練。這可以防止模型在學習到雜訊之前就停止。

4. 資料增強 (Data Augmentation)：

   • 對於圖像、音頻等資料，可以通過對現有訓練資料進行隨機變換（如旋轉、縮放、裁剪、顏色抖動、添加噪聲等）來生成新的訓練樣本。這相當於在不實際獲取新資料的情況下，增加了訓練資料的「多樣性」。

5. 交叉驗證 (Cross-Validation)：

   • 使用 K-Fold 交叉驗證等方法，更全面地評估模型的泛化能力，並幫助選擇最佳的模型超參數。

二、Imbalanced Data (資料不平衡)

定義：
資料不平衡是指在分類問題中，不同類別的樣本數量差異巨大。例如，在一個二分類問題中，一個類別有 9900 個樣本，而另一個類別只有 100 個樣本。如果直接使用標準的分類器，模型可能會傾向於預測樣本數較多的類別，導致在少數類別上的預測性能很差。

處理方法：

1. 重採樣技術 (Resampling Techniques)：

   • 過採樣 (Oversampling)：
     • 隨機過採樣 (Random Oversampling)：複製少數類別的樣本，直到其數量與多數類別大致相等。缺點是可能導致過擬合。
     • SMOTE (Synthetic Minority Over-sampling Technique)：不是簡單複製樣本，而是通過插值的方法，在少數類別樣本之間生成新的「合成」樣本。這是比較常用的過採樣方法。
   • 欠採樣 (Undersampling)：
     • 隨機欠採樣 (Random Undersampling)：隨機移除多數類別的樣本，直到其數量與少數類別大致相等。缺點是可能丟失多數類別的重要資訊。
     • Tomek Links / Edited Nearest Neighbours：更聰明的欠採樣方法，嘗試移除多數類別中與少數類別樣本「接近」的樣本，以清晰化類別邊界。

2. 調整模型權重 (Adjusting Class Weights)：

   • 在訓練模型時，為少數類別的樣本分配更高的權重，而為多數類別的樣本分配較低的權重。這樣，模型在優化損失函數時，會更關注對少數類別的預測準確性。
   • 許多機器學習庫（如 scikit-learn）的模型都支持 class_weight 參數。

3. 使用合適的評估指標 (Use Appropriate Evaluation Metrics)：

   • 在資料不平衡的情況下，準確率 (Accuracy) 是一個誤導性的指標。因為模型即使將所有樣本都預測為多數類別，準確率也可能很高。
   • 應使用更合適的指標，例如：
     • 精確率 (Precision)
     • 召回率 (Recall / Sensitivity)
     • F1-Score (Precision 和 Recall 的調和平均數)
     • AUC (Area Under the ROC Curve)

本題考查機器學習分類模型評估指標，特別是 ROC 曲線 (Receiver Operating Characteristic Curve) 和相關概念。圖中顯示了一個 ROC 曲線的示意圖。

ROC 曲線介紹：
ROC 曲線是衡量二分類模型性能的常用工具。它繪製了在不同分類閾值下，真陽性率 (True Positive Rate, TPR) 與偽陽性率 (False Positive Rate, FPR) 之間的權衡關係。

• TPR (True Positive Rate)，也稱為召回率 (Recall) 或敏感度 (Sensitivity)：
  $TPR = \frac{TP}{TP + FN}$
  表示所有實際為陽性的樣本中，被模型正確預測為陽性的比例。

• FPR (False Positive Rate)：
  $FPR = \frac{FP}{FP + TN}$
  表示所有實際為陰性的樣本中，被模型錯誤預測為陽性的比例。

• TP (True Positive)：實際為陽性，預測為陽性。

• FP (False Positive)：實際為陰性，預測為陽性 (Type I Error)。

• TN (True Negative)：實際為陰性，預測為陰性。

• FN (False Negative)：實際為陽性，預測為陰性 (Type II Error)。

圖示分析與問題解答：

圖中包含了以下元素：

• 橫軸：False Positive (FP) / Total Negative。這是 FPR。
• 縱軸：True Positive (TP) / Total Positive。這是 TPR 或 Sensitivity。
• 曲線：從左下角 (0,0) 到右上角 (1,1) 的曲線，代表一個分類模型的性能。
• 區域：
  • 左上角區域：代表高的 TPR 和低的 FPR。
  • 右下角區域：代表低的 TPR 和高的 FPR。
  • 中間虛線：從 (0,0) 到 (1,1) 的對角線。
• 標記 A：在縱軸上標記了 100% Sensitivity。

1. False Positive 區塊之線下面積之意義 (Area under the curve of the False Positive block)

• 題目描述「False Positive 區塊之線下面積」可能指的是 ROC 曲線下方，從 X 軸到 ROC 曲線，再到 Y 軸的面積。
• 更準確地說，ROC 曲線下的面積 (Area Under the Curve, AUC) 是衡量模型整體性能的一個重要指標。AUC 的值介於 0 和 1 之間。
  • AUC = 0.5 表示模型性能與隨機猜測相當。
  • AUC > 0.5 表示模型性能優於隨機猜測。
  • AUC = 1 表示模型性能完美。
• 這個面積代表了模型將隨機選擇的陽性樣本排在隨機選擇的陰性樣本之前的概率。
• 如果題目指的是 ROC 曲線本身下方，從 X 軸到曲線的面積，那麼它就是 AUC (Area Under the ROC Curve)。AUC 值越高，表示模型的分類能力越強。

2. True Negative 之意義 (True Negative)

• True Negative (TN)：表示一個樣本實際為陰性 (Negative)，並且被模型正確預測為陰性。
• 在 ROC 曲線的上下文中，TN 與 FPR 相關。FPR 的分母是 $FP + TN$ (所有實際為陰性的樣本數)。
• True Negative Rate (TNR) 或Specificity = $\frac{TN}{TN + FP}$。
• 在 ROC 圖上，FPR = $\frac{FP}{FP + TN}$，TPR = $\frac{TP}{TP + FN}$。
• True Negative 的意義是模型正確識別出「不是」某類別的樣本。例如，在疾病檢測中，True Negative 是指沒有患病且被模型判斷為未患病的健康人。

3. 中間虛線之意義 (The dotted line in the middle)

• 這條從 (0,0) 到 (1,1) 的對角線代表一個隨機分類器 (Random Classifier) 的性能。
• 對於隨機分類器，無論是陽性還是陰性樣本，它都是隨機猜測，因此 TPR 和 FPR 的值會成比例增長，形成一條直線。
• 任何一個有意義的分類模型的 ROC 曲線都應該盡可能地偏離這條線，向左上角（高 TPR，低 FPR）移動。

本題考查無線網路 (Wi-Fi) 中的 RTS/CTS (Request to Send / Clear to Send) 機制，以及它如何解決隱藏終端問題 (Hidden Terminal Problem)。

隱藏終端問題 (Hidden Terminal Problem)：
在無線網路（如 Wi-Fi）中，兩個節點 A 和 B 可以互相通信，但它們都無法直接聽到對方。然而，它們可能同時都連接到一個接入點 (Access Point, AP) 或另一個節點 C。
假設 A 和 C 可以互相通信，B 和 C 可以互相通信，但 A 和 B 聽不到對方。
如果 A 和 B 同時向 C 發送資料，則 C 會收到來自 A 和 B 的衝突資料，導致 C 無法正確接收任何一個。
問題在於，A 不知道 B 正在發送資料，B 也不知道 A 正在發送資料，但它們都想與 C 通信，從而造成衝突。

802.11 的 RTS/CTS 機制：
RTS/CTS 是一種「握手」機制，用於在實際資料傳輸之前，先協調兩個節點之間的通信。這個機制可以選擇性地啟用，通常用於傳輸較大封包時。

工作流程：

1. 節點 A 想要發送資料給節點 C：
   • A 首先向 C 發送一個 RTS (Request to Send) 封包。這個 RTS 封包中包含 A 預計傳輸的資料量（或預計傳輸時間）。
2. 接入點 C 回應 CTS (Clear to Send)：
   • C 收到 A 的 RTS 後，如果 C 準備好接收資料，它會向 A 發送一個 CTS 封包。
   • 關鍵點：C 在發送 CTS 的同時，還會廣播一個 CTS 封包給所有能聽到 C 的節點（包括 B，如果 B 在 C 的範圍內）。這個廣播的 CTS 封包會告知其他節點，C 正在與 A 進行通信，並且在接下來的一段時間內（由 RTS 中的資訊決定）將無法接收其他節點的資料。
3. 節點 A 開始傳輸資料：
   • A 收到 C 的 CTS 後，開始向 C 發送實際的資料封包。
4. 其他節點的行為：
   • 節點 B（以及其他能聽到 C 的節點）收到 C 發送的廣播 CTS 後，會知道 C 正在忙碌，並且 A 正在與 C 通信。
   • 因此，B 會暫停其發送請求，等待 CTS 中指示的通信結束後再嘗試發送。

RTS/CTS 如何解決隱藏終端問題：

• 在上述例子中，節點 A 和 B 聽不到對方，但都連接到 C。
• 如果 A 想發送資料，它會發送 RTS。C 會回應 CTS，並且這個 CTS 會被廣播。
• 節點 B 聽到 C 的 CTS 後，就知道 C 正在與 A 通信，並且通信期間 C 不會響應 B 的請求。
• 因此，B 會暫停發送，避免了與 A 的資料發生衝突。

本題考查運算式轉換，包括轉換為表達樹 (Expression Tree)、前綴表示法 (Prefix Notation) 和後綴表示法 (Postfix Notation)。

運算式：$(A \times B - C) \times D + E$

運算符的優先級：
在沒有括號的情況下，通常的優先級順序是：

1. 括號 ()
2. 乘法 * 和除法 /
3. 加法 + 和減法 -

在這個運算式中，括號 (A * B - C) 具有最高優先級。

1. Expression Tree (表達樹)
表達樹是一種二元樹，其中：

• 葉節點 (Leaf Nodes) 是運算數 (Operands)，如 A, B, C, D, E。
• 內部節點 (Internal Nodes) 是運算符 (Operators)，如 *, -, +。
• 每個內部節點的左子樹代表其左運算元，右子樹代表其右運算元。

構建表達樹的步驟：

1. 找到最高優先級的運算符，或者由括號確定的運算符，作為樹的根節點。
2. 在我們的運算式 $(A \times B - C) \times D + E$ 中，最後執行的運算符是 +。所以 + 是根節點。
3. + 的左子樹是來自 (A * B - C) * D。
4. + 的右子樹是來自 E。
5. 現在處理左子樹 (A * B - C) * D。最後執行的運算符是 *。所以 * 是 + 的左子節點。
6. * 的左子樹是來自 (A * B - C)。
7. * 的右子樹是來自 D。
8. 現在處理 (A * B - C)。最後執行的運算符是 -。所以 - 是 * 的左子節點。
9. - 的左子樹是來自 A * B。
10. - 的右子樹是來自 C。
11. 現在處理 A * B。運算符是 *。所以 * 是 - 的左子節點。
12. * 的左子樹是 A。
13. * 的右子樹是 B。

畫出表達樹：

        +
       / \
      *   E
     / \
    *   D
   / \
  A   B

請注意，在處理 (A * B - C) 時，* 的優先級高於 -。
所以，我們應該先處理 A * B。
樹的結構應該是：

        +
       / \
      *   E
     / \
    -   D
   / \
  *   C
 / \
A   B

這個結構是正確的。

2. Prefix Notation (前綴表示法)
前綴表示法（也稱為波蘭表示法 Polish Notation）將運算符放在其運算元之前。
規則：從樹的根節點開始，先輸出運算符，然後遞迴地輸出左子樹，再遞迴地輸出右子樹。

• 根節點：+
• 左子樹根節點：* (來自 (A*B-C)*D)
• 右子樹根節點：E

所以，結果是 + (* ... E)

現在處理左子樹 * (來自 (A*B-C)*D)：

• 運算符：*
• 左子樹根節點：- (來自 A*B-C)
• 右子樹根節點：D

所以，結果是 + (* (- ... D) E)

現在處理 - (來自 A*B-C)：

• 運算符：-
• 左子樹根節點：* (來自 A*B)
• 右子樹根節點：C

所以，結果是 + (* (- (* ... C) D) E)

現在處理 * (來自 A*B)：

• 運算符：*
• 左子樹根節點：A
• 右子樹根節點：B

所以，結果是 + (* (- (* A B) C) D) E

最終前綴表示法：+ * - * A B C D E

3. Postfix Notation (後綴表示法)
後綴表示法（也稱為逆波蘭表示法 Reverse Polish Notation, RPN）將運算符放在其運算元之後。
規則：從樹的葉節點開始，遞迴地輸出左子樹，然後遞迴地輸出右子樹，最後輸出運算符。

本題考查乙太網路 (Ethernet) 中 CSMA/CD (Carrier Sense Multiple Access with Collision Detection) 協定下的衝突處理機制，特別是二進位指數退避 (Binary Exponential Backoff) 演算法。

CSMA/CD 的背景：
在早期共享式乙太網路中，所有設備共享同一條傳輸介質。為了避免或處理多個設備同時發送數據造成的衝突 (Collision)，CSMA/CD 協定被設計出來。

• Carrier Sense (載波偵聽)：在發送數據前，先偵聽介質是否空閒。如果空閒，則發送。
• Multiple Access (多點接入)：多個設備可以接入同一個傳輸介質。
• Collision Detection (衝突偵測)：在發送數據的同時，繼續監聽介質。如果在發送過程中發現訊號異常（表示發生了衝突），則立即停止發送。

衝突發生後：
當兩個或多個節點同時發送數據並發生衝突時，根據 CSMA/CD，它們會：

1. 停止發送：立即停止發送數據。
2. 發送衝突訊號 (Jam Signal)：為了讓其他所有節點都意識到發生了衝突，發送方會發送一個短的「衝突訊號」(Jam Signal)。
3. 退避 (Backoff)：每個發生衝突的節點都需要等待一段時間後，才能重新嘗試發送數據。這個等待時間的選擇至關重要，它直接影響到網路的效率和穩定性。

二進位指數退避 (Binary Exponential Backoff, BEB)：
BEB 演算法是 CSMA/CD 協定中用於確定衝突後等待時間的標準方法。其核心思想是：

• 隨機等待：每個節點會隨機選擇一個等待時間。
• 指數增長：如果衝突持續發生（即多次嘗試發送都以衝突告終），則隨機選擇的等待時間範圍會指數級增長。

BEB 的具體步驟：

1. 衝突計數器 (Collision Counter, $k$)：每個節點維護一個衝突計數器 $k$，記錄連續發生衝突的次數。
2. 隨機選擇等待槽 (Slot Time)：
   • 在第一次衝突後 ($k=1$)，節點會從 $0$ 到 $2^k - 1$ 的範圍內隨機選擇一個「槽」(slot) 的數量。
   • 對於乙太網路，一個槽 (slot time) 的長度是固定的，通常是 51.2 微秒 ($\mu s$)。
   • 所以，第一次衝突後，等待時間是 $k=1$，範圍是 $[0, 2^1-1] = [0, 1]$ 個 slot time。節點隨機選擇等待 0 或 1 個 slot time。
3. 等待並重試：節點等待選定的時間後，重新偵聽介質。如果介質空閒，則再次嘗試發送。
4. 衝突持續：如果重試後再次發生衝突，則衝突計數器 $k$ 增加 1。
   • 第二次衝突 ($k=2$)：範圍是 $[0, 2^2-1] = [0, 3]$ 個 slot time。
   • 第三次衝突 ($k=3$)：範圍是 $[0, 2^3-1] = [0, 7]$ 個 slot time。
   • 依此類推，範圍是 $[0, 2^k - 1]$ 個 slot time。
5. 上限限制：為了防止網路癱瘓，衝突計數器 $k$ 通常會有一個上限（例如，在標準乙太網路中是 10）。
   • 當 $k$ 達到上限（例如 10）後，如果仍然發生衝突，節點會從範圍 $[0, 2^{10} - 1]$ 中隨機選擇等待時間。
   • 如果衝突持續發生，達到一個極限次數（例如 16 次），節點會放棄傳輸，並向更高層級的協議報告錯誤。
6. 重置計數器：
   • 如果一次數據幀成功發送，則衝突計數器 $k$ 會被重置為 0。
   • 如果節點在等待期間成功偵聽到介質空閒，並且沒有發生衝突，即使沒有成功發送數據，也可能重置計數器（具體實現可能略有不同，但通常是成功傳輸後重置）。

BEB 的目的：

• 避免持續衝突：通過引入隨機等待，降低了兩個節點在衝突後又立即以相同等待時間再次衝突的概率。
• 減少網路負載：當網路擁塞（衝突頻繁）時，等待時間會自動增加，從而減少發送請求，緩解網路壓力。

本題考查程式設計，要求撰寫一個函式 isPowerofTwo(n)，判斷給定的非負整數 n 是否為 2 的冪次方（即 $n = 2^x$，其中 $x$ 為整數）。

問題分析：

• 輸入：一個非負整數 n。
• 輸出：布林值 True 或 False。
• 條件：n 必須能夠表示為 $2^x$，其中 $x$ 必須是整數。

考慮邊界情況：

• n = 0：0 不是 2 的任何整數次冪。所以 isPowerofTwo(0) 應返回 False。
• n = 1：$1 = 2^0$。0 是整數。所以 isPowerofTwo(1) 應返回 True。
• n 為負數：題目說明 n 是非負整數，所以不用考慮負數。

方法一：循環除以 2
如果一個數是 2 的冪次方，那麼它可以不斷地被 2 整除，直到結果為 1。如果在除法的過程中，遇到不能被 2 整除的奇數（除了 1 之外），那麼它就不是 2 的冪次方。

演算法步驟：

1. 如果 n 小於或等於 0，返回 False。
2. 如果 n 等於 1，返回 True (因為 $1 = 2^0$)。
3. 當 n 大於 1 時，進入循環：
   a. 檢查 n 是否能被 2 整除 (即 n % 2 == 0)。
   b. 如果不能被 2 整除，說明 n 不是 2 的冪次方（因為它包含除了 2 以外的其他因子），返回 False。
   c. 如果能被 2 整除，則將 n 除以 2 (n = n / 2)。
   d. 重複步驟 a-c，直到 n 變為 1。
4. 如果循環結束（即 n 變為 1），說明 n 最初是 2 的冪次方，返回 True。

Pseudocode (方法一)：

function isPowerofTwo(n):
  // Handle non-positive numbers
  if n <= 0:
    return False

  // Loop while n is divisible by 2
  while n > 1:
    // If n is odd and greater than 1, it's not a power of two
    if n % 2 != 0:
      return False
    // Divide n by 2
    n = n / 2

  // If the loop finishes, n must be 1, which is 2^0
  // (The case n=1 is handled implicitly here, as the loop condition n>1 fails immediately)
  return True

測試範例：

• isPowerofTwo(16):
  • n=16 > 1, 16%2==0, n=8
  • n=8 > 1, 8%2==0, n=4
  • n=4 > 1, 4%2==0, n=2
  • n=2 > 1, 2%2==0, n=1
  • n=1, loop ends. Return True. (Correct)
• isPowerofTwo(12):
  • n=12 > 1, 12%2==0, n=6
  • n=6 > 1, 6%2==0, n=3
  • n=3 > 1, 3%2!=0, return False. (Correct)
• isPowerofTwo(1):
  • n=1, loop condition n>1 is false. Return True. (Correct)
• isPowerofTwo(0):
  • n<=0 is true. Return False. (Correct)

方法二：位元操作 (Bitwise Operation)
一個正整數如果是 2 的冪次方，那麼它的二進位表示只有一個位元是 1，其餘位元都是 0。
例如：

• $1 = 2^0 = 0001_2$
• $2 = 2^1 = 0010_2$
• $4 = 2^2 = 0100_2$
• $8 = 2^3 = 1000_2$

考慮一個數 n 和 n-1 的二進位表示：

• 如果 n 是 2 的冪次方 (例如 $n=8 = 1000_2$)，那麼 n-1 ($7 = 0111_2$) 的所有位元都會是 1，且長度比 n 少一位。

• 當我們對 n 和 n-1 進行按位與 (Bitwise AND) 操作 (n & (n-1)) 時：

  • 對於 $n=8 (1000_2)$ 和 $n-1=7 (0111_2)$：
    $1000_2$
    & $0111_2$

    $0000_2$
  • 結果是 0。

• 如果 n 不是 2 的冪次方（例如 $n=12 = 1100_2$），那麼 n-1 ($11 = 1011_2$)：
  $1100_2$
  & $1011_2$

  $1000_2$ (結果不為 0)

演算法步驟：

1. 如果 n 小於或等於 0，返回 False。
2. 計算 n & (n-1)。
3. 如果結果為 0，則 n 是 2 的冪次方，返回 True。
4. 否則，返回 False。

Pseudocode (方法二)：

function isPowerofTwo(n):
  // Handle non-positive numbers
  if n <= 0:
    return False

  // Check if n has only one bit set to 1
  // If n is a power of two, n & (n-1) will be 0
  return (n & (n - 1)) == 0

測試範例：

• isPowerofTwo(16): $n=16 (10000_2)$, $n-1=15 (01111_2)$. $10000_2 \& 01111_2 = 0$. Return True. (Correct)
• isPowerofTwo(12): $n=12 (1100_2)$, $n-1=11 (1011_2)$. $1100_2 \& 1011_2 = 1000_2 \neq 0$. Return False. (Correct)
• isPowerofTwo(1): $n=1 (0001_2)$, $n-1=0 (0000_2)$. $0001_2 \& 0000_2 = 0$. Return True. (Correct)
• isPowerofTwo(0): $n<=0$ is true. Return False. (Correct)

方法三：檢查位元數量 (Bit Count)
一個正整數是 2 的冪次方，當且僅當它的二進位表示中只有一個位元是 1。