●如果只想得到一个关键字序列中第k个最小元素之前的排序序列,最好采用 (53) 排序方法。如果有这样

Question

●如果只想得到一个关键字序列中第k个最小元素之前的排序序列，最好采用 (53) 排序方法。如果有这样的一个序列(57，40，38，11，13，34，48，75，25，6，19，9，7)，得到第4个最小元素之前的部分序列(6，7，9，11)，使用所选择的算法实现时，要执行 (54) 次比较。

(53) A．堆排序

B．快速

C．归算

D．基数排序

(54) A．13

B．34

C．269

D．以上都不对

Answer 1

正确答案：A,B
【解析】采用堆排序最合适。依题意可知，只需取得第k个最小元素之前的排序序列，堆排序的时间复杂度为O（n+k×log₂n)，若k≤n／log₂n，则时间复杂度为O(n)。对于序列：(57，40，38，11，13,34 48，75，25，6，19，9，7)，得到第4个最小元素之前的部分序列(6，7，9，11)，使用所选择的算法实现时，其执行比较次数如下：
建堆     20次比较   得到6
调整     5次比较    得到7
调整     4次比较    得到9
调整     5次比较    得到11
总的比较次数为34次。