110 年 國立臺灣大學圖書資訊系碩士班《電子計算機概論》

本題考查排序演算法的定義。題目描述的排序過程，是將未排序數列的元素逐一取出，插入到已排序數列的正確位置，保持已排序數列的有序性。這正是插入排序法 (Insertion Sort) 的核心概念。

• 泡沫排序法 (Bubble Sort): 相鄰元素比較交換，重複進行直到排序完成。

本題考查軟體測試的兩種基本方法：白箱測試與黑箱測試。

• 白箱測試 (White-box Testing): 測試者了解程式的內部結構、邏輯、程式碼，並根據這些資訊來設計測試案例。目標是測試程式碼的覆蓋率和內部邏輯的正確性。
• 黑箱測試 (Black-box Testing): 測試者不關心程式的內部實現細節，僅從外部觀察程式的行為，根據規格書的要求，測試程式的輸入與輸出是否符合預期。這就像操作一個「黑箱」，不知道裡面發生了什麼。

本題考查資料庫基礎概念，特別是 SQL 語法、DDL/DML 的功能以及主鍵的特性。

• 選項 (A): SQL 的 SELECT * FROM table_name; 語句中，* (星號) 是萬用字元 (wildcard)，表示「選取所有欄位 (all columns)」。它並不是用來查詢欄位內容中帶有星號的資料。若要查詢特定字串，則需使用 LIKE 運算子，例如 WHERE column_name LIKE '%*%';。因此，此敘述是錯誤的。

