高考申論題
115年
[電信工程] 計算機概論
第 一 題
📖 題組：
二、(一)請問下列的 C 語言函式 xxxSort()是在執行那種排序演算法？請說明理由。（10 分） void xxxSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } (二)費氏數列的定義為： F(0)=0, F(1)=1 F(n)=F(n-1)+F(n-2), n≥2 假設我們要寫一個程序來算出 F(n)，可以用遞迴（recursive）方式，也可用迭代（iterative）方式來寫程式。請問這兩種方式的優缺點為何？（10 分）
二、(一)請問下列的 C 語言函式 xxxSort()是在執行那種排序演算法？請說明理由。（10 分） void xxxSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } (二)費氏數列的定義為： F(0)=0, F(1)=1 F(n)=F(n-1)+F(n-2), n≥2 假設我們要寫一個程序來算出 F(n)，可以用遞迴（recursive）方式，也可用迭代（iterative）方式來寫程式。請問這兩種方式的優缺點為何？（10 分）
📝 此題為申論題，共 2 小題
小題 (一)
請問下列的 C 語言函式 xxxSort()是在執行那種排序演算法？請說明理由。（10 分）
void xxxSort(int arr[], int n)
{
int i, j, key;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void xxxSort(int arr[], int n)
{
int i, j, key;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
思路引導 VIP
本題考查經典排序演算法的程式碼辨識。仔細分析程式碼：
- 外層迴圈
for (i = 1; i < n; i++)將陣列切分為「已排序」與「未排序」兩部分，每次挑選未排序的第一個元素arr[i]存入key。
小題 (二)
費氏數列的定義為：
F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2), n≥2
假設我們要寫一個程序來算出 F(n)，可以用遞迴（recursive）方式，也可用迭代（iterative）方式來寫程式。請問這兩種方式的優缺點為何？（10 分）
F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2), n≥2
假設我們要寫一個程序來算出 F(n)，可以用遞迴（recursive）方式，也可用迭代（iterative）方式來寫程式。請問這兩種方式的優缺點為何？（10 分）
思路引導 VIP
本題是計算機概論中「演算法策略比較」的必考經典題。比較對象是遞迴（Recursive）與迭代（Iterative）計算費氏數列。考生的思考架構應包括：
- 遞迴（Recursive）計算 F(n) 的優缺點：直覺、與定義契合，但有嚴重的重複計算問題（重疊子問題 Overlapping Subproblems），導致時間複雜度呈指數級 $O(2^n)$，且會有呼叫棧（Call Stack）過深的風險（Stack Overflow）。