114 公務人員升官等薦任 資訊處理 程式語言 考古題詳解
第 一 題25 分
請詳述下列四種排序（sort）演算法的運作原理及其時間複雜度。
（一）泡沫排序（bubble sort）
（二）插入排序（insertion sort）
（三）合併排序（merge sort）
（四）快速排序（quick sort）
登入後即可作答並保存紀錄。
核心觀念
本題考查四種基本排序演算法的運作方式，以及輸入資料已排序、逆序或一般情況下，演算法所需的時間。分析時間複雜度時，以元素數量 為規模，並區分：
- 最佳情況：對演算法最有利的輸入。
- 平均情況：對一般輸入的期望時間。
- 最差情況：對演算法最不利的輸入。
下文以由小到大排序為例。時間複雜度通常採用漸近表示法；例如 表示執行時間與 同階。
解題方法
回答每種排序時，先說明它如何逐步改變資料，再分析比較與搬移元素的次數。泡沫排序與插入排序會反覆處理相鄰元素或已排序區段；合併排序將問題分割後合併；快速排序則依樞紐值分割資料，再遞迴排序子區段。
（一）泡沫排序（Bubble Sort）
運作原理： 由左至右比較相鄰的兩個元素。若左邊元素大於右邊元素，就交換兩者。每完成一趟，尚未定位的最大元素會「浮」到未排序區段的最右端；後續各趟因此不必再檢查已定位的尾端元素。
以 為例，第一趟比較並交換後，最大值 會移至最右端；之後只需排序前面的未定位元素，逐步完成排序。
時間複雜度：
- 最佳情況：。 若資料已排序，且實作中設有「本趟是否發生交換」的旗標，第一趟沒有交換即可結束。
- 平均情況：。
- 最差情況：。 例如資料為逆序時，需要多趟比較與交換。
未最佳化的標準版本，即使輸入已排序，仍會執行完整的多趟比較，因此最佳情況也是 。寫答案時應交代採用的實作版本。
（二）插入排序（Insertion Sort）
運作原理： 將資料分為「已排序區段」與「未處理元素」。每次取出未處理區段最左側的元素，向左與已排序區段比較，將比它大的元素逐一右移，再把該元素插入適當位置。每完成一次插入，已排序區段便增加一個元素。
以 為例，先將 視為已排序；插入 後成為 ，再將 插入成為 ，最後插入 完成排序。
時間複雜度：
- 最佳情況：。 資料已排序時，每個新元素只需與已排序區段末端比較一次。
- 平均情況：。 插入元素時，平均須向左移動已排序區段中的一部分元素。
- 最差情況：。 逆序資料中，第 個元素最多須與前面 個元素比較並移動，總工作量為
（三）合併排序（Merge Sort）
運作原理： 採用「分治法」：
- 將資料分成大小盡量相等的兩半。
- 遞迴地排序左右兩半。
- 將兩個已排序區段合併成一個已排序區段。
第 二 題25 分
二元樹（binary tree）是一種常見的資料結構。對二元樹的任何一節點（node）而言，其可能包含的子節點（children）數量為 、 或 。舉例來說，對於一個具有 個節點的二元樹，其可能的結構如下圖所示：
🖼️【此處有附圖，請對照原卷】
（一）請使用遞迴（recursion）的方式撰寫一個 C 語言函數 int nTrees(int n)，來計算具有 個節點的二元樹，共有多少種不同的二元樹結構。（20 分）
（二）在許多情況下，使用遞迴的方式所撰寫的程式不是最有效率的方法。請問可以使用何種程式撰寫的方法來提高（一）的程式的執行效率？（5 分）
登入後即可作答並保存紀錄。
核心觀念
本題考二元樹的遞迴計數。每棵非空二元樹都有一個根節點；若左子樹有 個節點，右子樹就有 個節點。左、右子樹的結構可分別選擇，因此兩邊的組合數相乘，再對所有可能的 加總。
依題目圖示，左子節點與右子節點的位置有別；只有一個子節點時，放在左邊或右邊會算作不同結構。
解題方法
令 表示具有 個節點的二元樹結構數。空樹有一種，因此 ；非空樹的根節點占用一個節點，左子樹節點數可由 到 ，故：
依此可得 、、，與題目所列的 3 節點二元樹數量相符。
第 三 題25 分
若我們使用 C 程式語言，定義了如下的結構（struct）：
typedef struct { char frst_name[20]; char last_name[20]; int score; char grade; } student_t;
並宣告兩個變數為此結構：
student_t stu1, stu2;
請分別判斷下列 個敘述是否有可能為有效（valid）的敘述或是一定為無效（invalid）的敘述，並詳述其理由。（25 分）
-
student_t A_list[30]; -
printf("%s", stu2); -
printf("%d %c", stu2.score, stu2.grade); -
stu1 = stu2; -
if (stu1.grade == stu2.grade) printf("Same Grade"); -
if (stu1 == stu2) printf("Same Structure"); -
stu1.last_name = "Donald"; -
student_func(&stu1);
登入後即可作答並保存紀錄。
核心觀念
本題考查 C 語言中結構（struct）的宣告、成員存取、指定與比較，以及陣列和字串的型別規則。判斷敘述是否有效，須檢查運算子兩側的型別是否相容，以及該運算子能否用在結構或陣列上。
解題方法
逐項確認三件事：
- 敘述是否符合 C 的語法。
- 運算子是否支援該型別。
- 是否缺少必要的宣告或格式指定符。
題目沒有提供 student_func 的函式宣告，因此第 8 項須依合理假設判斷：假設函式已宣告且參數型別為 student_t *。
選項分析
1. student_t A_list[30];——有效
宣告一個含有 30 個 student_t 元素的陣列。結構型別可作為陣列元素型別，語法有效。
2. printf("%s", stu2);——無效
%s 要求對應引數是指向字元字串的指標，通常為 char * 或 const char *。stu2 的型別是 student_t 結構，與 %s 不相容；printf 不會自動把結構轉成字串。
若要輸出姓名，須傳入字元陣列成員，例如 printf("%s", stu2.frst_name);。
3. printf("%d %c", stu2.score, stu2.grade);——有效
stu2.score 是 int，對應 %d；stu2.grade 是 char，在變動參數函式呼叫時會提升為 int，而 %c 會將其作為字元輸出。格式指定符與引數型別相符。
4. stu1 = stu2;——有效
C 語言允許將同一結構型別的物件直接指定給另一個物件。此處兩者皆為 student_t，會逐成員複製結構內容，包括陣列成員的內容。
第 四 題15 分
請問下列 C 語言程式執行後的輸出為何？（15 分）
#include <stdio.h>
int main(void) { int x = 0;
do {
switch (x) {
case 0:
printf("%d\n", x);
case 1:
x++;
break;
case 2:
printf("3\n");
case 3:
printf("%d\n", x * 3);
case 4:
x += 3;
break;
default:
x = x * 2;
printf("%d\n", x / 3);
}
} while (x < 10);
return (0);
}
登入後即可作答並保存紀錄。
核心觀念
本題考查 do...while 迴圈與 switch 敘述的執行流程，重點有二：
do...while會先執行迴圈本體，再判斷條件，所以本體至少執行一次。switch從符合的case標籤開始往下執行；若沒有遇到break，就會繼續執行後續的case區段，這稱為「貫穿」（fall-through）。
解題方法
逐次記錄每輪進入 switch 時的 x 值，並依程式實際執行順序追蹤輸出與變數變化。每輪執行到 break 後離開 switch，再檢查 while (x < 10) 是否成立。
| 輪次 | 進入 switch 時的 x | 執行流程與輸出 | 離開 switch 後的 x | 迴圈條件 |
|---|---|---|---|---|
| 1 | 0 | case 0 印出 0；沒有 break，貫穿至 case 1，令 x++，再由 break 離開 | 1 | ，繼續 |
第 五 題10 分
請描述何謂白箱測試（white-box testing）和黑箱測試（black-box testing）。
登入後即可作答並保存紀錄。
核心觀念
本題考查軟體測試依據與檢查方式的差異。白箱測試與黑箱測試都用來發現程式錯誤，主要區別在於測試者是否利用程式內部的程式碼、邏輯與結構來設計測試。
| 比較項目 | 白箱測試（white-box testing） | 黑箱測試（black-box testing） |
|---|---|---|
| 測試依據 | 程式內部結構、控制流程與資料處理邏輯 | 需求規格、輸入與預期輸出 |
| 是否須了解程式內部 | 須檢視或掌握程式碼與結構 | 不以了解程式碼為前提 |
| 主要檢查重點 | 程式路徑、判斷條件、敘述與迴圈是否適當執行 | 功能是否符合需求，輸入與輸出是否正確 |
| 常見技術 | 敘述覆蓋、分支覆蓋、條件覆蓋、路徑覆蓋 | 等價分割、邊界值分析、決策表、狀態轉移測試 |
「白箱」著重檢查程式內部如何運作；「黑箱」著重檢查程式對外呈現的功能結果。
解題方法
本題為名詞解釋題，作答時先說明兩種測試的判斷基準，再各自補充測試目的與例子，最後對照兩者差異。