107 地方特考四等 資訊處理 程式設計概要 考古題詳解

核心觀念 本題測驗 for 迴圈的執行順序 與 迴圈變數在迴圈體內被修改時的追蹤能力。 for (初始式; 條件式; 遞增式) { 迴圈主體 } 的標準執行順序為：

1. 執行「初始式」（僅在進入迴圈時執行一次）。
2. 檢查「條件式」：若為真（True）則執行迴圈主體；若為偽（False）則跳出迴圈。
3. 執行「迴圈主體」。
4. 執行「遞增式」，接著回到步驟 2 重新判斷條件。

---

解題方法 變數 $i$ 不僅在迴圈主體中執行 i = i + 2;，每次迭代結束時還會執行迴圈頭部的 i++（即 $i = i + 1$）。因此，每次完整迴圈迭代實際上使 $i$ 增加 3。

詳細追蹤過程如下表：

迭代次數	進入時 $i$ 值	條件檢查 ($i \le 10$)	執行主體 ($i = i + 2$)	執行遞增式 ($i\text{++}$)	結束時 $i$ 值
第 1 次	0	$0 \le 10$（成立）	$i = 0 + 2 = 2$	$i = 2 + 1 = 3$	3
第 2 次	3	$3 \le 10$（成立）	$i = 3 + 2 = 5$	$i = 5 + 1 = 6$	6
第 3 次	6	$6 \le 10$（成立）	$i = 6 + 2 = 8$	$i = 8 + 1 = 9$	9
第 4 次	9	$9 \le 10$（成立）	$i = 9 + 2 = 11$	$i = 11 + 1 = 12$	12
終止檢查	12	$12 \le 10$（不成立）	跳出迴圈	—	12

跳出迴圈後，執行 printf("%d\n", i);，印出此時的 $i$ 值。

---

解題技巧

• 常見陷阱：考生常忽略迴圈頭部的 i++，誤以為每次迴圈 $i$ 只加 2；或誤以為印出的值是符合迴圈條件的最大值 11。
• 速算訣竅：每次迭代 $i$ 淨增加 $2 + 1 = 3$。數值變化為 $0 \to 3 \to 6 \to 9$（此時 $9 \le 10$ 仍成立，進入主體變 11，再由 i++ 變 12），當 $i = 12$ 時不滿足 $i \le 10$，迴圈終止並印出 12。

---

【答案】 執行結果為輸出：

12

---

（二）遞迴函式追蹤

核心觀念 本題測驗 遞迴函式（Recursive Function）呼叫機制、整數除法（/） 與 取餘數運算（%）。

• x % 10：取得整數 $x$ 的個位數字。
• x / 10：去掉整數 $x$ 的個位數字（在 C 語言中，整數相除會無條件捨去小數點）。
• 遞迴終止條件（Base Case）：當 $x \le 0$ 時回傳 0。
• 該函式的數學意義為：計算並回傳整數 $x$ 各個位數的總和（Digit Sum）。

---

解題方法 呼叫 $fun(123456)$，遞迴展開展開步驟如下：

$fun(123456) = (123456 \pmod{10}) + fun(123456 / 10) = 6 + fun(12345)$ $fun(12345) = 5 + fun(1234)$ $fun(1234) = 4 + fun(123)$ $fun(123) = 3 + fun(12)$ $fun(12) = 2 + fun(1)$ $fun(1) = 1 + fun(0)$

當 $x = 0$ 時，不滿足條件 $x > 0$，觸發終止條件回傳 0： $fun(0) = 0$

將回傳值由底層向上逐層代回（Backtracking）： $fun(1) = 1 + 0 = 1$ $fun(12) = 2 + 1 = 3$ $fun(123) = 3 + 3 = 6$ $fun(1234) = 4 + 6 = 10$ $fun(1235) = 5 + 10 = 15$ $fun(123456) = 6 + 15 = 21$

---

解題技巧

