108 關務特考四等 資訊處理 程式語言概要 考古題詳解

核心觀念

1. 費波那契數列（Fibonacci Numbers）的數學定義： $F(0) = 0, \quad F(1) = 1, \quad F(n) = F(n-1) + F(n-2) \quad (n \ge 2)$
2. 遞迴關係式（Recurrence Relation）與時間複雜度分析：

• 遞迴演算法之時間複雜度取決於函數遞迴呼叫的次數與每次呼叫本身的計算量。其結構會展開為「遞迴呼叫樹」（Recursion Tree），利用遞迴關係式與特徵方程式可推導其漸進時間上界。
• 遞迴計算常伴隨「重疊子問題」（Overlapping Subproblems），若未進行記憶化處理，會造成大量重複計算。

3. 迭代（非遞迴）演算法之迴圈計數分析：

• 非遞迴解法採「由底向上」（Bottom-up）的動態規劃思維，透過有限狀態變數（如暫存變數 $a, b$）記錄前兩項狀態，時間複雜度取決於迴圈的執行次數。

4. 系統呼叫堆疊（Call Stack）與空間負擔：

• 遞迴呼叫需要將返回位址、區域變數與參數壓入系統堆疊（Push Stack Frame），深度為 $O(n)$；迭代法僅使用常數個區域變數，空間複雜度為 $O(1)$。

---

解題方法

(一) 計算時間複雜度

1. 遞迴方式（fib_r）的時間複雜度

• 建立遞迴關係式： 設 $T(n)$ 為計算 $F(n)$ 所需的時間步驟。
• 當 $n = 0$ 或 $n = 1$ 時，僅需常數次判斷與回傳，故基本情況為： $T(0) = O(1), \quad T(1) = O(1)$
• 當 $n \ge 2$ 時，程式執行一次條件判斷、一次加法，並分別遞迴呼叫 fib_r(n-1) 與 fib_r(n-2)： $T(n) = T(n-1) + T(n-2) + c \quad (c \text{ 為常數時間 } O(1))$
• 求解漸進複雜度：
• 此關係式之增長階數與費波那契數列本身相同。考慮齊次特徵方程式 $r^2 - r - 1 = 0$，其特徵根為： $r = \frac{1 \pm \sqrt{5}}{2}$
• 取其正根 $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618$（黃金比例），可推得緊等界（Tight Bound）為： $T(n) = \Theta(\phi^n) = \Theta(1.618^n)$
• 若以遞迴樹高度粗估上界，樹的最大深度為 $n$，各層節點數以 $2$ 的冪次增長，其漸進上界通常亦表示為指數階： $T(n) = O(2^n)$
• 結論：遞迴方式的時間複雜度為 $O(2^n)$（或更精確之 $\Theta(1.618^n)$，均屬指數時間複雜度，Exponential Time）。

2. 非遞迴方式（fib_un）的時間複雜度

• 迴圈次數與單次成本：
• 基本情況 $n = 0$ 或 $n = 1$ 直接回傳，耗時 $O(1)$。
• 當 $n \ge 2$ 時，變數初始化 $a = 0, b = 1$ 耗時 $O(1)$。
• 核心為 for i = 2 to n 迴圈，共迭代 $(n - 2 + 1) = n - 1$ 次。
• 迴圈本體內部包含：數值搬移 temp = b、加法運算 b = a + b、數值指派 a = temp，均為常數時間操作 $O(1)$。
• 總執行時間： $T(n) = O(1) + (n - 1) \times O(1) = O(n)$
• 結論：非遞迴方式的時間複雜度為 $O(n)$（線性時間複雜度，Linear Time）。

---

核心觀念

本題測驗電腦組織與結構中的快取記憶體寫入策略（Cache Write Policies）。在 CPU、快取記憶體（Cache）與主記憶體（Main Memory）組成的階層式記憶體架構中，當 CPU 對記憶體位址執行寫入（Write）操作且發生快取命中（Write Hit）時，系統必須決定何時將更新後的資料同步至較慢的主記憶體中。核心策略即為：

1. 直寫法／寫入（Write Through）：快取與主記憶體同步更新。
2. 回寫法／寫回（Write Back）：僅更新快取，直到該區塊被置換（Eviction）時才寫回主記憶體。

---

解題方法

本題為標準的申論名詞解釋與比較題，作答時切入點如下：

1. 定義精準度：明確指出 CPU 發出寫入命令時，資料流向的「時間點」與「目標儲存元件」。
2. 機制完整度：說明關鍵輔助機制（如 Write Through 常搭配的 Write Buffer；Write Back 必備的 Dirty Bit）。
3. 多維度對比：針對第 (三) 小題（15 分），從「執行效能與延遲」、「匯流排頻寬占用」、「硬體複雜度與成本」、「資料一致性與容錯能力」四大維度全面剖析優缺點，避免過於簡略而失分。

