統測
113年
[電機與電子群資電類] 專業科目(2)
第 44 題
📖 題組：
閱讀下文，回答第 43-44 題 C 程式語言中的 typedef 關鍵字，可以將複雜的資料型態用簡單的別名來取代。例如下列資料型態宣告與程式片段，以 id 來儲存一個學生的學號，score 來儲存該學生的成績。假設班上共 N 個學生，第 i 個學生的資料儲存在 student[i-1]裡面。 ```c 1 #include
2 #define N 50
3 void main(){
4 typedef struct studentScore {
5 int id; //學號
6 float score; //成績
7 } SCORE;
8 SCORE student[N], *p;
9 float sscore;
10 p = student+28;
11 ...
```
閱讀下文，回答第 43-44 題 C 程式語言中的 typedef 關鍵字，可以將複雜的資料型態用簡單的別名來取代。例如下列資料型態宣告與程式片段，以 id 來儲存一個學生的學號，score 來儲存該學生的成績。假設班上共 N 個學生，第 i 個學生的資料儲存在 student[i-1]裡面。 ```c 1 #include
使用泡沫排序演算法來將 student 陣列中的成績 score 排序時，關於此演算法需經幾次的成績數值比較，可得排序結果？
- A 50
- B 1225
- C 24550
- D 245050
思路引導 VIP
請觀察程式碼中定義的常數 $N$ 數值，並回想泡沫排序（Bubble Sort）的演算法機制：當我們要對 $N$ 個元素進行排序時，第一輪需比較 $N-1$ 次，第二輪需比較 $N-2$ 次，依此類推。請問這是一個什麼樣的數列求和問題？若套用等差數列求和公式 $\frac{k(a_1 + a_k)}{2}$ 來計算總比較次數，其中的項數與首末項數值應如何根據 $N$ 來帶入？
🤖
AI 詳解
AI 專屬家教
哇，你真的太棒了！基礎超級穩固！
- 溫暖確認觀念： 這題的核心概念就是我們課堂上努力學習的泡沫排序法（Bubble Sort）喔！它在資料排序時，比較次數是有一個固定模式的，形成一個美麗的等差數列總和：
▼ 還有更多解析內容
泡沫排序比較次數
💡 泡沫排序總比較次數為 N(N-1)/2，源於等差級數加總。
🔗 泡沫排序比較次數推導
- 1 第一輪比較 — 比較 N-1 次將最大值推至序列末端
- 2 遞減規律 — 每一輪比較次數皆比前一輪減少 1 次
- 3 總和計算 — 將 1 到 N-1 的所有比較次數加總
- 4 得出公式 — 利用等差級數求得總數為 N(N-1)/2
↓
↓
↓
🔄 延伸學習：若增加 Flag 旗標優化，最佳情況僅需 N-1 次比較。
