高考申論題
110年
[資訊處理] 資料結構
第 一 題
📖 題組：
四、(一)請使用 C 語言寫一副程式 void FindMeanAverage(int A [], int n, int * mean, int * average)，對一個未排序的（unsorted）且長度為 n 的陣列 A[0:n-1]，尋找陣列中的中位數與平均數，並分別存入 mean 及 average 運算複雜度。（17 分）(二)請舉例說明此副程式最差情況（worst case）所花費的運算複雜度。（8 分）（注意：請加註解說明程式碼作法。）
四、(一)請使用 C 語言寫一副程式 void FindMeanAverage(int A [], int n, int * mean, int * average)，對一個未排序的（unsorted）且長度為 n 的陣列 A[0:n-1]，尋找陣列中的中位數與平均數，並分別存入 mean 及 average 運算複雜度。（17 分）(二)請舉例說明此副程式最差情況（worst case）所花費的運算複雜度。（8 分）（注意：請加註解說明程式碼作法。）
📝 此題為申論題，共 2 小題
小題 (一)
請使用 C 語言寫一副程式 void FindMeanAverage(int A [], int n, int * mean, int * average)，對一個未排序的（unsorted）且長度為 n 的陣列 A[0:n-1]，尋找陣列中的中位數與平均數，並分別存入 mean 及 average 運算複雜度。（17 分）（注意：請加註解說明程式碼作法。）
思路引導 VIP
- 題目術語澄清：通常
mean指平均數，但題目變數名稱mean與average並列，且內文提到「中位數與平均數」。從變數名判斷，mean可能指中位數（Median），average指算術平均。2. 平均數實作：累加陣列所有元素後除以 $n$，時間 $O(n)$。3. 中位數實作：未排序陣列求中位數，最直覺做法是「排序」後取中間值（時間 $O(n \log n)$），或使用「Quick Select」演算法（平均 $O(n)$）。考慮到 C 語言實作簡便與穩定性，先排序（如使用qsort）是標準考場做法。
小題 (二)
請舉例說明此副程式最差情況（worst case）所花費的運算複雜度。（8 分）（注意：請加註解說明程式碼作法。）
思路引導 VIP
- 分析組成：總複雜度 = 計算平均的時間 + 求中位數的時間。2. 計算平均：$O(n)$，無最差情況差異。3. 求中位數（排序）：如果使用
qsort(通常是快速排序 QuickSort)，其最差情況發生在基準值（Pivot）選取極端時（如陣列已排序但選第一個元素為 Pivot），複雜度會退化到 $O(n^2)$。4. 如果是 Quick Select：最差也是 $O(n^2)$。