109 年 國立成功大學會計學研究所乙組《計算機概論》

此題考查儲存裝置的物理特性。題幹詢問哪種儲存系統不需要物理運動。

• A. Magnetic tape (磁帶): 磁帶需要馬達轉動捲軸來讀寫資料，有物理運動。
• B. Magnetic disk (磁碟): 磁碟（如硬碟、軟碟）需要盤片旋轉，磁頭也需要移動，有物理運動。

此題考查作業系統中「上下文切換」(Context Switch) 的概念。上下文切換是當作業系統在多個行程(Process)之間切換執行時，保存當前行程的執行狀態，並載入下一個要執行的行程的執行狀態的過程。

• A. Interrupt (中斷): 中斷是觸發上下文切換的常見原因之一。當硬體或軟體發生事件（如 I/O 完成、定時器到期、程式錯誤）時，會產生中斷，作業系統會響應中斷並可能進行上下文切換。

此題考查 TCP/IP 協定模型的各層功能，特別是訊息重組的部分。TCP/IP 模型通常包含應用層、傳輸層、網路層和鏈結層（或網路介面層）。

• A. Application Layer (應用層): 處理應用程式的特定需求，如 HTTP, FTP, DNS 等。它不負責訊息的分段與重組。
• B. Transport Layer (傳輸層): 負責端對端(end-to-end)的資料傳輸，提供可靠或不可靠的傳輸服務。

此題考查網路安全相關組織與技術，判斷何者主要目的「非」在於增強安全性。

• A. ICANN (Internet Corporation for Assigned Names and Numbers): 網際網路名稱與數字位址分配機構。ICANN 的主要職責是協調全球網際網路的域名系統 (DNS) 和 IP 位址的分配。雖然 DNS 的安全（如 DNSSEC）是其關注點之一，但其核心宗旨是網際網路的協調管理與發展，而非直接的安全性增強。

核心觀念

本題考的是「迴圈不變量」（loop invariant）。

迴圈不變量是指：在迴圈開始前，以及每次執行迴圈主體後、下一次進行終止條件測試前，都持續成立的敘述。

程式如下：

X = 3;
while (X < 5) do
    X = X + 2

終止條件為 $X < 5$。每次進入迴圈主體時，$X$ 增加 $2$。

解題方法

依照程式執行流程追蹤 $X$ 的值：

1. 初始設定：

   $X=3$

2. 第一次測試：

   $3<5$

   條件成立，執行迴圈主體：

   $X=3+2=5$

3. 第二次測試：

   $5<5$

   條件不成立，迴圈終止。

因此，在每一次進行終止條件測試時，$X$ 的可能值為 $3$ 或 $5$，兩者皆符合：

$X\leq 5$

所以迴圈不變量為 $X\leq 5$。

選項分析

A. $X>5$

錯誤。

此題考查物件導向程式設計 (Object-Oriented Programming, OOP) 的核心概念。OOP 的三大基本特徵通常是：封裝 (Encapsulation)、繼承 (Inheritance) 和多型 (Polymorphism)。

• A. Inheritance (繼承): 允許一個類別（子類別）繼承另一個類別（父類別）的屬性和方法，實現程式碼的重用和層次結構。這是 OOP 的核心概念。
• B. Resolution (解析): "Resolution" 這個詞在程式設計中有不同的含義，例如「連結時解析」(link-time resolution) 或「名稱解析」(name resolution)，在某些上下文中可能與物件有關，但它不是 OOP 的核心、獨立的原則或特徵。

此題考查軟體開發方法的歷史演進，詢問哪一種方法是最古老的。

• A. Component architecture (組件架構): 組件化軟體開發是一種較現代的開發模式，強調將軟體分解為可重用、可獨立部署的組件。
• B. Waterfall model (瀑布模型): 瀑布模型是一種早期的、線性的軟體開發模型，將開發過程分為需求分析、設計、實現、測試、部署和維護等階段，每個階段按順序完成後進入下一階段。它在 1970 年代由 Winston W. Royce 提出，是早期最為經典和廣泛使用的開發模型之一。

核心觀念

本題考查二元樹的「高度」與各層最多節點數。

依本題選項與一般考試慣例，「longest path」是指由根節點到最深葉節點的最長路徑；題目說該路徑包含 4 個節點，表示二元樹共有 4 層：