• 判斷出 x % 10 為「取末位」、x / 10 為「消去末位」後，即可快速將問題簡化為求 $123456$ 的各數字和： $1 + 2 + 3 + 4 + 5 + 6 = 21$

---

【答案】 執行結果為：

21

---

（三）4 位元組整數之最大與最小範圍

核心觀念 本題測驗 資料型別的位元長度（Bit Width） 與 電腦整數數值表示法（二補數 Two's Complement）。

• 1 位元組（Byte）$= 8$ 位元（Bits），因此 4 位元組 $= 4 \times 8 = 32$ 位元。

核心觀念

本題為經典的費氏數列（Fibonacci Sequence）推廣型——三階費氏數列（Tribonacci Numbers），主要評量公職資訊處理類科考生對以下四大核心概念的掌握：

1. 差分遞迴關係式（Recurrence Relation）的轉化： 題目給定之數學定義為： $X(0)=1,\quad X(1)=1,\quad X(2)=1,\quad X(k+1)=X(k-2)+X(k-1)+X(k)$ 將自變數平移（令 $n = k+1$，即 $k = n-1$），可改寫為標準的向後參照形式： $X(n) = X(n-3) + X(n-2) + X(n-1)\quad (n \ge 3)$ 亦即：從第 4 項（索引 3）開始，每一項皆為其「前三項之和」。
2. 遞迴函式（Recursive Function）： 掌握終止條件（Base Case）與遞迴呼叫（Recursive Step）的配對。若終止條件設定不當，將導致無窮遞迴與堆疊溢位（Stack Overflow）。
3. 迭代法與動態規劃空間壓縮（Rolling Variables / Space Optimization）： 利用有限的輔助變數滾動記錄前三項數值，將空間複雜度自 $O(n)$ 降至 $O(1)$。
4. 演算法複雜度分析（Algorithm Complexity Analysis）： 精確評估樹狀重複遞迴（指數時間複雜度）與循序迴圈迭代（線性時間複雜度）在時間與空間資源耗用上的差異。

---

解題方法

（一）遞迴函式 X1 的推導

• 基底條件（Base Case）： 依數學定義，數列前三項為 $X(0)=1$、$X(1)=1$、$X(2)=1$。 因此當輸入引數 $k \le 2$ 時，直接回傳常數 1。
• 遞迴步驟（Recursive Step）： 當 $k \ge 3$ 時，數值為前三項之總和，即 $X(k) = X(k-1) + X(k-2) + X(k-3)$。 程式碼中直接呼叫三次函式本身並相加：X1(k-1) + X1(k-2) + X1(k-3)。

（二）for-迴圈函式 X2 的推導（六行以內）

• 變數定義與初值： 題幹給定 int S1=1, S2=1, S3=1, sum=0;，這三個變數分別代表相鄰的前三項： 初始時對應 $S_1 = X(0) = 1$、$S_2 = X(1) = 1$、$S_3 = X(2) = 1$。
• 滾動更新邏輯（Rolling Update）： 進入迴圈後，每一次迭代代表計算新的一項：

1. 將前三項累加至總和：sum = S1 + S2 + S3;
2. 視窗右移一個位置（捨棄最舊項，引進最新項）：

• S1 = S2;（原第二項變為第一項）
• S2 = S3;（原第三項變為第二項）
• S3 = sum;（原計算出之總和變為第三項）
• 迴圈範圍設計： 第 1 次迭代計算 $X(3) = 1+1+1 = 3$； 第 2 次迭代計算 $X(4) = 1+1+3 = 5$； 依此類推，計算至目標項 $X(k)$ 需迭代至計數器等於 $k$。 因此迴圈控制行設計為 for (int i = 3; i <= k; i++)。包含迴圈本體剛好為 6 行程式碼。

（三）執行效率比較與理論證明

函式 X2（迴圈函式）之執行效率遠高於 X1（遞迴函式），其具體理論依據如下：

