足彩彩票网站建设,云南公共资源交易中心,上海人才网官网,官网建站合作模版目录 一、选择填空判断题题型一#xff08;插入排序——直接插入排序#xff09;题型二#xff08;插入排序——折半插入排序#xff09;题型三#xff08;插入排序——希尔排序#xff09;题型四#xff08;交换排序——冒泡排序#xff09;题型五#xff08;交换排序… 目录 一、选择填空判断题题型一插入排序——直接插入排序题型二插入排序——折半插入排序题型三插入排序——希尔排序题型四交换排序——冒泡排序题型五交换排序——快速排序 一、选择填空判断题
题型一插入排序——直接插入排序 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)。
题型二插入排序——折半插入排序 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)。
题型三插入排序——希尔排序 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、对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、多选以下算法中每趟排序时都能确定一个元素的最终排序位置的算法有。 A、直接插入排序 B、折半插入排序 C、希尔排序 D、冒泡排序 E、快速排序 F、简单选择排序 G、堆排序 解析D、F、G 冒泡排序、简单选择排序、堆排序每趟可确定一个元素的最终位置堆排序中每趟形成整体有序的子序列而快速排序只是确定枢轴元素的最终位置。
题型五交换排序——快速排序 1、对n个元素进行快速排序若每次划分得到的左右子区间中的元素个数相等或只差一个则排序的时间复杂度为。 A、O(1) B、O(nlog2n) C、O(n2) D、O(n) 解析B 快速排序是对冒泡排序的一种改进算法它又称为分区交换排序通过多次划分操作来实现排序思想。每一趟排序中选取一个关键字作为枢轴枢轴将待排序的序列分为两个部分比枢轴小的元素移到其前比枢轴大的元素移到其后这是一趟快速排序然后分别对两个部分按照枢轴划分规则继续进行排序直至每个区域只有一个元素为止最后达到整个序列有序。 当每次划分很平均时即最好时间复杂度为O(n2)而当序列原本正序或逆序时此时性能最差由于每次选择的都是最靠边的元素即最坏时间复杂度为O(nlog2n)故快速排序的平均时间复杂度为O(nlog2n)。