• 第 1 層：最多 $1$ 個節點
• 第 2 層：最多 $2$ 個節點
• 第 3 層：最多 $4$ 個節點
• 第 4 層：最多 $8$ 個節點

二元樹每個節點最多有 2 個子節點，因此第 $i$ 層最多有 $2^{i-1}$ 個節點。

解題方法

要使整棵樹的節點數最大，在不增加最長路徑長度的前提下，每一層都必須填滿，形成高度為 4 的滿二元樹。

因此最多節點數為：

$$1+2+4+8=15$$

也可使用等比級數公式：

$$1+2+2^2+2^3=2^4-1=15$$

所以整棵樹最多有 15 個節點。

選項分析

• A. 4：錯誤。
  4 是最長路徑所包含的節點數，不是整棵樹的最大節點數。若每一層只有一個節點，整棵樹才會只有 4 個節點。

此題考查 SQL 查詢語言（或類似的關係代數操作）的執行過程。

給定關係 X：

A	B	C
2	5	7
3	3	3
4	4	2
5	2	8

查詢步驟：

1. TEMP ← SELECT from X where B = C:
   這個步驟從關係 X 中選取 B 欄位的值等於 C 欄位值的那些列。
   我們檢查每一列：
   • 第一列：B=5, C=7。 $5 \neq 7$。不選取。
   • 第二列：B=3, C=3。 $3 = 3$。選取。
   • 第三列：B=4, C=2。 $4 \neq 2$。不選取。

此題考查記憶體系統的特性。題幹詢問哪種記憶體系統能夠提供「相關資訊」。

• A. Read-only memory (ROM): ROM 是唯讀記憶體，通常儲存固定的程式碼或資料，不能隨機存取特定「相關」資訊。
• B. Associative memory (關聯記憶體): 關聯記憶體（也稱為內容尋址記憶體, Content-Addressable Memory, CAM）是一種特殊的記憶體，它允許使用者通過記憶體內容的一部分或全部來進行搜尋，而不是通過記憶體位址。這意味著它可以根據「關聯性」來檢索資訊。例如，可以搜尋所有包含特定數值或模式的條目。因此，它能夠提供相關資訊。

此題考查二元樹的記憶體表示法以及如何根據記憶體內容繪製樹狀結構。

題目給定：

• 每個節點包含三個儲存單元：資料、左子節點指標、右子節點指標。
• Nil pointer (空指標) 用 00 表示。
• 樹的根節點指標是 53。
• 記憶體內容如下表所示：

  Address	Contents
  50	AA
  51	56
  52	00
  53	BB
  54	00
  55	50
  56	CC
  57	00
  58	00

解題步驟：

1. 找到根節點： 根節點指標是 53。所以，我們從位址 53 開始。
2. 解析根節點：
   • 位址 53 儲存的內容是 BB。這代表根節點的資料是 BB。
   • 下一個儲存單元（位址 53+1 = 54，假設每個節點佔用 3 個儲存單元，但題目中 Memory Map 顯示 Address 是連續的，所以我們需要根據內容來推斷。題目說「每個節點包含三個cell」，這通常意味著三個連續的記憶體位置。例如，如果節點起始於 Address X，則 Data 在 X，Left Child Pointer 在 X+1，Right Child Pointer 在 X+2。但這裡的 Memory Map 是 Address -> Contents，所以我們需要看 Address 53 的內容，然後推斷它的左右子節點指標在哪裡。
   • 從題目描述「每個節點包含三cells」，我們可以推斷，如果一個節點的資料在 Address i，那麼其左子節點指標在 i+1，右子節點指標在 i+2。
   • 根節點指標是 53。所以，節點的資料是 Contents[53] = BB。
   • 左子節點指標是 Contents[53+1] = Contents[54] = 00。

此題考查 SQL 查詢語法，涉及多表連接 (JOIN) 和條件篩選 (WHERE)。

給定三個關係 (表格)：
Relation X:

A	B
7	s
3	z
1	u

Relation Y:

C	D
t	4
r	2

Relation Z:

E	F
7	w
3	q

查詢語句：

select X.B, Y.C, Z.F
from X, Y, Z
where X.A > Y.D and X.A = Z.E

解題步驟：

1. FROM 子句: from X, Y, Z 表示將 X, Y, Z 三個表進行笛卡爾積 (Cartesian Product) 的操作。這意味著 X 的每一行都與 Y 的每一行組合，然後再與 Z 的每一行組合。
   總共有 $3 \times 2 \times 2 = 12$ 種組合。