1. 時間複雜度（Time Complexity）：

• X1（遞迴解法）： 其執行時間遞迴式為 $T(k) = T(k-1) + T(k-2) + T(k-3) + O(1)$。 其特徵方程式為 $r^3 - r^2 - r - 1 = 0$，最大實數根約為 $r \approx 1.839$。 因此 X1 的時間複雜度為指數階： $O(1.839^k)$ 這是因為單純的樹狀遞迴存在大量的重疊子問題（Overlapping Subproblems），同一子項（例如 $X(2)$）會被重複呼叫計算數億次，造成運算效能急遽低落。

核心觀念

本題的核心考點為資料結構中的最大堆積（Max-Heap）​及其向上調整（Reheap Up / Percolate Up / Swim）演算法。

1. 二元樹的陣列表示法（Array Representation of Binary Tree）：

• 樹根（Root）存放於索引 $0$。
• 對於任意節點索引 $k$（$k > 0$），其父節點（Parent）索引為 $\lfloor k/2 \rfloor$。
• 當子節點的鍵值大於父節點時，違反最大堆積性質，必須進行交換（Swap）。

2. 最大堆積性質（Max-Heap Property）：

• 樹中任一節點的值，均小於或等於其父節點的值。
• 因此，樹根節點（即陣列第 0 個元素）恆為整個堆積中的最大值（Maximum）。

3. 試題瑕疵與筆誤分析（國考評分重點）：

• 瑕疵一（未宣告之變數）：函式 reorder 內部使用的陣列名稱 books 未定義，顯係全域陣列 num 之筆誤。
• 瑕疵二（迴圈終止條件）：main 函式中 int i = 0; while (i != 0)，初始條件 $i = 0$ 使得迴圈條件一開始即為假（false），迴圈體完全不執行。依題意「輸入 99 個正整數後再輸入 0 作為結束」，此處顯係 while (num[i] != 0) 之筆誤。
• 作答原則：評分標準通常以「命題委員原意（Max-Heap）」為核心給分標準，但亦有閱卷委員重視「程式碼字面語意（Literal Tracing）」。為求萬無一失，本解題採命題原意（修正筆誤後）​與字面嚴格執行雙軌並陳。

---

解題方法

一、命題原意之演算法推導（修正 books $\to$ num、while (i != 0) $\to$ while (num[i] != 0)）

1. reorder(k) 向上調整流程：

• 傳入目前新插入節點的索引 $k$。
• 終止條件：若已至根節點（$k = 0$），或父節點的值大於等於目前節點（$num[k] \le num[\lfloor k/2 \rfloor]$），則結束調整。
• 交換與遞迴：若 $k \ne 0$ 且 $num[k] > num[\lfloor k/2 \rfloor]$，將兩者數值交換，並對父節點繼續呼叫 reorder(k/2)，持續向上比對至樹根。

2. 主程式構建堆積流程：

• 依序將讀入的數值存入陣列尾端（索引 $i$），並呼叫 reorder(i) 向上調整。
• 透過數學歸納法，每次插入新節點並調整後，陣列均能維持最大堆積結構，故根節點 $num[0]$ 永遠保持為「目前所有已輸入數值中的最大值」。

二、題面程式碼之字面嚴格執行推導

1. 全域變數初始化：$num[0 \ldots 99] = 0$。
2. 進入 main：

• 執行 int i = 0;。
• 執行 scanf("%d", &num[0]);，讀入第一個整數存入 $num[0]$。
• 執行 while (i != 0)：此時 $i = 0$，條件式 $0 \ne 0$ 為 false，迴圈完全不執行。
• 程式直接結束。

3. 結論：除了第一個輸入值成功寫入 $num[0]$ 外，後續所有輸入均未被讀入處理。

---

各小題詳細分析

（一）$num[]$ 一維陣列最多可儲存幾個正整數？

