高考申論題
105年
[資訊處理] 程式語言
第 一 題
📖 題組：
請回答下列問題：（每小題 5 分，共 10 分） (一) 給定一個整數陣列 S[n]，請寫出一個副程式 int SelectionK(int *S, int n)，此函數可以回傳（return）第 K 大的數值。 (二) 給定一個陣列 S[n]，請寫出一個演算法，此演算法可以用平均時間複雜度為 O(n) 的效率，回傳（return）第 K 大的數值。
請回答下列問題：（每小題 5 分，共 10 分） (一) 給定一個整數陣列 S[n]，請寫出一個副程式 int SelectionK(int *S, int n)，此函數可以回傳（return）第 K 大的數值。 (二) 給定一個陣列 S[n]，請寫出一個演算法，此演算法可以用平均時間複雜度為 O(n) 的效率，回傳（return）第 K 大的數值。
📝 此題為申論題，共 2 小題
小題 (一)
給定一個整數陣列 S[n]，請寫出一個副程式 int SelectionK(int *S, int n)，此函數可以回傳（return）第 K 大的數值。
思路引導 VIP
看到此題需先注意函數簽名缺少了參數 K，作答時應合理假設 K 為全域變數或另有定義。因題組第二小題才要求 O(n) 的時間複雜度，本小題最適合使用與函數名稱呼應的「部分選擇排序（Partial Selection Sort）」，執行 K 次尋找最大值的操作即可，時間複雜度為 O(K×n)。
小題 (二)
給定一個陣列 S[n]，請寫出一個演算法，此演算法可以用平均時間複雜度為 O(n) 的效率，回傳（return）第 K 大的數值。
思路引導 VIP
看到「找第 K 大（或小）元素」且要求「平均時間複雜度 O(n)」，必須直覺聯想到「快速選擇（Quickselect）」演算法。該演算法利用 Quick Sort 中的分割（Partition）概念，每次只需遞迴包含目標值的單側區間，無需對完整陣列進行排序，進而將平均複雜度從 O(n log n) 降至 O(n)。