2. WHERE 子句: where X.A > Y.D and X.A = Z.E 這是篩選條件，用來從笛卡爾積的結果中找出符合條件的行。
   我們需要同時滿足兩個條件：

   • X.A > Y.D
   • X.A = Z.E

   讓我們逐一檢查 X 中的每一行，並與 Y 和 Z 中的行進行組合和篩選：

   • 考慮 X 的第一行: X = (A=7, B=s)

     • 與 Y 的第一行 Y = (C=t, D=4) 組合：

       • 檢查 X.A > Y.D：7 > 4 (True)
       • 現在需要找 Z 中 Z.E = X.A (即 Z.E = 7) 的行。
       • 在 Z 中，Z.E = 7 的是第一行 Z = (E=7, F=w)。
       • 檢查 X.A = Z.E：7 = 7 (True)
       • 兩個條件都為 True。所以，組合 (X=7, B=s), (Y=t, D=4), (Z=7, F=w) 符合條件。
       • 從這個組合中選取 X.B, Y.C, Z.F，得到 (s, t, w)。

     • 與 Y 的第二行 Y = (C=r, D=2) 組合：

       • 檢查 X.A > Y.D：7 > 2 (True)

此題考查中綴表達式 (Infix Expression) 轉換為抽象語意樹 (Abstract Syntax Tree, AST)、後綴表達式 (Postfix Expression) 和前綴表達式 (Prefix Expression)。

給定的中綴表達式是：A - B * (-C + - 3.5)

轉換原則：

• 運算符的優先級：括號 > 乘除 > 加減。
• 相同優先級的運算符，按照從左到右的順序處理（除指數運算符外，這裡沒有）。

步驟一：建立抽象語意樹 (AST)

