110 年 國立政治大學數位內容碩士學位學程資訊技術組《計算機概論與程式設計》

本題考查 OSI 七層模型的組成。OSI（Open Systems Interconnection）模型是一個概念模型，將網路通訊協定分為七個層級，分別為：

1. 實體層 (Physical Layer)：負責傳輸原始位元流。
2. 資料鏈結層 (Data Link Layer)：負責在節點之間傳輸資料框，並處理錯誤偵測與修正。
3. 網路層 (Network Layer)：負責在不同網路之間路由資料封包。
4. 傳輸層 (Transport Layer)：負責端對端（end-to-end）的資料傳輸，確保資料的可靠性與順序。

本題考查圖像壓縮技術的種類，特別是無損壓縮（lossless compression）與有損壓縮（lossy compression）。

• 無損壓縮：壓縮後可以完全恢復原始資料，沒有任何資訊損失。
• 有損壓縮：壓縮過程中會捨棄部分資訊，以達到更高的壓縮率，但恢復的資料與原始資料會有差異。

我們來分析各選項：
(A) GIF (Graphics Interchange Format)：使用 LZW 演算法，是一種無損壓縮格式。

本題考查不同類型記憶體的存取速度。記憶體的速度通常與其技術、結構以及與 CPU 的距離有關。一般而言，存取速度由快到慢的順序大致為：CPU 暫存器 (Registers) > 快取記憶體 (Cache) > 主記憶體 (RAM) > 固態硬碟 (SSD) > 機械硬碟 (HDD) > 輔助儲存 (如光碟)。

我們來分析各選項：
(A) ROM (Read-Only Memory)：唯讀記憶體，通常用於儲存固件，存取速度相對較慢，且主要是讀取。

本題考查迭代（iteration）與遞迴（recursion）在計算費氏數列（Fibonacci number）時的效率比較。

費氏數列的定義是：
$F(0) = 0$
$F(1) = 1$
$F(n) = F(n-1) + F(n-2)$ for $n > 1$

• 遞迴方法：直接根據定義實現。例如，計算 fib(n) 會呼叫 fib(n-1) 和 fib(n-2)，而這兩個呼叫又會進一步遞迴。這種實現方式雖然直觀，但會產生大量的重複計算。例如，計算 fib(5) 會計算 fib(4) 和 fib(3)。

核心觀念

本題考查遞迴函式呼叫次數分析（Recursion Call Tree Analysis）。

在計算機概論與資料結構中，計算費氏數列（Fibonacci sequence）的典型無記憶化（Naive）遞迴定義通常設定基礎終止條件（Base case）為前兩項 $F(1) = 1, F(2) = 1$，其遞迴關係如下：

$$F(n) = \begin{cases} 1, & \text{if } n = 1 \text{ or } n = 2 \\ F(n-1) + F(n-2), & \text{if } n > 2 \end{cases}$$

設 $C(n)$ 代表計算 fib(n) 時，函式 fib() 被呼叫的總次數（包含最外層呼叫與內部所有子呼叫）：

1. 當 $n \le 2$ 時，遇到終止條件直接回傳，僅呼叫自身 1 次，即 $C(1) = 1, C(2) = 1$。
2. 當 $n > 2$ 時，呼叫 fib(n) 本身算 1 次，接著內部產生兩次遞迴呼叫 fib(n-1) 與 fib(n-2)，因此呼叫次數滿足遞迴關係式：

$$C(n) = 1 + C(n-1) + C(n-2)$$

---

解題方法

1. 關鍵程式碼實作

標準無記憶化的遞迴實作如下：

