地特三等申論題
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
看到函數名稱為「SelectionK」且未限制時間複雜度，應直覺想到使用「選擇排序法（Selection Sort）」的概念。只要做 K 次選擇找出前 K 大的值即可，同時需注意原題目函數簽章漏了參數 K，答題時必須明確指出並給出合理假設或修正。
小題 (二)
給定一個陣列 S[n]，請寫出一個演算法，此演算法可以用平均時間複雜度為 O(n) 的效率，回傳（return）第 K 大的數值。
思路引導 VIP
看到「尋找第 K 大元素」且「平均時間複雜度為 O(n)」的限制條件，應立刻聯想到「快速選擇演算法（Quickselect）」。此演算法利用快速排序（Quicksort）中的 Partition 概念，每次挑選基準值（Pivot）將陣列分區，只需針對包含目標元素的那半邊繼續遞迴尋找，從而省去對無關區間的排序時間。