免费黄页网站,淄博网站建设优化运营,广州小程序开发的公司,wordpress flatsome目录 一、选择题题型一 #xff08;插入排序#xff09;1、直接插入排序2、折半插入排序3、希尔排序 题型二#xff08;交换排序#xff09;1、冒泡排序2、快速排序 题型三#xff08;选择排序#xff09;1、简单选择排序~2、堆排序 ~题型四#xff08;归并排序#xf… 目录 一、选择题题型一 插入排序1、直接插入排序2、折半插入排序3、希尔排序 题型二交换排序1、冒泡排序2、快速排序 题型三选择排序1、简单选择排序~2、堆排序 ~题型四归并排序 一、选择题
题型一 插入排序
1、直接插入排序 1、对n个元素进行直接插入排序需要进行趟处理。 A、n B、n1 C、n-1 D、2n 解析C 直接插入排序是将要排序的序列按照关键字的大小插入至已排好序的子序列中一直进行直到整个序列有序所以对n个元素进行直接插入排序一共插入元素n-1次需要进行n-1趟。 2、对5个不同的数据元素进行直接插入排序则最多需要进行的比较次数为。 A、8 B、10 C、15 D、25 解析B 考虑最坏情况下为最多需要进行的比较次数即序列元素呈逆序排列时最多由于此时从前到后依次需要比较1次、2次、3次、……、n-1次所以n(n-1)/2(5×4)/210。 3、对n个元素进行直接插入排序最好情况下的时间复杂度为最坏情况下的时间复杂度为。 A、O(n)O(n2) B、O(n2)O(n) C、O(n)O(n) D、O(n2)O(n2) 解析A 最好情况下即序列元素都有序此时只需比较元素而不需移动元素比较次数为n-1次故最好时间复杂度为O(n)而最坏情况下即序列元素呈逆序排列时此时比较次数和移动次数都到达最大值均为n(n-1)/2故最坏时间复杂度为O(n2)考虑平均情况总的比较次数和移动次数约为n2/4故直接插入排序的时间复杂度为O(n2)。 4、对n个元素进行直接插入排序其空间复杂度为 A、O(n) B、O(1) C、O(n2) D、O(log2n) 解析B 直接插入排序代码如下
/*直接插入排序由小到大*/
void InsertSort(int r[],int n) {int i,j,temp;for(i1; in; i) {tempr[i]; //将要插入的元素暂存在temp中for(j0,ji-1;tempr[j];--j)r[j1]r[j]; //向后挪一位 r[j1]temp; //找到插入位置并插入}
}由于直接插入排序中只使用了辅助变量故空间复杂度为O(1)。 5、若排序的元素序列呈基本有序的前提下选用效率最高的排序算法是。 A、简单选择排序 B、快速排序 C、直接插入排序 D、归并排序 解析C 由于序列基本有序应该选用平均复杂度最小的排序算法。直接/折半插入排序、简单选择排序、冒泡排序都是简单型的排序算法平均时间复杂度均为O(n2)但最好情况下直接插入排序和冒泡排序可以达到O(n)折半插入排序可以达到O(nlog2n)堆排序、快速排序、归并排序都是改进型的排序算法所以其时间复杂度均为O(nlog2n)在最好情况下可以达到O(nlog2n)。
2、折半插入排序 1、对n个元素进行折半插入排序最好情况下的时间复杂度为最坏情况下的时间复杂度为。 A、O(n2)O(nlog2n) B、O(n)O(n2) C、O(n2)O(n) D、O(nlog2n)O(n2) 解析D 折半插入排序与直接插入排序相比减少了比较元素的次数其移动次数与直接插入排序是一样的。 先折半查找当前元素的插入位置此时的时间复杂度为O(nlog2n)然后移动插入位置之后的所有元素此时的时间复杂度为O(n2)故最好时间复杂度为O(nlog2n)而最坏情况下故最坏时间复杂度为O(n2)考虑平均情况下折半插入排序的时间复杂度仍为O(n2)。 2、对n个元素进行折半插入排序其空间复杂度为 A、O(n) B、O(1) C、O(n2) D、O(log2n) 解析B 折半插入排序代码如下
/*折半插入排序*/
void Binary_InsertSort(int r[],int n) {int i,j,temp,low,high,mid;for(i1; in; i) { tempr[i]; //将要插入的元素暂存在temp中low0;highi-1; //low和high为折半查找的范围 while(lowhigh) {mid(lowhigh)/2; //mid取中间点 if(r[mid]temp) //查找左半子表 highmid-1;else //查找右半子表 lowmid1;}for(ji-1; jhigh1; j--) //先后移动元素空出位置留给插入元素 r[j1]r[j];r[j1]temp; //找到插入位置并插入 }
}由于折半插入排序中只使用了辅助变量故空间复杂度与直接插入排序相同也为O(1)。
3、希尔排序 1、对初始数据序列(8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6)进行希尔排序。若第一趟排序结果为(1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8)第二趟排序结果为(1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9)则两趟排序采用的增 量间隔依次是。 A、31 B、32 C、52 D、53 解析D 故两趟排序采用的增量依次为5和3。 2、希尔排序的组内排序采用的是。 A、直接插入排序 B、折半插入排序 C、快速排序 D、归并排序 解析A 希尔排序也称为缩小增量排序它是通过选取一定的增量来排序的其本质还是插入排序通过增量将序列分为几个子序列然后对每个子序列进行直接插入排序当所有序列呈基本有序时再进行一次直接插入排序即完成。 3、以下排序中不稳定的排序算法是。 A、冒泡排序 B、直接插入排序 C、希尔排序 D、归并排序 解析C 由于分为不同子序列后可能会出现改变其相对位置情况所以希尔排序是不稳定的。
题型二交换排序
1、冒泡排序 1、对n个元素进行冒泡排序最好情况下的时间复杂度为最坏情况下的时间复杂度为 A、O(n2)O(n) B、O(n)O(n2) C、O(n)O(n) D、O(n2)O(n2) 解析B 最好情况下即待排序结果恰好是排序后的结果此时比较次数为n-1移动次数和交换次数都为0故最好时间复杂度为O(n)而最坏情况下即排好的序列刚好与初始序列相反呈逆序排列则此时需要进行n-1趟排序第i趟排序中要进行n-i次比较即比较次数交换次数n(n-1)/2由于每次交换都会移动3次元素从而来交换元素即移动次数为3n(n-1)/2故最坏时间复杂度为O(n2)而考虑平均情况下故冒泡排序的时间复杂度为O(n2) 2、若用冒泡排序算法对序列{10、14、26、29、41、52}从大到小排序则需要进行次比较。 A、3 B、10 C、15 D、25 解析C 元素52冒泡到最前面比较5次元素41冒泡到最前面比较4次……所以一共比较次数为5432115次。 3、若用冒泡排序算法对序列{52638}升序排序且以从后向前进行比较则第一趟冒泡排序的结果为。 A、{25368} B、{25638} C、{23568} D、{23658} 解析A 首先83符合升序不交换 36不符合升序交换此时为{52368} 23符合升序不交换 52不符合升序交换此时为{25368} 故第一趟冒泡排序的结果为{25368}。 4、多选以下算法中每趟排序时都能确定一个元素的最终排序位置的算法有。 A、直接插入排序 B、折半插入排序 C、希尔排序 D、冒泡排序 E、快速排序 F、简单选择排序 G、堆排序 解析D、F、G 冒泡排序、简单选择排序、堆排序每趟都可以确定一个元素的最终排序位置堆排序中每趟形成整体有序的子序列而快速排序只是确定每趟排序中枢轴元素的最终位置。
2、快速排序 1、对n个元素进行快速排序若每次划分得到的左右子区间中的元素个数相等或只差一个则排序的时间复杂度为。 A、O(1) B、O(nlog2n) C、O(n2) D、O(n) 解析B 快速排序是对冒泡排序的一种改进算法它又称为分区交换排序通过多次划分操作来实现排序思想。每一趟排序中选取一个关键字作为枢轴枢轴将待排序的序列分为两个部分比枢轴小的元素移到其前比枢轴大的元素移到其后这是一趟快速排序然后分别对两个部分按照枢轴划分规则继续进行排序直至每个区域只有一个元素为止最后达到整个序列有序。 当每次划分很平均时即最好时间复杂度为O(nlog2n)而当序列原本正序或逆序时此时性能最差由于每次选择的都是最靠边的元素即最坏时间复杂度为O(n2)故快速排序的平均时间复杂度为O(nlog2n)。 2、快速排序算法在情况下最不利发挥其长处。 A、要排序的数据量太大 B、要排序的数据中含有多个相同值 C、要排序的数据个数为奇数 D、要排序的数据已基本有序 解析D 快速排序算法的时间复杂度与递归层数有关为O(n×递归层数)即取决于递归深度若每次划分越均匀则递归深度越低越不均匀则递归深度越深。可知当初始序列有序或逆序时快速排序的性能最差其每次选择的都是最靠序列两边的元素所划分的区域有一边为空所以初始序列越接近无序或基本上无序此时算法效率越高越接近有序或基本上有序算法效率越低。 3、下列4种排序算法中关键字平均比较次数最少的是。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 解析C 快速排序的最好时间复杂度为O(nlog2n)与其在平均情况下的所需时间最接近与最坏情况O(n2)相比较远所以快速排序是所有内部排序算法中平均性能最优的排序算法其平均比较次数最少。 4、对n个关键字进行快速排序最大递归深度为最小递归深度为。 A、n1 B、nlog2n C、log2n1 D、log2nnlog2n 解析B 由于快速排序代码中的递归进行需要栈来辅助所以其需要的空间较大这一点与其他排序算法相较特殊。其空间复杂度与递归层数栈的深度有关为O(递归层数)。
二叉树的最大/小高度
若将n个要排序的元素组成一个二叉树
这个二叉树的层数就是递归调用的层数栈的深度
由于在n个结点的二叉树中其最小高度⌊ log2n ⌋
以2为底n的对数然后再向上取整取比自己大的最小整数
其最大高度n。所以其情况与二叉树一样最好情况下为最小高度为⌊ log2n ⌋层即最小递归深度而最坏情况下为最大高度为n层即最大递归深度。 5、对n个元素的序列进行快速排序时其空间复杂度为。 A、O(n) B、O(n2) C、O(log2n) D、O(1) 解析C 最好情况下为最小高度为⌊ log2n ⌋即最小递归深度此时最好空间复杂度为O(log2n)而最坏情况下为最大高度即最大递归深度为n层此时最坏空间复杂度为O(n)故平均空间复杂度为O(log2n)。 6、设一组初始记录关键字序列{58632}以第一个记录关键字5为基准进行一趟从大到小快速排序的结果为。 A、{23586} B、{23568} C、{32586} D、{32568} 解析B 以第一个元素5为枢轴原位置空出i和j指向序列的头、尾元素开始进行第一趟快速排序 整个过程保证i指针左边是比枢轴元素小的元素j指针右边是比枢轴元素大的元素j指针找小于i指针找大于。首先对于j从右往左一直寻找找到小于枢轴元素的元素若找到则j停下由于元素2大于枢轴元素5此时j的值与i的值交换 然后对于i从左往右一直寻找找到大于枢轴元素的元素若找到则i停下由于元素2小于则继续向右到元素8停下85 j继续移动由于元素8大于则继续向左到元素3停下35此时j与i交换 …………重复步骤 j继续移动此时i与j相遇最终位置即是枢轴元素的位置 故快速排序的结果为{23568}。
题型三选择排序
1、简单选择排序 1、下列4种排序方法中排序过程中的比较次数与序列的初始状态无关的是。 A、选择排序法 B、插入排序法 C、快速排序法 D、冒泡排序法 解析A 选择排序的比较次数始终与初始序列无关。 2、对n个元素进行简单选择排序时间复杂度为。 A、O(n) B、O(n2) C、O(log2n) D、O(nlog2n) 解析B 在每一趟的简单选择排序过程中每次从未排序的序列中选取当前元素最小的元素将其作为有序子序列的第ii1……个元素加入到已排好序列的末尾依次进行下去即和第一个元素交换依次进行交换直到剩余一个元素此时整个序列已经有序每一趟简单选择排序可确定一个元素的最终位置。
所以相较于其他排序算法其元素比较次数与初始序列无关每次的比较次数分别是n-1n-2……21即n(n-1)/2n2/2故时间复杂度始终为O(n2)。 2、对n个元素进行简单选择排序其比较次数和移动次数分别为。 A、O(n)O(log2n) B、O(log2n)O(n2) C、O(n2)O(n) D、O(nlog2n)O(n) 解析C 简单选择排序的比较次数与初始序列无关始终为O(n2)而移动次数与初始序列有关。当初始序列为正序时为最好情况此时移动次数最少即无需移动移动次数为0次而当序列逆序时为最坏情况此时移动次数最多为3(n-1)次故平均移动次数为O(n)。
~2、堆排序 1、堆排序是一种排序。 A、交换 B、选择 C、插入 D、归并 解析B 2、下列4个序列中哪一个是堆。 A、704060251020155 B、706040525201510 C、706025102040155 D、704060520251510 解析A 堆排序是利用堆树来进行排序可以将其视为一棵完全二叉树树中每一个结点均大于或等于其两个子结点的值根结点是堆树中的最小值或最大值即对应小根堆和大根堆其定义如下表
堆条件大根堆完全二叉树中根≥左右小根堆完全二叉树中根≤左右
将题中的序列通过堆画出序列中第一个元素为堆的根结点均为元素70 可知其中B、C、D选项不符合大根堆的定义且也不是小根堆所以正确选项为A。 3、假定对元素序列{7359112}进行堆排序并且采用小根堆则由初始数据构成的初始堆为。 A、1357912 B、1359712 C、1537912 D、1539127 解析B 初始小根堆不满足小根堆所以进行调整 对于一个小根堆检查所有非终端结点是否满足大根堆的要求根结点≤左孩子,右孩子不满足则进行调整若当前结点的元素大于左、右孩子中较小者元素则将当前结点与较小者元素进行交换使该子树成为堆若因元素交换破坏了下一级的堆顺序使不满足堆的性质则向下继续进行调整。
由于N6可得非叶子结点的编号i≤⌊N/2 ⌋⌊6/2 ⌋3检查所有非终端结点是否满足小根堆的要求即检查i≤3的结点且按照从下往上的顺序依次检查。 i3结点5满足要求无需进行调整。 i2结点3不满足要求所以将其与左、右孩子中较小者元素进行交换即结点3与1交换如下 i1结点7不满足要求即与子结点中较小者1进行交换如下 可见调整后的结点7又不满足条件需要再次调整结点7与其子结点中较小的元素交换即7与3交换如下 故最终的初始堆序列为{1359712}。 4、假定一个初始堆为(15391271510)则进行第一趟堆排序后再重新建堆得到的结果为。 A、35791210151 B、35971210151 C、37591210151 D、35712910151 解析A 由初始堆序列可知该堆是小根堆完全二叉树中根≤左右如下 进行堆排序堆排序的步骤如下在建立根堆后将堆中堆顶元素与堆的最后一个元素进行交换堆顶元素进入有序序列到达最终位置从无序序列中被排出符合选择排序的过程然后对剩下的无序序列继续进行调整依次进行下去……直到无序序列中剩余最后一个元素此时整个序列已经有序堆排序结束。 1、第一趟将堆顶元素与堆的最后一个元素进行交换将堆顶元素加入有序子序列即1与10交换 显而易见交换后的完全二叉树不满足小根堆的定义此时对排出后剩下的完全进行调整 5、构建n个记录的初始堆其时间复杂度为进行堆排序其时间复杂度为。 A、O(n)O(log2n) B、O(n)O(nlog2n) C、O(n2)O(log2n) D、O(n2)O(nlog2n) 解析B 初始建堆的时间复杂度为O(n)建堆过程中元素对比次数不超过4nn-1趟交换和建堆过程中根结点最多下坠h-1层每下坠一层最多只需对比元素两次每一趟不超过O(h)O(log2n)即堆排序的时间复杂度为O(nlog2n)故堆排序的时间复杂度为O(n)O(nlog2n)O(nlog2n)。 6、向具有n个结点的堆中插入一个新元素的时间复杂度为删除一个元素的时间复杂度为。 A、O(log2n)O(log2n) B、O(nlog2n)O(nlog2n) C、O(1)O(log2n) D、O(n)O(nlog2n) 解析A 对堆进行插入操作时将要插入的结点放在堆的末尾插入后整个完全二叉树仍需满足堆的要求对该结点进行向上调整每次上升操作需对比元素1次由于完全二叉树的高度为h⌊log2n⌋1所以向n个结点的堆中插入一个新元素的时间复杂度为O(log2n)。
对堆进行删除操作时删除的结点的位置就会空出来此时需要将堆的末尾元素填到该位置然后下调至合适位置每次下调需对比元素1次或2次删除操作也是取决于树的高度即时间复杂度为O(log2n)。 7、对n个元素的序列进行堆排序时所需要的附加存储空间是。 A、O(n) B、O(n2) C、O(log2n) D、O(1) 解析D 在建立根堆后将堆中堆顶元素与堆的最后一个元素进行交换堆顶元素进入有序序列到达最终位置从无序序列中被排出符合选择排序的过程然后对剩下的无序序列继续进行调整依次进行下去……直到无序序列中剩余最后一个元素此时整个序列已经有序堆排序结束。堆排序的代码如下
/*堆排序*/
void HeapSort(int r[],int n){int i,temp;for(in/2;i1;i--) //建立初始堆 Adjust(r,i,n);for(in;i1;i--){ //进行n-1次循环完成堆排序 tempr[1]; //将堆中最后一个元素与堆顶元素交换将其放入最终位置 r[1]r[i];r[i]temp;Adjust(r,1,i-1); //对剩下的无序序列进行调整 }
}由于只需要常数个辅助单元所以空间复杂度为O(1)。 8、若只想的带1000个元素组成的序列中第10个最小元素之前的部分排序的序列用方法最快。 A、冒泡排序 B、快速排序 C、希尔排序 D、堆排序 解析D 通常在一大堆数据中取k个最大/最小元素时一般采用堆排序由于其只需要调整10次大/小根堆其时间与形成的树的高度成正比。
~题型四归并排序 1、下列排序算法中占用辅助空间最多的是。 A、快速排序 B、归并排序 C、堆排序 D、冒泡排序 解析B 归并排序的代码如下
/*归并*/
void Merge(int r[],int low,int mid,int high) {int *r1(int *)malloc((high-low1)*sizeof(int)); //辅助数组r1 for(int klow; khigh; k)r1[k]r[k]; //将r中的所有元素复制到r1中 for(ilow,jmid1,ki; imidjhigh; k) {//low指向为第一个有序表的第一个元素j指向第二个有序表的第一个元素if(r1[i]r1[j]) //比较r1的左右两段中的元素 r[k]r1[i]; //将较小值复制到r1中 elser[k]r[j];}while(imid)r[k]r1[i]; //若第一个表没有归并完的部分复制到尾部 while(ihigh)r[k]r1[j]; //若第二个表没有归并完的部分复制到尾部
}/*归并排序*/
void MergeSort(int r[],int low,int high) {if(lowhigh) {int mid(lowhigh)/2; //划分 MergeSort(r,low,mid); //对左有序子表递归 MergeSort(r,mid1,high); //对右有序子表递归 Merge(r,low,mid,high); //归并}
}该算法中用到了递归工作栈递归工作栈的空间复杂度为O(log2n)另外还需用到辅助数组其空间复杂度为O(n)所以归并排序算法的空间复杂度为O(n)。而快速排序的平均空间复杂度为O(log2n)堆排序、冒泡排序的空间复杂度为均O(1)。
