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

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

admin2009-02-15  44
问题 如果只想得到一个关键字序列中第k个最小元素之前的排序序列，最好采用(53)排序方法。如果有这样的一个序列(57，40，38，11，13，34，48，75，25，6，19，9，7)，得到第4个最小元素之前的部分序列(6，7，9，11)，使用所选择的算法实现时，要执行(54)次比较。
选项 A、13
B、34
C、269
D、以上都不对
答案B
解析 采用堆排序最合适。依题意可知，只需取得第A个最小元素之前的排序序列，堆排序的时间复杂度为O(n+A×log2n)，若k≤n/ log2n，则时间复杂度为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次。
转载请注明原文地址:https://www.kaotiyun.com/show/hDxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)