• 選項 (B): 資料定義語言 (DDL) 用於定義和修改資料庫結構，例如建立表格 (CREATE TABLE)、修改表格 (ALTER TABLE)、刪除表格 (DROP TAB

本題考查電腦如何使用二進位表示整數，特別是負數的表示法：1 的補數 (1's complement) 和 2 的補數 (2's complement)。

假設我們使用 N 個位元來表示。

• 1 的補數 (1's Complement):

  • 正數的表示法與原碼相同。
  • 負數的表示法是將其對應正數的二進位表示法逐位反轉 (0 變 1，1 變 0)。
  • 特性:
    • 存在兩種 0 的表示法：全 0 表示 +0，全 1 表示 -0。
    • 例如，若 N=4：
      • +0: 0000
      • -0: 1111
      • +1: 0001
      • -1: 1110 (對 +1 的 0001 反轉)

• 2 的補數 (2's Complement):

  • 正數的表示法與原碼相同。
  • 負數的表示法是將其對應正數的二進位表示法逐位反轉後，再加 1。或者，可以看作是 1 的補數加 1。
  • 特性:
    • 只有一種 0 的表示法：全 0 表示 0。
    • 表示範圍比 1 的補數多一個負數。
    • 例如，若 N=4：
      • +0: 0000
      • +1: 0001
      • -1: 1111 (對 +1 的 0001，反轉為 1110，加 1 為 1111)

本題考查 ASCII 碼的特性以及不同進制之間的轉換。

ASCII (American Standard Code for Information Interchange) 碼是一個標準的字元編碼。7 位元的 ASCII 碼可以表示 2⁷ = 128 個字元。其中，大寫字母 'A' 到 'Z' 是連續編碼的。

題目給了以下資訊：

1. ASCII 碼使用 7 bits。
2. 'B' 的 ASCII 碼是 66₁₀ (十進制)。
3. 已知 'Z' > 'B' (在 ASCII 碼的順序上)。
4. 要求 'Z' 的 ASCII 碼。

由於大寫字母 'A' 到 'Z' 在 ASCII 碼中是連續編碼的，我們知道：

• 'A' 的 ASCII 碼是 65₁₀。
• 'B' 的 ASCII 碼是 66₁₀。
• 'C' 的 ASCII 碼是 67₁₀。
• ...
• 'Z' 的 ASCII 碼是 'A' 的 ASCII 碼加上 ('Z' - 'A') 的差值。
  • 'Z' - 'A' = 25 (因為 Z 是第 26 個字母，A 是第 1 個，26 - 1 = 25)。
  • 所以，'Z' 的 ASCII 碼 = 'A' 的 ASCII 碼 + 25 = 65₁₀ + 25 = 90₁₀。

或者，我們也可以從 'B' 開始計算：

• 'B' 是第 2 個大寫字母，ASCII 碼是 66₁₀。
• 'Z' 是第 26 個大寫字母。

CPU (Central Processing Unit) 是電腦的核心，負責執行指令和處理數據。其基本架構包含幾個關鍵單元，主要負責指令的獲取、解碼、執行和數據的處理。

CPU 的基本架構主要包含以下幾個核心單元：

1. 控制單元 (Control Unit, CU):

   • 功能: 負責協調和指揮電腦各部件的工作。它從記憶體中取出指令，對指令進行解碼，並產生控制信號，指示其他單元（如算術邏輯單元、記憶體、輸入/輸出設備）執行相應的操作。它就像是 CPU 的「指揮官」。
   • 主要工作:
     • 指令的提取 (Fetch): 從記憶體讀取下一條指令。
     • 指令的解碼 (Decode): 識別指令的類型和操作。
     • 指令的執行 (Execute): 產生控制信號，協調其他單元執行指令。
     • 中斷處理 (Interrupt Handling): 處理來自外部設備或內部錯誤的中斷信號。

2. 算術邏輯單元 (Arithmetic Logic Unit, ALU):

   • 功能: 負責執行所有的算術運算 (加、減、乘、除等) 和邏輯運算 (AND, OR, NOT, XOR, 比較等)。
   • 主要工作:
     • 接收來自控制單元的指令和來自暫存器的數據。
     • 執行指定的算術或邏輯運算。
     • 將運算結果存入暫存器或送往記憶體。

3. 暫存器 (Registers):

   • 功能: CPU 內部的高速儲存單元，用於暫時存放指令、數據、位址和運算結果。暫存器的存取速度遠高於主記憶體，是 CPU 高速運行的關鍵。
   • 常見的暫存器類型:
     • 程式計數器 (Program Counter, PC): 儲存下一條要執行的指令的記憶體位址。

核心觀念

本題比較兩種程式設計典範：

• 結構化程式設計（Structured Programming）：以「程序、函式與控制流程」為主要組織方式。
• 物件導向程式設計（Object-Oriented Programming, OOP）：以「物件、類別與物件間互動」為主要組織方式。

兩者都追求模組化、可讀性、可維護性與降低程式複雜度，但分解問題的角度不同。

解題方法

回答此題可從以下面向比較：

1. 程式的基本組成單位。
2. 問題分解方式。
3. 資料與操作的關係。
4. 程式重複使用方式。
5. 對大型系統維護與擴充的支援。

結構化程式設計

結構化程式設計以「演算法與控制流程」為核心，將大型問題逐步分解成多個程序或函式，再以函式呼叫完成整體功能。

其基本控制結構通常包括：

1. 循序結構：依照程式碼順序逐步執行。
2. 選擇結構：依條件選擇不同執行路徑，例如 if、switch。
3. 迴圈結構：重複執行某段程式，例如 for、while。

結構化程式設計強調避免任意的 goto 跳躍，使程式流程具有清楚的邏輯結構，便於閱讀、測試與除錯。

例如，計算學生平均成績時，可將程式分成：

• readScores()：讀取成績。
• calculateAverage()：計算平均值。
• printResult()：輸出結果。

這種分解方式主要是依照「要執行哪些工作」來設計程式。

物件導向程式設計

物件導向程式設計以「物件」為核心。物件同時包含：

• 狀態（state）：例如學生姓名、學號、成績。
• 行為（behavior）：例如計算平均、修改資料、顯示資訊。

類別（class）是建立物件的藍圖，物件則是類別所建立的實例（instance）。

物件導向通常包含以下重要特性：

1. 封裝（Encapsulation）

將資料與操作資料的方法包裝在同一個物件中，並限制外部直接存取內部資料。

例如，學生物件可以將成績設為私有資料，只透過 setScore() 與 getScore() 存取。如此可避免外部程式任意修改資料，並維持資料的一致性。

2. 抽象化（Abstraction）

只公開使用者需要的功能，隱藏不必要的實作細節。

例如，使用者只需呼叫：

student.calculateAverage()

不必知道平均值計算的內部流程。

3. 繼承（Inheritance）

子類別可以繼承父類別的資料與方法，再增加或修改特定功能。

例如：

Person
 ├── Student
 └── Teacher

Student 與 Teacher 都可以繼承 Person 的姓名、年齡等共同屬性。

4. 多型（Polymorphism）

相同的操作介面可以因物件類型不同而產生不同結果。

例如，draw() 可以是圖形的共同方法，但圓形、矩形各自以不同方式實作：

Shape.draw()
Circle.draw()
Rectangle.draw()

程式只需呼叫 draw()，實際執行哪一種繪圖行為由物件的實際類型決定。

兩者比較

OSI (Open Systems Interconnection) 參考模型是一個概念模型，將網路通訊的功能劃分為七個層級。每一層都為其上一層提供服務，並使用其下一層提供的服務。本題要求簡述第三層 (網路層) 和第四層 (傳輸層) 的工作。

第三層：網路層 (Network Layer)

• 核心功能: 負責將資料包 (Packet) 從來源主機傳送到目的主機，可能需要經過多個中間路由器。它主要處理「邏輯定址」和「路由選擇」。
• 主要工作:
  • 邏輯定址 (Logical Addressing): 為每個連接到網路的設備分配一個唯一的邏輯位址，例如 IP 位址 (Internet Protocol address)。這個位址與底層硬體位址 (MAC 位址) 不同，可以在不同網路之間路由。
  • 路由選擇 (Routing): 決定資料包從來源到目的地的最佳路徑。路由器 (Routers) 運行路由協議，根據位址資訊和網路拓撲，選擇下一跳 (next hop) 的路徑，將資料包轉發到下一個節點。
  • 封裝 (Encapsulation): 將傳輸層傳來的資料段 (Segment) 封裝成網路層的資料包 (Packet)，並加上網路層的標頭 (Header)，其中包含來源和目的地的邏輯位址。
  • 分段與重組 (Segmentation and Reassembly): 雖然主要工作在傳輸層，但網路層也可能需要處理不同網路之間的 MTU (Maximum Transmission Unit) 差異，進行分段和重組。
• 常見協定: IP (Internet Protocol), ICMP (Internet Control Message Protocol), OSPF, BGP (路由協議)。

第四層：傳輸層 (Transport Layer)

• 核心功能: 提供端對端 (end-to-end) 的資料傳輸服務，確保資料能夠可靠、有序地從來源程序的埠 (port) 傳送到目的程序的埠。它負責處理「可靠性」、「流量控制」和「連接管理」。
• 主要工作:

死結 (Deadlock) 是指在一個系統中，多個進程 (process) 都因等待其他進程釋放資源而陷入互相等待的狀態，導致所有進程都無法繼續執行。要處理死結，作業系統通常採用以下幾種策略，其中「預防」和「避免」是兩種主要的方法，而「檢測與恢復」是另一種處理死結的方法。題目提到「有二種處理方式」，通常是指「死結預防」與「死結避免」這兩種預先設計的方式，或者「死結檢測與恢復」與「忽略死結」。然而，最常見的分類是「預防」、「避免」、「檢測與恢復」以及「忽略」。根據題目「有二種處理方式」，最貼切的解釋是「死結預防」與「死結避免」，或是「死結檢測與恢復」與「忽略死結」。這裡我們分別闡述這幾種常見的策略，並強調最常被認為是「處理」死結的兩種核心方法。

處理死結的策略通常分為以下幾類：

1. 死結預防 (Deadlock Prevention):

   • 目標: 透過限制進程對資源的要求方式，來破壞死結發生的四個必要條件之一，從而確保死結永遠不會發生。
   • 四個必要條件:
     • 互斥 (Mutual Exclusion): 資源至少有一個是不可共享的。
     • 持有並等待 (Hold and Wait): 進程至少持有一個資源，並等待獲取其他進程持有的資源。
     • 不可剝奪 (No Preemption): 資源一旦被進程持有，就不能被強制剝奪，只能由持有者主動釋放。
     • 循環等待 (Circular Wait): 存在一個進程集合 $P = \{P_1, P_2, \dots, P_n\}$，使得 $P_1$ 等待 $P_2$ 釋放資源，$P_2$ 等待 $P_3$ 釋放資源，...，$P_n$ 等待 $P_1$ 釋放資源。
   • 預防方法 (破壞四個條件之一):
     • 破壞互斥: 對於可共享資源，則不會發生死結。但很多資源本質上是不可共享的（如印表機）。
     • 破壞持有並等待:
       • 要求所有進程在開始執行前一次性申請所有需要的資源。缺點是可能導致資源浪費和進程長時間阻塞。
       • 允許進程在持有資源時，再申請其他資源。如果申請不到，則必須釋放已持有的所有資源，然後再重新申請。
     • 破壞不可剝奪: 如果一個進程請求一個當前被其他進程佔有的資源，而該請求不能被立即滿足，則該進程必須釋放它目前持有的所有資源。
     • 破壞循環等待:
       • 對所有資源進行編號。
       • 要求所有進程按順序申請資源。例如，如果一個進程已經佔有了編號為 $i$ 的資源，那麼它只能申請編號大於 $i$ 的資源。這樣可以避免資源申請的循環。

2. 死結避免 (Deadlock Avoidance):

   • 目標: 在不破壞死結發生條件的情況下，動態地檢查資源分配請求，確保系統永遠不會進入一個可能導致死結的不安全狀態 (unsafe state)。
   • 基本思想: 系統中的資源分配策略必須保證系統處於安全狀態 (safe state)。一個狀態是安全的，如果系統可以按某種順序為所有進程分配資源，直到所有進程都完成。
   • 常用算法: 銀行家算法 (Banker's Algorithm)。它需要知道每個進程的最大資源需求量。

本題考查**二元搜尋法（Binary Search Algorithm）的運作機制與搜尋步驟追蹤。二元搜尋法的核心思想為「分治法（Divide and Conquer）」，前提為資料必須已處於由小到大排序（Sorted）**的狀態；演算法每次比對中間元素（$mid$），根據與目標值（$target$）的大小關係排除一半無效區間，從而將搜尋的時間複雜度降低至 $O(\log n)$。

---

解題過程與步驟說明

給定數列包含 $12$ 個已排序的元素：
8, 13, 17, 26, 44, 56, 88, 97, 143, 178, 190, 213
目標搜尋值 $target = 190$。

在現代電腦科學與主流程式語言（如 C、C++、Java、Python）中，陣列索引（Index）預設採用 $0$-based 規範（即第一個元素索引為 $0$）。中間索引計算公式採用整數除法（無條件捨去 Floor Division）：
$mid = \lfloor \frac{low + high}{2} \rfloor$

0-based 陣列索引對照表：

• 陣列長度 $n = 12$
• 初始搜尋區間：$low = 0$, $high = 11$

索引 ($index$)	0	1	2	3	4	5	6	7	8	9	10	11
數值 ($value$)	8	13	17	26	44	56	88	97	143	178	190	213

詳細搜尋步驟：

• 第 1 步：

  • 搜尋範圍： $low = 0$, $high = 11$
  • 計算中間索引： $mid = \lfloor \frac{0 + 11}{2} \rfloor = 5$
  • 取得中間值： $array[5] = 56$
  • 判斷與更新： 比較目標值與中間值，$190 > 56$。因為數列已排序，目標值若存在必在右半部，故可完全排除左半部（包含索引 $0 \sim 5$ 的元素）。更新左邊界 $low = mid + 1 = 6$。

• 第 2 步：

  • 搜尋範圍： $low = 6$, $high = 11$
  • 計算中間索引： $mid = \lfloor \frac{6 + 11}{2} \rfloor = 8$
  • 取得中間值： $array[8] = 143$
  • 判斷與更新： 比較目標值與中間值，$190 > 143$。目標值仍大於中間值，說明目標值位於更右側區間，故排除索引 $6 \sim 8$ 的元素。更新左邊界 $low = mid + 1 = 9$。

• 第 3 步：

  • 搜尋範圍： $low = 9$, $high = 11$

核心觀念

本題的核心考點為 C 語言中遞迴（Recursion）的執行流程與階乘（Factorial）數學函式的程式實作。遞迴解題的關鍵在於辨識基本情況（Base Case）與遞迴關係式（Recursive Step），並理解程式在執行時如何利用**呼叫堆疊（Call Stack）**進行遞迴呼叫的「展開（Unrolling）」與結果的「回溯（Unwinding）」。

---

完整解題過程

步驟 1：分析函式結構與數學意涵

觀察題目給予的 C 語言函式 youUnderstand(int target)：

1. 基本情況（Base Case）：
   當 target == 1 時，條件成立，直帶入並回傳 1。這是遞迴停止並開始回溯的終止條件，避免造成無限遞迴（Stack Overflow）。
2. 遞迴關係式（Recursive Step）：
   當 $target > 1$ 時，回傳 youUnderstand(target - 1) * target。這符合階乘的數學定義：
   $n! = n \times (n-1)! \quad \text{其中 } 1! = 1$

由此可知，該函式的作用即為計算正整數 $target$ 的階乘 $target!$。

---

步驟 2：執行流程追蹤（Tracing）

當傳入 $target = 6$ 時，執行過程可分為「遞迴展開」與「結果回溯」兩個階段：

1. 遞迴呼叫展開階段（Push 至 Call Stack）

函式持續呼叫自身，並將尚未完成乘法計算的區域變數與返回位址壓入呼叫堆疊：

• 呼叫 youUnderstand(6)：因 $6 \neq 1$，回傳 youUnderstand(5) * 6
• 呼叫 youUnderstand(5)：因 $5 \neq 1$，回傳 youUnderstand(4) * 5
• 呼叫 youUnderstand(4)：因 $4 \neq 1$，回傳 youUnderstand(3) * 4
• 呼叫 youUnderstand(3)：因 $3 \neq 1$，回傳 youUnderstand(2) * 3

核心觀念

本題考查「算術運算式二元樹」與三種二元樹巡訪順序。

• 前序巡訪：根節點 → 左子樹 → 右子樹，記為

  $\text{VLR}$

• 中序巡訪：左子樹 → 根節點 → 右子樹，記為

  $\text{LVR}$

• 後序巡訪：左子樹 → 右子樹 → 根節點，記為

  $\text{LRV}$

在算術運算式二元樹中：

• 葉節點是運算元，例如 $A、B、C$。
• 內部節點是運算子，例如 $+、-、\times、\div$。
• 根節點代表整個運算式最後執行的運算。

解題方法

設圖一的根節點為運算子 $r$，左子樹為 $L$，右子樹為 $R$。依照三種巡訪規則，可得到：

前序巡訪

前序先處理根節點，再處理左、右子樹：

$$r\;L\;R$$

因此，依序抄寫：

1. 根節點運算子；
2. 左子樹所有節點；
3. 右子樹所有節點。

以前序表示法寫出的運算式屬於前綴表示法，運算子位於運算元之前。

中序巡訪

中序先處理左子樹，再處理根節點，最後處理右子樹：

$$L\;r\;R$$

因此，依序抄寫：

1. 左子樹所有節點；
2. 根節點運算子；
3. 右子樹所有節點。

中序巡訪所得的是一般熟悉的中綴表示法。為維持原二元樹所代表的運算順序，通常需在每個子樹外加括號：

$$(L\;r\;R)$$

後序巡訪

後序先處理左、右子樹，最後處理根節點：

核心觀念

題目考查將 ER 圖轉換為關聯式資料模式。圖中有三個實體：SUPPLIER、PROJECT、PART；它們透過三元關係 SUPPLY 相連。SUPPLY 關係另有屬性 Quantity。

圖中各實體的底線屬性為主鍵：

• SUPPLIER 的主鍵是 SName
• PROJECT 的主鍵是 ProjName
• PART 的主鍵是 PartNo

解題方法

先將每個實體轉成一個資料表，保留其屬性並以原實體主鍵作為資料表主鍵。再將三元關係轉成一個資料表，納入三個參與實體的主鍵作為外鍵，並加入關係本身的屬性 Quantity。

圖中沒有標示關係的基數或其他鍵限制，因此依一般三元關係轉換方式，以三個外鍵的組合作為 SUPPLY 的複合主鍵。

關聯式資料模式

• SUPPLIER(SName)
• PROJECT(ProjName)
• PART(PartNo)