2. 计算机
  3. 设有n个结点进行排序，不稳定排序是(1)；快速排序的最大比较次数是(2)。

设有n个结点进行排序，不稳定排序是(1)；快速排序的最大比较次数是(2)。

admin2019-04-09  70
问题 设有n个结点进行排序，不稳定排序是(1)；快速排序的最大比较次数是(2)。
选项 A、n1og2n
B、n2
C、n2/2
D、n
答案B
解析 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字
的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。题目选项中，只有shell排序是不稳定的。第1空的正确答案为选项C。
   快速排序利用分治法的基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。它的最坏情况是，每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
   Cmax=n(n-1)/2=n2
   第2空的正确答案为选项B。
转载请注明原文地址:https://kaotiyun.com/show/vCVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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