• 陣列實體容量角度：陣列宣告為 int num[100]，索引範圍為 $0 \sim 99$，在不考慮結束標記下，記憶體空間最多可儲存 100 個正整數。
• 程式執行邏輯角度：依題目輸入格式，輸入資料以數值 0 作為結束標記（Sentinel）。若以 0 占用陣列最後一個位置（$num[99] = 0$），則前面最多可儲存 99 個正整數。

核心觀念

本題評量物件導向程式設計（Object-Oriented Programming, OOP）​的兩大核心基石：

1. 封裝（Encapsulation）與存取控制（Access Control）：利用存取修飾子（Access Modifiers）劃定資料邊界，實踐資訊隱藏（Information Hiding），降低模組間的耦合度。
2. 類別（Class）與物件（Object）之本質與關聯：理解自訂資料型態的抽象定義（藍圖）與執行時期具體實體（實例，Instance）的映射機制與記憶體生命週期。

---

解題方法

本題為標準的觀念申論題，配分各佔 10 分。作答時切忌僅以口語化一句話帶過，應採用​「精準學理定義 $\rightarrow$ 關鍵維度對比（列點/表格） $\rightarrow$ 程式實務效益」​的三段式架構：

1. 第（一）子題（public vs. private 變數）：

• 從「存取權限範圍（Scope / Accessibility）」與「封裝與資訊隱藏效益」兩大維度切入。
• 說明 private 如何保護內部狀態並搭配存取子（Getter / Setter），以及 public 變數在維護與除錯上的風險。

2. 第（二）子題（物件與類別的關係）：

• 從「抽象藍圖與具體實例」、「實例化過程（Instantiation）與記憶體配置」、「一對多的衍生關係」切入。
• 輔以經典的比喻（如：建築藍圖 vs. 實體建築）與記憶體配置機制（方法區/靜態區 vs. 堆積區 Heap），展現資訊專業深度。

---

解題技巧

1. 閱卷給分關鍵字（Keywords）導向：

• 評分委員審閱卷宗時，會快速搜尋專有名詞：封裝（Encapsulation）、資訊隱藏（Information Hiding）、存取修飾子（Access Modifier）、實例化（Instantiation）、建構子（Constructor）、藍圖（Blueprint）與實體（Instance）、Heap 記憶體。務必將這些關鍵字以中英文並列呈現。

2. 避免純口語化比喻：

• 可以使用「印模與餅乾」或「建築藍圖與房屋」當作引子，但後續必須緊扣資料型態（Data Type）、變數狀態（State）、行為（Behavior）與記憶體實體化過程，方能拿滿 10 分。

3. 表格化對比拉開得分差距：

• 在論述後附上摘要比較表，能讓版面清晰俐落，利於閱卷老師快速核對給分點。

---

【答案】

（一）public 變數與 private 變數的差別

在物件導向程式語言（如 Java、C++、C#）中，public 與 private 為存取修飾子（Access Modifiers），兩者主要差異如下：

1. 存取權限範圍（Accessibility / Scope）：

• public（公有變數）： 具備完全開放的存取權限。任何外部類別、子類別或套件（Package）中的程式碼，皆可直接讀取與修改該變數。
• private（私有變數）： 存取權限受到最嚴格的限制。僅有「定義該變數的類別內部方法」可以直接存取；所有外部類別、外部物件，甚至其繼承的子類別（Subclass），皆無法直接存取。

2. 封裝與資訊隱藏（Encapsulation & Information Hiding）：

• private 實踐資訊隱藏： 物件導向的核心設計準則要求將資料成員（屬性）設為 private，內部狀態不直接對外曝露，僅透過公有的方法（如 getter 與 setter）提供受控存取。此舉可加入資料驗證機制（如數值範圍檢查），防止物件狀態被外部任意篡改而導致不一致。
• public 破壞封裝性： 若變數宣告為 public，外部程式可繞過驗證直接修改數值，易破壞物件內部的資料完整性（Data Integrity）。