数据结构与算法第十二单元测试题附答案

数据结构与算法第十二单元测试题1、排序可以分为四大类，主要包含有()。A插入排序(正确答案)B交换排序(正确答案)C选择排序(正确答案)D归并排序(正确答案)2、按照排序中具有相同关键字的记录在排序前后的相对位置是否发生改变，排序分为()。A稳定排序(正确答案)B不稳定排序(正确答案)C外部排序D内部排序3、排序是稳定排序或不稳排序的插入排序是()。A希尔排序(正确答案)B直接插入排序(正确答案)C堆排序D快速排序4、属于插入排序的有()。A希尔排序(正确答案)B直接插入排序(正确答案)C冒泡排序D简单选择排序5、直接插入排序是()。A内排序(正确答案)B稳定排序(正确答案)C时间复杂度为O(nn)的排序(正确答案)D插入排序(正确答案)6、序列(12,9,14,7,8)经过一趟直接排序，结果不可能是()。A12,9,14,7,8(正确答案)B9,12,14,7,8C7,8,9,12,14(正确答案)D9,7,8,12,14(正确答案)7、直接插入排序最好、最坏两种情况的时间复杂度分别是()。AO(nlog2n)BO(nn)(正确答案)CO(log2n)DO(n)(正确答案)8、按照待排记录是否全部在内存中，排序可分为()。A内排序(正确答案)B外排序(正确答案)C稳定排序D不稳定排序9、希尔排序就稳定性和内外排序而言，属于()。A稳定排序B不稳定排序(正确答案)C内排序(正确答案)D外排序10、希尔排序的时间复杂度不可能是()。AO(nn)(正确答案)BO(nlog2n)(正确答案)CO(n)(正确答案)DO(n3/2)11、下列排序中属于插入排序的有()。A希尔排序(正确答案)B直接插入排序(正确答案)C快速排序D简单选择排序12、12个待排记录，使用直接插入排序需要()趟能完成全部排序。A11(正确答案)B12C10D都不对13、所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为()。A外部排序(正确答案)B内部排序C插入排序D交换排序14、数组中有25个元素，若使用直接插入排序对其进行排序，则需要()趟才能完成排序。A24(正确答案)B25C26D2315、N个记录采用直接插入排序的最好的情况是记录完全有序，只要比较()次，不需要插入就可以排序完成。ANBN-1(正确答案)CN-2DN(N-1)/216、哪种排序可能发生：在最后一趟排序开始之前，所有记录均不在其最终位置上()。A直接插入排序(正确答案)B简单选择排序C冒泡排序D快速排序17、所有的记录都能存放在内存中进行排序，称为()。A外部排序B内部排序(正确答案)C插入排序D交换排序18、直接插入排序的稳定性和时间复杂度分别是()。A稳定排序且时间复杂度是O(nn)(正确答案)B不稳定排序且时间复杂度是O(n)C稳定排序且时间复杂度是O(log2n)D不稳定排序且时间复杂度是O(log2n)19、直接插入排序的时间复杂度和顺序查找的时间复杂度分别是()。AO(n)和O(log2n)BO(nn)和O(n)(正确答案)CO(1)和)O(n)DO(n)和O(1)20、在排序中，对于关键字相等的记录，排序前后相对位置不变。这时称排序为()。A"稳定排序"(正确答案)B不稳定排序C不确定是稳定排序还是不稳定排序D基数排序21、数组中有30个元素，若使用直接插入排序对其进行排序，则需要()趟才能完成排序。A29(正确答案)B30C28D2722、N个记录采用直接插入排序(按从小到大排序)的最好的情况是记录完全有序，只要比较N-1次，不需要插入就可以排序完成，这种情况是()。A记录初始状态已经按照从小到大有序排列了。(正确答案)B记录初始状态已经按照从大到小有序排列了。C记录初始状态是乱序D记录初始状态前一半是有序，后一半是乱序23、排序前序列为：3415886672问经过一趟直接插入排序(按从小到大排序)后的序列是()。A1534886672(正确答案)B3415886672C1534667288D153466887224、直接插入排序的时间复杂度和稳定性分别是()。A时间复杂度是O(nn)且稳定排序(正确答案)B间复杂度是O(n)且是不稳定排序C时间复杂度是O(log2n)且是稳定排序D间复杂度是O(log2n)且是不稳定排序25、直接插入排序的时间复杂度和折半查找的时间复杂度分别是()。AO(nn)和O(log2n)(正确答案)BO(nn)和O(n)CO(1)和)O(n)DO(n)和O(1)26、19个记录进行排序，使用直接插入排序需要()趟能完成全部排序。A18(正确答案)B19C17D都不对27、就排序记录所在位置而言，希尔排序排序属于()。A外排序B内排序(正确答案)C稳定排序D交换排序28、希尔排序是一种插入排序，希尔排序又称为()。A缩小增量排序(正确答案)B多路插入排序C直接插入排序D冒泡排序29、下列选项关于内外排序说法正确的是()。A所有的记录都能存放在内存中进行排序，称为外部排序B所有的记录都能存放在内存中进行排序，称为内部排序(正确答案)C所有的记录都能存放在内存中进行排序，称为插入排序D所有的记录都能存放在内存中进行排序，称为交换排序30、下列选项关于直接插入排序思想说法正确的是()。A将第一个记录看成有序的，将之后的记录逐一插入，是有序序列扩大，直到全部有序是冒泡排序的思想B将第一个记录看成有序的，将之后的记录逐一插入，是有序序列扩大，直到全部有序是直接插入排序的思想(正确答案)C将第一个记录看成有序的，将之后的记录逐一插入，是有序序列扩大，直到全部有序是简单选择排序的思想31、下列选项关于直接插入排序的分类说法正确的是()。A直接插入排序属于四大排序类型中的插入排序(正确答案)B直接插入排序属于四大排序类型中的选择排序C直接插入排序属于四大排序类型中的交换排序D直接插入排序属于四大排序类型中的归并排序32、下列选项关于直接插入排序比较次数说法正确的是()。AN个记录采用直接插入排序的最好的情况是记录倒序只要比较N-1次，不需要插入就可以排序完成BN个记录采用直接插入排序的最好的情况是记录有序只要比较N-1次，不需要插入就可以排序完成(正确答案)CN个记录采用直接插入排序的最好的情况是记录乱序只要比较N-1次，不需要插入就可以排序完成DN个记录采用直接插入排序的最好的情况是记录顺序只要比较N-1次，不需要插入就可以排序完成33、关于直接插入排序的排序趟数下面说法正确的是()。A数组中有25个元素，若使用直接插入排序对其进行排序，则需要24趟才能完成排序(正确答案)B数组中有25个元素，若使用直接插入排序对其进行排序，则需要25趟才能完成排序C数组中有25个元素，若使用直接插入排序对其进行排序，则需要26趟才能完成排序D数组中有25个元素，若使用直接插入排序对其进行排序，则需要23趟才能完成排序34、N个记录采用直接插入排序说法正确的是()。AN个待排记录，使用直接插入排序需要N-1趟能完成全部排序(正确答案)BN个待排记录，使用直接插入排序需要N趟能完成全部排序CN个待排记录，使用直接插入排序需要N-2趟能完成全部排序35、直接插入排序的时间复杂度是()。AO(nlog2n)BO(nn)(正确答案)CO(log2n)DO(n)36、直接插入排序的稳定性如何()。A是稳定排序(正确答案)B是不稳定排序C有时是稳定的，有时不稳定D以上说法都不对37、下列选项中关于稳定排序说法正确的是()。A稳定排序是指对于关键字相等的记录，排序前后相对位置不变(正确答案)B稳定排序是指对于关键字相等的记录，排序前后相对位置可以变化C稳定排序是指排序是指将记录变成无序的38、排序前序列为：11101389问经过一趟直接插入排序(按从小到大排序)后的序列是()。A10111389(正确答案)B10118913C11108913D8910111339、希尔排序就分类而言属于()。A归并排序B选择排序C交换排序D插入排序(正确答案)40、就性能而言，希尔排序的时间复杂度是()。AO(nn)BO(nlog2n)CO(n)DO(n3/2)(正确答案)41、希尔排序又称为()。A缩小增量排序(正确答案)B二分插入排序C多路归并排序D锦标赛排序42、希尔排序是根据增量，将所有记录分为若干个组，每组采用()排序进行排序。A直接插入排序(正确答案)B冒泡排序C快速排序D简单选择排序43、关于希尔排序的描述正确的是()。A希尔排序是稳定排序B希尔排序是交换排序的一种C希尔排序是一种插入排序(正确答案)D希尔排序的时间复杂度是O(nn)44、希尔排序是一种不稳定排序，那么原因是()。A存在不相邻记录的交换(正确答案)B存在相邻记录的交换C存在相同关键字的记录D存在着记录顺序的一次调换45、希尔排序与直接插入排序相同之处是()。A它们都是稳定排序B它们的时间复杂度是一样的C它们都是插入排序大类里的(正确答案)D它们都是缩小增量排序46、直接插入排序的稳定性和希尔排序的稳定性是()。A一样的B不一样(正确答案)C可能一样也可能不一样D不确定47、希尔排序就稳定性而言属于()。A稳定排序B不稳定排序(正确答案)C可能是稳定的也可能是不稳定，根据情况不同而不同D其它选项都不对48、希尔排序属于不稳定排序，而直接插入排序是稳定排序，他们都是插入排序。对(正确答案)错49、排序只有外部排序没有内部排序。对错(正确答案)50、直接插入排序是一种不稳定排序。对错(正确答案)51、直接插入排序是不稳定排序而且时间复杂度是O(nn)。对错(正确答案)52、直接插入排序必须需要使用switch语句才能实现。对错(正确答案)53、在直接插入排序中可以使用循环嵌套来完成。对(正确答案)错54、就排序稳定性而言，希尔排序是不稳定排序。对(正确答案)错55、希尔排序的时间复杂度是O(nn)。对错(正确答案)56、希尔排序又叫缩小增量排序，属于交换排序的一种。对错(正确答案)57、希尔排序属于不稳定排序，而直接插入排序是稳定排序。对(正确答案)错58、直接插入排序必须需要使用continue才能实现。对错(正确答案)59、在直接插入排序中可以使用for循环来完成。对(正确答案)错60、直接插入排序是不稳定排序。对