1.从尚未排序的N名学生的考试分数中挑出排名第K的分数，平均时间复杂度最优可以达到多少?（ )
A、O(NlogN)
B、O(NK)
C、O(N)
D、O(N^2)
答: 在尚未排序的N名学生的考试分数中挑出排名第K的分数，平均时间复杂度最优的算法是使用快速选择（Quickselect）算法，其平均时间复杂度为O(n)，最坏时间复杂度为O(n^2)。
快速选择算法的步骤如下：
- 选择一个枢轴元素，将整个序列分成3部分：小于枢轴元素的、等于枢轴元素的、大于枢轴元素的。
- 判断K落在哪一部分：如果K落在小于枢轴元素的部分，继续在该部分中递归地进行选择；如果K落在大于枢轴元素的部分，继续在该部分中递归地进行选择；如果K落在等于枢轴元素的部分，则返回该元素即可。
- 重复上述步骤，直到选出第K个元素。
在快速选择算法中，为了避免最坏情况的发生，需要采取一些优化措施，比如每次选择枢轴元素时随机选择，或者采用三数中值分割法等。
因此，快速选择算法是一种时间复杂度比较优秀的算法，可以在较短的时间内找出第K个分数