int fib(int n) {
    if (n <= 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

• 時間複雜度：由於產生大量的重複子問題，遞迴呼叫樹的節點數與費氏數成正比，時間複雜度為 $O(2^n)$（更精確為 $\Theta(\phi^n)$，其中黃金比例 $\phi \approx 1.618$）。
• 空間複雜度：最大遞迴呼叫深度等於呼叫樹的高度，堆疊空間複雜度為 $O(n)$。

2. 由底向上遞推計算

利用關係式 $C(n) = 1 + C(n-1) + C(n-2)$ 逐項推導：

• $C(1) = 1$
• $C(2) = 1$
• $C(3) = 1 + C(2) + C(1) = 1 + 1 + 1 = 3$
• $C(4) = 1 + C(3) + C(2) = 1 + 3 + 1 = 5$
• $C(5) = 1 + C(4) + C(3) = 1 + 5 + 3 = 9$
• $C(6) = 1 + C(5) + C(4) = 1 + 9 + 5 = 15$

3. 遞迴呼叫樹展開驗算

將 fib(6) 的展開樹繪製如下，樹中的每個節點即代表一次函式呼叫：

本題需要將所有給定的數字轉換為相同的進位制（例如十進制），然後進行比較以找出最大的數字。

我們逐一轉換：

(A) 11011011 in 2's complement
這是一個 8 位元的二補數。最高位是 1，表示為負數。
為了求其值，我們可以先求其反碼（1's complement），然後加 1，最後取負。
反碼：00100100
加 1：00100101
轉換為十進制：$0 \times 2^7 + 0 \times 2^6 + 1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 32 + 4 + 1 = 37$。
所以，這個二補數的值是 -37。

(B) 10010110 in binary
這是一個純二進制數字（通常指無符號數）。
$1 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0$
$= 128 + 0 + 0 + 16 + 0 + 4 + 2 + 0 = 150$。

本題考查排序演算法在最壞情況下的時間複雜度與空間複雜度。題目中提到「same time complexity in best, average and worst cases」，這句話可能有些誤導，因為並非所有列出的排序演算法在三種情況下時間複雜度都相同。我們應該關注的是「worst case」下的時間和空間複雜度。

我們逐一分析各個排序演算法在最壞情況下的複雜度：

• (A) Selection Sort (選擇排序)

  • 時間複雜度 (Worst Case)：$O(n^2)$。無論輸入如何，都需要進行 $n-1$ 次外層迴圈和 $n-1$ 次內層迴圈來尋找最小值。
  • 空間複雜度 (Worst Case)：$O(1)$。只需要常數額外的空間來儲存臨時變數。

• (B) Quick Sort (快速排序)

  • 時間複雜度 (Worst Case)：$O(n^2)$。當輸入數列已經排序或逆序排序，且 pivot 選擇不佳時，會發生這種情況。
  • 空間複雜度 (Worst Case)：$O(n)$。這是由於遞迴呼叫堆疊所致。在最壞情況下，遞迴深度可能達到 n。

• (C) Merge Sort (合併排序)

  • 時間複雜度 (Worst Case)：$O(n \log n)$。合併排序的分割和合併步驟總是平均執行，因此其時間複雜度在最佳、平均和最壞情況下都是 $O(n \log n)$。
  • 空間複雜度 (Worst Case)：$O(n)$。需要額外的空間來儲存合併過程中產生的臨時數列。

• (D) Insertion Sort (插入排序)

  • 時間複雜度 (Worst Case)：$O(n^2)$。當輸入數列逆序排序時，每個元素都需要與前面所有元素進行比較和移動。
  • 空間複雜度 (Worst Case)：$O(1)$。只需要常數額外的空間。

本題需要根據給定的邏輯值，計算每個邏輯表達式的值，並找出與其他不同的那個。
給定：A = True (T), B = False (F), C = False (F), D = True (T)。

我們逐一計算每個選項：

(A) (A OR B) AND (C AND D)

• A OR B = T OR F = T
• C AND D = F AND T = F
• (A OR B) AND (C AND D) = T AND F = F

(B) (A NAND B) XOR (C NOR D)

• A NAND B = NOT (A AND B) = NOT (T AND F) = NOT (F) = T
• C NOR D = NOT (C OR D) = NOT (F OR T) = NOT (T) = F
• (A NAND B) XOR (C NOR D) = T XOR F = T

(C) (A XOR (NOT B)) XOR (C AND D)

• NOT B = NOT F = T
• A XOR (NOT B) = T XOR T = F
• C AND D = F AND T = F
• (A XOR (NOT B)) XOR (C AND D) = F XOR F = F

(D) (A AND D) XOR (B OR C)

• A AND D = T AND T = T
• B OR C = F OR F = F
• (A AND D) XOR (B OR C) = T XOR F = T

我們計算的結果如下：
(A) F
(B) T
(C) F
(D) T

本題考查 C/C++ 語言中各種運算符的優先級。運算符優先級決定了在一個表達式中，哪些運算會先被執行。優先級越高的運算符，越先被執行。

我們來列出這些運算符的優先級（從高到低）：

• (A) ++ (遞增運算符)：

  • 前綴遞增 (++x) 和後綴遞增 (x++) 都屬於最高優先級的運算符之一。它們的優先級高於算術運算符、關係運算符和邏輯運算符。

• (B) && (邏輯 AND 運算符)：

  • 邏輯 AND (&&) 的優先級低於算術運算符和關係運算符，但高於賦值運算符。

核心觀念

本題考查 C++ 巢狀 for 迴圈的執行順序，以及：

• break：立即結束目前所在的內層迴圈。
• continue：跳過本次迴圈剩餘敘述，直接執行迴圈更新式。
• 迴圈變數可以在迴圈本體內被修改。
• for 迴圈的執行順序為：

$$\text{初始化} \rightarrow \text{條件判斷} \rightarrow \text{迴圈本體} \rightarrow \text{更新式}$$

外層迴圈每輪結束時會執行 i++；內層迴圈每輪結束時會執行 j++。

---

解題方法

逐步追蹤 $i$、$j$ 與 $a$ 的變化。

第一階段：$i=0$

此時 i > 3 不成立，而且：

$$i \% 7 = 0$$

因此每次執行：

i += i % 7;

都不會改變 $i$。

當 $j=0,1,2$ 時，會正常執行：

i += i%7;
a++;

所以 $a$ 增加 $3$ 次。

當 $j=3,4,5,6,7$ 時，符合：

j > 2 && j < 8

執行 continue，因此不會執行 a++。但內層 for 的更新式 j++ 仍然會執行。

當 $j=8$ 時，不符合 continue，也不符合 j > 8，因此正常執行一次 a++。

當 $j=9$ 時：

j > 8 && i > 0

中的 i > 0 不成立，因此仍然執行一次 a++。

所以 $i=0$ 時：

$$a=3+1+1=5$$

內層迴圈結束後，外層更新式使：

$$i=0+1=1$$

---

第二階段：$i=1$

內層迴圈從 $j=0$ 開始。

$j=0$

此時：

$$i \leftarrow i+i\%7=1+1=2$$

並執行 a++：

$$a=6$$

內層更新後 $j=1$。

$j=1$

此時：

$$i \leftarrow 2+2\%7=2+2=4$$

並執行 a++：

核心觀念

本題考查「圓形與軸對齊正方形的碰撞偵測」。

正方形不旋轉，因此其邊與座標軸平行。已知：

• 圓心：$(c_x,c_y)$
• 圓半徑：$r$
• 正方形左上角：$(s_x,s_y)$
• 正方形邊長：$e$

採用一般 2D 遊戲座標系統，正方形範圍為：

$$s_x \le x \le s_x+e$$ $$s_y \le y \le s_y+e$$

圓與正方形碰撞的條件，是「圓心到正方形最近點的距離」不大於半徑：

$$d \le r$$

為避免使用平方根，可將兩邊平方：

$$d^2 \le r^2$$

因此只要計算圓心到正方形最近點的水平、垂直距離即可。

解題方法

1. 判斷圓心與正方形的相對位置

圓心在水平方向的距離定義如下：

• 若圓心在正方形左側，水平距離為 $s_x-c_x$
• 若圓心在正方形右側，水平距離為 $c_x-(s_x+e)$
• 若圓心位於正方形的水平範圍內，水平距離為 $0$

同理，垂直距離為：

• 若圓心在正方形上方，垂直距離為 $s_y-c_y$
• 若圓心在正方形下方，垂直距離為 $c_y-(s_y+e)$
• 若圓心位於正方形的垂直範圍內，垂直距離為 $0$

設這兩個距離分別為 $d_x$ 與 $d_y$，則圓心到正方形最近點的距離平方為：

$$d^2=d_x^2+d_y^2$$

2. 使用平方距離判斷碰撞

若：

$$d_x^2+d_y^2 \le r^2$$

代表圓與正方形相交或剛好接觸，回傳 true；否則回傳 false。

參考程式碼

以下使用 C 語言撰寫，僅使用題目允許直接使用的 pow 函式：

本題考查物件導向程式設計 (OOP) 中的繼承 (Inheritance) 概念、存取修飾符 (Access Modifiers) 的差異，以及不同繼承方式對基底類別成員可存取性的影響。

1. 繼承 (Inheritance) 是什麼？

繼承是物件導向程式設計中的一個核心概念，它允許一個類別（稱為子類別、衍生類別或派生類別）繼承另一個類別（稱為父類別、基底類別或超類別）的屬性（成員變數）和行為（成員函數）。

• 目的：

  • 程式碼重用 (Code Reusability)：避免重複編寫相同的程式碼。
  • 建立「is-a」關係：表示一種層次結構，例如「狗」is-a「動物」。
  • 多型 (Polymorphism)：允許在衍生類別中覆寫基底類別的方法，實現行為的多樣化。

• 運作方式：

  • 子類別獲得父類別的非私有成員。
  • 子類別可以添加新的成員（變數和函數）。
  • 子類別可以修改（覆寫）從父類別繼承來的成員函數。

2. public, private, protected 成員的差異

這些存取修飾符決定了類別成員（變數和函數）在類別內部、子類別以及外部程式碼中的可存取性。

• public (公開)：

  • 類別內部：可存取。
  • 子類別：可存取。
  • 外部程式碼：可存取。
  • 這是預設的存取層級（在某些語言中，如 Java，類別成員預設是 package-private，C++ 中類別成員預設是 private）。

• private (私有)：

  • 類別內部：可存取。
  • 子類別：不可存取。
  • 外部程式碼：不可存取。
  • 私有成員僅限於定義它們的類別內部使用，用於封裝實現細節。

• protected (保護)：

  • 類別內部：可存取。
  • 子類別：可存取。
  • 外部程式碼：不可存取。
  • 保護成員允許子類別存取，同時保護它們不被外部程式碼直接存取，常用於繼承結構中。

3. 不同繼承方式對基底類別成員可存取性的影響

在 C++ 中，當一個類別繼承另一個類別時，基底類別的成員的可存取性會根據繼承方式（public, private, protected）而有所不同。

假設我們有一個基底類別 Base，其中包含 public, protected, private 成員。我們有一個衍生類別 Derived，它通過不同的繼承方式繼承 Base。

基底類別成員	繼承方式 (Base Class Member)	衍生類別 (Derived Class) 中的可存取性	外部程式碼 (Outside Code) 中的可存取性
public	public inheritance	public	public
public	protected inheritance	protected	private
public	private inheritance	private	private
protected	public inheritance	protected	private

本題要求使用二元搜尋法（Binary Search）在一個給定的數列中尋找數字 18，並繪製搜尋過程圖示，同時提供遞迴版本的二元搜尋程式碼。

給定的數列（已排序）：b = {1, 5, 9, 18, 25, 36, 42, 74, 89, 97}。
我們要尋找的目標值是 target = 18。

二元搜尋法的基本原理：
二元搜尋法適用於已排序的數列。它通過不斷將搜尋範圍縮小一半來進行搜尋。

1. 找到搜尋範圍的中間元素。
2. 將目標值與中間元素進行比較。
3. 如果目標值等於中間元素，則搜尋成功，找到目標。
4. 如果目標值小於中間元素，則在中間元素的左半部分繼續搜尋。
5. 如果目標值大於中間元素，則在中間元素的右半部分繼續搜尋。
6. 重複步驟 1-5，直到找到目標或搜尋範圍縮小到空。

1. 搜尋過程圖示 (Procedure Diagram):

我們用 low 指向搜尋範圍的起始索引，high 指向搜尋範圍的結束索引。
數列 b 的索引從 0 開始。
b = {1, 5, 9, 18, 25, 36, 42, 74, 89, 97}
Indices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Target = 18

第一次搜尋 (Iteration 1):

• low = 0, high = 9
• mid = floor((low + high) / 2) = floor((0 + 9) / 2) = floor(4.5) = 4
• b[mid] = b[4] = 25
• 比較 target (18) 和 b[mid] (25)：18 < 25。
• 目標值較小，所以目標在左半部分。更新 high = mid - 1 = 4 - 1 = 3。
• 搜尋範圍：[low=0, high=3]。數列部分：{1, 5, 9, 18}。

第二次搜尋 (Iteration 2):

• low = 0, high = 3
• mid = floor((low + high) / 2) = floor((0 + 3) / 2) = floor(1.5) = 1
• b[mid] = b[1] = 5
• 比較 target (18) 和 b[mid] (5)：18 > 5。
• 目標值較大，所以目標在右半部分。更新 low = mid + 1 = 1 + 1 = 2。
• 搜尋範圍：[low=2, high=3]。數列部分：{9, 18}。

第三次搜尋 (Iteration 3):

• low = 2, high = 3
• mid = floor((low + high) / 2) = floor((2 + 3) / 2) = floor(2.5) = 2
• b[mid] = b[2] = 9
• 比較 target (18) 和 b[mid] (9)：18 > 9。
• 目標值較大，所以目標在右半部分。更新 low = mid + 1 = 2 + 1 = 3。
• 搜尋範圍：[low=3, high=3]。數列部分：{18}。

第四次搜尋 (Iteration 4):

• low = 3, high = 3
• mid = floor((low + high) / 2) = floor((3 + 3) / 2) = floor(3) = 3
• b[mid] = b[3] = 18
• 比較 target (18) 和 b[mid] (18)：18 == 18。
• 搜尋成功！找到目標值 18，其索引為 3。

圖示說明（可視化）：

Initial Array: [ 1,  5,  9, 18, 25, 36, 42, 74, 89, 97 ]
Indices:       [ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9 ]
Target: 18

Iteration 1:
low=0, high=9, mid=4 (value=25)
18 < 25, search left half. New range: low=0, high=3
[ 1,  5,  9, 18 ] | 25, 36, 42, 74, 89, 97

Iteration 2:
low=0, high=3, mid=1 (value=5)
18 > 5, search right half. New range: low=2, high=3
[ 1,  5 ] | [ 9, 18 ] | 25, 36, 42, 74, 89, 97

Iteration 3:
low=2, high=3, mid=2 (value=9)
18 > 9, search right half. New range: low=3, high=3
[ 1,  5,  9 ] | [ 18 ] | 25, 36, 42, 74, 89, 97

Iteration 4:
low=3, high=3, mid=3 (value=18)
18 == 18. Found! Index is 3.

2. 遞迴版本的二元搜尋程式碼 (Recursive Binary Search Code):