---

解題技巧

1. 字義聯想法：

• Through（穿透）：寫入操作「穿透」快取，直接抵達主記憶體。
• Back（延後寫回）：先留在快取，被趕出去（置換）時才「回寫」。

2. 作答關鍵字（閱卷給分點）：

• Write Through 必寫：同步更新（Simultaneous update）、資料一致性（Data Consistency）、匯流排頻寬負擔（Bus Traffic）、寫入緩衝區（Write Buffer）。
• Write Back 必寫：延遲寫回（Deferred write）、髒位元（Dirty bit / Modified bit）、區塊置換（Block Replacement / Eviction）、快取同調性（Cache Coherence）。

3. 配分比重拿捏：第 (一)、(二) 小題各佔 5 分，重在觀念定義與流程；第 (三) 小題佔 15 分，應條列清楚並以對比架構呈現，方能取得滿分。

---

【答案】

(一) 寫入（Write Through，又稱直寫法／透寫法）

定義： 當 CPU 執行寫入動作且快取記憶體命中（Write Hit）時，處理器會同時將新資料寫入快取記憶體與主記憶體中。

運作機制：

1. CPU 修改快取中的資料區塊。
2. 系統立即透過系統匯流排將相同資料同步寫入對應的主記憶體位址。
3. 為避免 CPU 每次寫入都因等待主記憶體而處於停頓（Stall）狀態，現代架構通常會在快取與主記憶體之間配置一個寫入緩衝區（Write Buffer），CPU 將資料寫入 Buffer 後即可繼續執行後續指令，由硬體自動將 Buffer 中的資料排程寫入主記憶體。

---

(二) 寫回（Write Back，又稱回寫法／延遲寫入）

定義： 當 CPU 執行寫入動作且快取記憶體命中（Write Hit）時，處理器僅將新資料寫入快取記憶體中，暫時不同步更新主記憶體；

核心觀念

本題旨在測驗作業系統中 行程管理（Process Management） 與 fork 系統呼叫（System Call） 的運作機制及行程樹（Process Tree）的生成規律。核心觀念包含以下四點：

1. fork 的回傳值特性：

• 在父行程（Parent Process）中，fork 回傳新建立之子行程的 PID（大於 $0$ 的整數）。
• 在子行程（Child Process）中，fork 回傳 $0$。
• 若建立失敗則回傳負值（本題在常態考題假設下，預設系統資源充足，呼叫皆成功）。

2. 記憶體空間與執行進程複製（Address Space Duplication）：

• 子行程會完整複製父行程的資料段、堆疊段、堆積段與程式計數器（Program Counter, PC）。
• 子行程不會從頭執行程式，而是自 fork 呼叫完成後的下一行指令繼續往下執行。

3. 連續 fork 的二元分裂特性：

• 單一行程連續執行 $n$ 次無條件 fork，產生的總行程數（含原本的行程）為 $2^n$ 個。

4. 行程生命週期與迴圈控制：

• 行程在完成程式區塊後，若無呼叫 exit、return 或 break，將循序執行至迴圈末端，並各自執行遞增運算（$i++），全數進入下一次迴圈迭代。

---

解題方法

本題採用​「單次回圈增長模型（狀態轉移推導）」​切入，計算每一輪迴圈結束時行程數量的放大倍率，再以指數遞迴求出總數。

步驟一：分析單一輪迴圈內行程的增長倍率

假設在某次迴圈開始前，系統中共有 $M$ 個行程。針對其中任意「單一行程」分析其執行歷程：

1. 外層 if(fork == 0)：

• 該行程執行 fork，分裂為「原行程（父）」與「新行程（子）」。
• 父行程：收到的回傳值為子行程的 $\text{PID} > 0$，因此 if(fork == 0) 條件為假（False），跳過 if 區塊，直接抵達迴圈本體結尾。此時父行程分支維持 $1$ 個行程。
• 子行程：收到的回傳值為 $0$，if 條件為真（True），進入 if 區塊執行。

2. if 區塊內部的三次連續 fork：

• 進入區塊的子行程連續執行 3 次 fork： $\text{區塊內產生的行程數} = 2^3 = 8\text{ 個}$
• 這 8 個行程完成區塊內指令後，全數離開 if 結構，抵達迴圈本體結尾。

3. 單輪迴圈結算：

• 每 $1$ 個進入迴圈的行程，在該輪迴圈結束時，都會衍生出： $1\text{（未進入 if 的父行程）} + 8\text{（進入 if 的子行程及其衍生行程）} = 9\text{ 個行程}$
• 因此，每經過一輪迴圈，系統內的行程總數變為原來的 $9$ 倍。

步驟二：推導各輪迭代的行程總數

本題迴圈條件為 $i = 0; i < 3; i++（此為公職題目常見之跨語言擬題寫法），總共執行 $i = 0$、$i = 1$、$i = 2$ 共 3 次迭代。