1. 掃描表達式：

   • A: 變數，葉節點。
   • -: 運算符。
   • B: 變數，葉節點。
   • *: 運算符。
   • (: 開括號，標誌著一個子表達式的開始。
   • -: 運算符。
   • C: 變數，葉節點。
   • +: 運算符。
   • -: 這是負號，可以看作是單目運算符，或者與後面的數字組合。這裡 - 3.5 是一個負數。
   • 3.5: 數字，葉節點。

2. 處理運算符優先級和括號：

   • 表達式中的最高優先級操作是括號內的 (-C + - 3.5)。
   • 在括號內，-C 是單目減法，+ 是二元加法，- 3.5 是負數。
   • -C 的優先級最高（或說，它緊跟著 (），然後是 +。
   • 最後，整個括號內的結果會被 * 運算符與 B 相乘。
   • 整個 B * (...) 的結果會被 - 運算符與 A 相減。

3. 繪製 AST：

   • 根節點是最低優先級的運算符：-。
   • 左子節點是 A。
   • 右子節點是 B * (-C + - 3.5) 這個子表達式的根節點，即 *。
   • * 節點的左子節點是 B。
   • * 節點的右子節點是括號內表達式的根節點，即 +。
   • + 節點的左子節點是 -C。
   • + 節點的右子節點是 - 3.5。
   • -C 節點的子節點是 C (單目減法)。
   • - 3.5 節點的子節點是 3.5 (負數)。

   AST 結構（文字表示）：

     -
    / \
   A   *
      / \
     B   +
        / \
       -   -
      /   /
     C   3.5
   

   視覺化 (文字描述)：
   頂部是 - 節點。
   其左子節點是 A。
   其右子節點是 * 節點。
   * 節點的左子節點是 B。
   * 節點的右子節點是 + 節點。
   + 節點的左子節點是單目 - 節點（其子節點為 C）。
   + 節點的右子節點是單目 - 節點（其子節點為 3.5）。

(a) Tree (抽象語意樹):
如上圖所示。

步驟二：轉換為後綴表達式 (Postfix Expression)

使用堆疊 (stack) 方法來轉換。
表達式：A - B * (-C + - 3.5)

1. 掃描表達式，遇到運算數直接輸出。

2. 遇到左括號 ( 壓入堆疊。

3. 遇到右括號 )，將堆疊中運算符彈出直到遇到左括號 (，然後將左括號彈出。

4. 遇到運算符 op1：

   • 如果堆疊為空，或者堆疊頂部是左括號，則將 op1 壓入堆疊。
   • 否則，比較 op1 與堆疊頂部運算符 op2 的優先級。
     • 如果 op1 優先級高於 op2，則將 op1 壓入堆疊。
     • 如果 op1 優先級低於或等於 op2，則彈出 op2 並輸出，然後重複此比較過程，直到滿足上述條件，最後將 op1 壓入堆疊。
   • 單目減法 (如 -C) 處理方式：通常視為一個特殊的二元運算符，或者在解析時就與運算數結合。在這裡，為了方便轉換，我們將 -C 視為一個組合，或者將單目減法視為一個高優先級運算符。為了簡化，我們將 -C 視為一個單元，將 - 3.5 視為一個單元。

   讓我們更嚴謹地處理括號和單目減法：
   原式：A - B * ( (-C) + (-3.5) ) (為了清晰，加上了隱含的括號和單目減法標記)

此題考查陣列在記憶體中的儲存方式，以及位址計算。

題目給定：

• 陣列 A 儲存的是 4 位元組 (byte) 的實數 (real numbers)。這表示陣列中每個元素的記憶體大小是 4 bytes。
• A(100) 是陣列 A 的第 100 個元素（假設索引從 0 開始，則 A(100) 是第 101 個元素；如果索引從 1 開始，則是第 100 個元素。常見情況下，這裡的 100 和 900 指的是索引，我們假設索引從 0 開始，則 A(100) 是索引為 100 的元素，A(900) 是索引為 900 的元素。但題目也可能將 A(100) 理解為第 100 個元素，A(900) 為第 900 個元素。為了計算方便，我們採用「索引」的理解，即 A[100] 和 A[900]）。
• A(100) 的記憶體位址是 $(1011)_{16}$ (十六進位)。

要求：

• A(900) 的記憶體位址。

解題步驟：

1. 計算索引差值：
   我們要找的元素 A(900) 相對於已知元素 A(100)，索引的差距是 $900 - 100 = 800$。

2. 計算記憶體位址差距：
   由於每個元素佔用 4 bytes，那麼索引差距為 800 的元素，其記憶體位址差距為：
   位址差距 = (索引差值) $\times$ (每個元素的大小)
   位址差距 = $800 \times 4$ bytes = $3200$ bytes。

3. 將位址差距轉換為十六進位：
   我們需要將十進位的 3200 轉換為十六進位。
   $3200 \div 16 = 200$ 餘 $0$
   $200 \div 16 = 12$ 餘 $8$
   $12 \div 16 = 0$ 餘 $12$ (C)
   將餘數從下往上讀，得到十六進位的 C80。
   所以，位址差距是 $(C80)_{16}$ bytes。

4. 計算 A(900) 的位址：
   A(900) 的位址是 A(100) 的位址加上位址差距。
   A(100) 的位址是 $(1011)_{16}$。
   A(900) 的位址 = $(1011)_{16} + (C80)_{16}$。

   進行十六進位加法：
   $1011_{16}$

   • $C80_{16}$

   ---

   從右邊第一位開始：$1 + 0 = 1$
   第二位：$1 + 8 = 9$

此題考查遞迴 (Recursion) 函式的執行過程。

給定的遞迴程序 xxx(N)：

procedure xxx (N)
  print the value of N;
  if (N < 5) then (apply the procedure xxx to the value N + 2);
  print the value of N

初始呼叫：xxx(0)

我們需要追蹤程式的執行流程，特別是列印 (print) 的順序。

1. xxx(0) 呼叫：

   • print the value of N; -> 列印 0。
   • if (N < 5): 0 < 5 為 True。
   • 執行 apply the procedure xxx to the value N + 2;，即呼叫 xxx(0 + 2)，也就是 xxx(2)。

2. xxx(2) 呼叫 (由 xxx(0) 呼叫)：

   • print the value of N; -> 列印 2。
   • if (N < 5): 2 < 5 為 True。
   • 執行 apply the procedure xxx to the value N + 2;，即呼叫 xxx(2 + 2)，也就是 xxx(4)。

3. xxx(4) 呼叫 (由 xxx(2) 呼叫)：

   • print the value of N; -> 列印 4。
   • if (N < 5): 4 < 5 為 True。
   • 執行 apply the procedure xxx to the value N + 2;，即呼叫 xxx(4 + 2)，也就是 xxx(6)。

4. xxx(6) 呼叫 (由 xxx(4) 呼叫)：

   • print the value of N; -> 列印 6。