计算机类
单选题下列内部排序算法中在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< A 快速排序B 直接插入排序C 二路归并排序D 简单选择排序E.起泡排序F.堆排序
题目
快速排序
直接插入排序
二路归并排序
简单选择排序E.起泡排序F.堆排序
相似问题和答案
第1题：
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入已排序序列中的正确位置。Insert类的成员函数sort()实现了插入排序算法，请填空。
class Insert{
public:
Insert(int*b0,int n0):b(b0),n(n0){};//参数b0是某数组首地址，n是数组元素个数
void sort()
{//此函数假设已排序序列初始化状态只包含b[0]，未排序序列初始为b[1]…b[n-1]
for(int i=1;i＜n;++i)
{
int t=b[i];
int j;
for(______;j＞0;--j)
{
if(t＞=b[j-1])
break;
b[j]=b[j-1];
b[j]=t;
}
}
}
};
j=i 解析：在函数sort()中，外层for循环中依次将数组b中的值赋值给变量t，然后在内层循环中依次与已经排序的数组元素进行比较，并在符合条件的位置插入该元素。“int t=b[i];”语句可知数组中有i个元素已经排序。因此，根据内层循环中的j＞0;--j语句，知道内层循环是将当前的第i个元素与j个元素进行比较，前面已知数组中有i个元素已经排序，根据题干中的要求“插入已排序序列中”，即j=i。
第2题：
对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用(59)，使用分治(Divide and Conquer)策略的是(60)算法。
A．希尔排序
B．直接插入排序
C．快速排序
D．堆排序
解析：本题考查排序算法及特点。对于希尔排序、直接插入排序，只有在排序过程后才能确保全部序列以及前k个元素的最终排列，快速排序采用分治算法，常用递归算法实现，该算法根据枢轴元素进行划分，第一趟划分结束后得到了两个子序列，一个序列中的元素均不大于另一个子序列中的元素，枢轴元素介于这两个子序列之间。若仅需得到最终序列的前k个元素，每次得到枢轴元素位置后再考虑下一步的排序过程，在算法的流程控制上比较复杂。对于只需得到最终序列的前k个元素，堆排序比较简单。
第3题：
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入到已排序序列中的正确位置，InsertSort 类的成员函数sort（）实现了插入排序算法，请将画线处缺失的部分补充完整。
class InsertSort{
public:
InsertSort（int*a0,int n0）:a（a0）,n（n0）{}//参数组首地址，n 是数组元素个数
void sort（）
{//此函数假设已排离序列初始化状态只包含a[0]，未排序序列初始为a[1]?a[n-1]
for （int i=1;iint j;
for（ [14] j>0;--j）{
if（t>a[j-1]）break;
a[j]=a[j-1];}
a[j]=t;}}
protected:
int*a,n;//指针a 用于存放数组首地址，n 用于存放数组元素个数
}；
i%2==0
第4题：
插入排序算法的主要思想：每次从未排序序列中取出一个数据，插入到已排序序列中的正确位置。Insert类的成员函数sort()实现了插入排序算法，请填空。
class Insert{
public:
Insert(int *b0,int n0):b(b0),n(n0)＜);//参数b0是某数组首地址，n是数组元素个数
void sort()
{//此函数假设已排序序列初始化状态只包含b[0]，未排序序列初始为b[1]...b[n-1]
for(int i=1;i＜n;++i)
{
int t=b[i];
int j;
for(______;j＞0;--j)
{
if(t＞=b[j-1])
break;
b[j]=b[j-1];
b[j]=t;
}
}
}
j=i 解析：在函数sort()中，外层for循环中依次将数组b中的值赋值给变量t，然后在内层循环中依次与已经排序的数组元素进行比较，并在符合条件的位置插入该元素。由“int t=b[i];”语句可知，数组中有i个元素已经排好了序。因此，根据内层循环中的j＞0；--j语句，知道内层循环是将当前的第i个元素与j个元素进行比较，前面已知数组中有i个元素已经排好了序，根据题干中的要求“插入到已排序序列中”，即j=i。
第5题：
以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。
A．快速排序算法是不稳定的排序算法
B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)
C．快速排序算法是一种分治算法
D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
解析：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：cmax=n(n-1)／2=O(2)在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
第6题：
● 以下关于快速排序算法的描述中，错误的是 （64） 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成，则初始排列为 （65） 时，排序效率最高（令序列的第一个元素为基准元素）。
（64）A. 快速排序算法是不稳定的排序算法
B. 快速排序算法在最坏情况下的时间复杂度为O(n1gn)
C. 快速排序算法是一种分治算法
D. 当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
（65）A. 45,12,30,25,67,52,85
B. 85,67,52,45,30,25,12
C. 12,25,30,45,52,67,85
D. 45,12,25,30,85,67,52
试题（64）、（65）分析
本题考查快速排序算法。
快速排序算法是一种经典的排序算法，其基本思想是选择一个基准元素（通常选择第一个元素或者最后一个元素），通过一趟排序将待排序序列分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的正确位置；然后再递归地排序划分的两部分，因此本质上快速排序是一种分治算法。由于在排序的过程中，各元素与基准元素比较大小，若小于基准元素则与基准元素交换位置，因此该算法是不稳定的排序算法。当每一趟排序进行后，选择的基准元素恰好最大或者最小时，就把序列分成极端不均衡的两部分，即一部分为空，另一部分为待排序序列的元素个数减1，此时算法处于最坏情况，其时间复杂度为O(n2)。当输入数据基本有序或者所有元素值相等时，不论选择第一个元素还是最后一个元素作为基准元素，都恰好把序列分成极端不均衡的两部分，快速排序算法具有最坏情况下的时间复杂度。
对于选项A，以45作为基准元素进行第一趟划分，先从后向前找出比45小的元素，67、52、85这三个元素保持不动，找到25，将其与45交换后，第一趟划分完成，序列为25,12,30,45,67,52,85。第二趟先对子序列25,12,30进行划分，使得25与12对调，形成子序列12,25,30；然后对67,52,85进行划分，使得67与52交换，形成子序列52,67,85。至此，整个排序过程完成。期间，第一趟划分中元素的比较次数为6次、交换1次，第二趟划分中元素的比较次数共4次、交换次数为2次，因此，排序过程中比较次数共10次，交换次数为3次。
对于选项B，以85作为基准元素，因12比它小，所以将85与12交换，由于剩下的元素都比85小，因此保持不动，第一趟划分之后的元素序列为12,67,52,45,30,25,85，期间元素比较次数为6次、交换1次，第二趟对85之前的6个元素进行划分，由于67、52、45、30、25都比基准元素12大，因此它们保持不动，完成第二趟划分，形成的子序列为12,67,52,45,30,25，期间比较次数为5、交换次数为0。接下来第三趟对子序列67,52,45,30,25进行划分，以67为基准元素，情况与第一趟相同，进行4次比较、l次交换后，形成子序列25,52,45,30,67。第四趟对子序列25,52,45,30进行划分，情况与第二趟相同。依此类推，完成排序时比较次数为21次（6＋5＋4＋3＋2＋1）。
对于选项C，以12作为基准元素，因为后面的所有元素都比它大，所以所有元素是持不动，第一趟划分之后的元素序列为12,25,30,45,52,67,85，期间元素比较次数为6次、交换0次。第二趟对子序列25,30,45,52,67,85进行划分，以25作为基准元素，因为后面的所有元素都比它大，所以所有元素保持不动，第一趟划分之后的元素序列为25,30,45,52,67,85，期间元素比较次数为5次、交换0次。接下来对子序列30,45,52,67,85进行划分，同理，元素保持不动，期间元素比较次数为4次、交换0次。依此类推，完成整个排序比较次数为21次、交换0次。
对于选项D，以45作为基准元素进行第一趟划分，先从后向前找出比45小的元素，85、67、52这三个元素保持不动，找到30，将其与45交换后，第一趟划分完成，序列30,12,25,45,85,67,52，期间元素比较次数为6次、交换1次。第二趟先对子序列30,12,25进行划分，以30为基准元素，30与25交换，经过2次比较、1次交换后子序列为25,12,30，需要再次对子序列25,12进行划分；同理，对子序列85,67,52进行划分后，结果为51,67,87，还需对子序列51,67进行划分。排序过程中比较次数共12次。
参考答案
（64）B（65）A
第7题：
在待排序的元素序列基本有序的前提下，效率最高的排序方法是______。
A．冒泡排序
B．选择排序
C．快速排序
D．归并排序
解析：从平均时间性能而言，快速排序最佳，其所需时间最少，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当序列中的记录基本有序或元素个数较少时，冒泡排序和简单选择排序为最佳排序方法。
第8题：
（ 14 ） 插入排序算法的主要思想是 ： 每次从未排序序列中取出一个数据 ， 插入到已排序序列中的正确位置 。
InsertSort 类的成员函数 sort() 实现了插入排序算法。请将画线处缺失的部分补充完整。
class InsertSort{
public:
InsertSort(int* a0, int n0) :a(a0), n(n0) {} // 参数 a0 是某数组首地址， n 是数组元素个数
void sort( )
{// 此函数假设已排序序列初始化状态只包含 a[0] ，未排序序列初始为 a[1]...a[n-1]
for (int i=1; i
int t=a[i];
int j;
for ( 【 14 】 ; j>0; --j){
if (t>=a[j-1]) break;
a[j]=a[j-1];}
a[j]=t;}}
protected:
int *a, n; // 指针 a 用于存放数组首地址， n 用于存放数组元素个数
};
第9题：
下列说法中错误的是：()
A.插入排序某些情况下复杂度为O(n)
B.排序二叉树元素查找的复杂度可能为O(n)
C.对于有序列表的排序最快的是快速排序
D.在有序列表中通过二分查找的复杂度一定是O(log2n)
第10题：
A.冒泡排序
B.直接插入排序
C.快速排序
D.希尔排序