• 初始狀態（迴圈執行前）： 只有原始執行的主行程（Parent Process），設初始行程數 $P_0 = 1$。
• 第 1 次迭代結束（$i = 0$）： $P_1 = P_0 \times 9 = 1 \times 9 = 9\text{ 個行程}$
• 第 2 次迭代結束（$i = 1$）：

核心觀念

本題評量程式語言依照「轉譯與執行機制」（Translation and Execution Model）之分類原理。核心概念包含：

1. 直譯式語言（Interpreted Language）：以「直譯器」（Interpreter）為核心，不產生獨立機器碼目的檔，而是在執行時期（Runtime）逐行讀取、即時解析並直接執行原始程式碼。
2. 編譯式語言（Compiled Language）：以「編譯器」（Compiler）為核心，在執行前將高階原始碼一次性完整轉換為特定硬體架構的「目的碼」（Object Code），再經「連結器」（Linker）產生可獨立執行的原生二進位檔案（Executable Binary）。
3. 混合式語言（Hybrid / Bytecode-based）與標記語言（Markup Language）之界線：釐清現代中介位元組碼（Bytecode）架構（如 Java）與純直譯式語言之區別，並區分「標記語言」（如 HTML）與「程式語言」在運算完備性上的本質差異。

---

解題方法

申論與問答題切入架構應掌握「定義 $\rightarrow$ 運作流程 $\rightarrow$ 優缺點比較」三層結構：

1. 第 (一) 小題：先給出直譯式語言的嚴謹定義，繪製或條列其處理流程（原始碼 $\rightarrow$ 直譯器 $\rightarrow$ 執行輸出），隨後列舉其在可攜性、除錯彈性及執行效能上的特性。
2. 第 (二) 小題：給出編譯式語言的嚴謹定義，條列其階段流程（前處理 $\rightarrow$ 編譯 $\rightarrow$ 組譯 $\rightarrow$ 連結 $\rightarrow$ 執行），並分析其執行效能、系統資源利用及跨平台限制。
3. 第 (三) 小題（選項分析）：針對題目列出的 6 個項目逐一判定其語言類別與執行機制，特別指明「非程式語言」的陷阱項目與「混合型中介語言」的定位，明確歸納出屬於直譯式的項目。

---

各小題詳解

(一) 何謂直譯式程式語言（Interpreted Language）

1. 基本定義： 直譯式程式語言是指在程式執行前不需要預先編譯成機器碼執行檔，而是在程式執行時，仰賴一個專屬的執行環境——「直譯器」（Interpreter），將高階原始程式碼（Source Code）或中介碼「逐行（或逐句）讀取、即時語法分析、即時轉譯並立即交由 CPU 執行」的程式語言。

2. 執行流程： $\text{原始程式碼 (Source Code)} \xrightarrow{\text{執行時期 (Runtime)}} \text{直譯器 (Interpreter)} \xrightarrow{\text{逐行即時解讀}} \text{輸出執行結果}$ 在此模式下，系統不會在磁碟中產生獨立的 .exe 或原生二進位目的檔，每次執行該程式時，皆必須啟動直譯器。

3. 主要優缺點：

• 優點：
• 跨平台可攜性高（High Portability）：只要目標作業系統安裝有對應的直譯器，同一份原始碼不需修改即可直接在不同平台運作。
• 除錯與開發效率佳：修改程式後可立即執行驗證，免去耗時的編譯與連結階段，通常支援互動式命令列環境（REPL）。
• 語意彈性大：普遍具備動態型別（Dynamic Typing）、反射（Reflection）及執行期動態評估（如 eval）等特性。
• 缺點：
• 執行效能較差：執行期同時包含「翻譯」與「執行」的運算開銷（Overhead），執行速度顯著低於編譯式語言。
• 原始碼保護不易：散布軟體時多半必須交付原始程式碼或易被反組譯的中介碼，商業機密性與智財權保護較弱。

---

(二) 何謂編譯式程式語言（Compiled Language）

1. 基本定義： 編譯式程式語言是指高階原始程式碼在真正執行前，必須先透過「編譯器」（Compiler）進行完整的詞法分析、語法分析、語意分析、最佳化，並針對目標硬體架構一次性完整轉譯為機器碼目的檔（Object Code），再經由「連結器」（Linker）將目的檔與相關函式庫（Libraries）結合成可獨立執行的原生二進位檔案（Executable File）。

2. 轉譯與執行流程： $\text{原始程式碼} \xrightarrow{\text{編譯器 (Compiler)}} \text{目的檔 (.obj / .o)} \xrightarrow{\text{連結器 (Linker)}} \text{可執行檔 (.exe)} \xrightarrow{\text{載入記憶體}} \text{CPU 直接執行}$