民國115年 高考三級 電力工程 計算機概論
第2題
請問下列的C 語言函式xxxSort()是在執行那種排序演算法？請說明 理由。（10 分） void xxxSort(int arr[], int n) { i…
題目
請問下列的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 分）
參考解答（AI 生成，非官方）
- 一、這是插入排序（Insertion Sort）。外層 i 從 1 到 n-1，將 arr[i] 存為 key；內層 j 由 i-1 往前，將大於 key 的元素右移，最後把 key 放入 arr[j+1]，使前 i+1 個元素保持排序。
- 二、理由是其迴圈不變式為「arr[0..i-1] 已排序」，每回合把未排序區的第一個元素插入已排序區的正確位置，作法如同整理撲克牌。最壞與平均時間 O(n^2)、最佳 O(n)、額外空間 O(1)，且為穩定排序；適合小資料或近乎排序，資料量大時搬移成本高。
- 三、遞迴版費氏數列直接依 F(n)=F(n-1)+F(n-2) 計算，終止條件為 F(0)=0、F(1)=1。優點是程式簡潔、與數學定義一致、容易驗證；缺點是未記憶化時會重複計算相同子問題，時間複雜度達 O(2^n)，且遞迴深度 O(n)，n 大時可能堆疊溢位。
- 四、迭代版以 a=0、b=1，迴圈執行 n 次更新 a、b，時間 O(n)、空間 O(1)，沒有函式呼叫與堆疊負擔，可穩定計算較大的 n；缺點是程式較不直觀，需正確處理 n=0、n=1 的邊界，數值過大時仍有整數溢位問題。若採備忘錄或動態規劃，遞迴可降為 O(n)。
- 五、取捨上，教學或驗證定義可用遞迴；實務重視效率與大 n 時宜用迭代，或使用遞迴加記憶化。若 n 超過資料型別範圍，還需改用大數運算，不能只依賴固定位元整數。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。