《2022年数据结构排序习题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构排序习题 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、07排序【单选题】1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。A、直接插入B、简单选择C、希尔D、二路归并2.直接插入排序在最好情况下的时间复杂度为（B）。A、O(logn)B、O(n)C、O(n*logn)D、O(n2)3.设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（B）。A、79,46,56,38,40,80B、84,79,56,38,40,46 C、84,79,56,46,40,38D、84,56,79,40,46,38 4.设有一组关键字值（46,79,56
2、,38,40,84），则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。A、38,40,46,56,79,84B、40,38,46,79,56,84 C、40,38,46,56,79,84D、40,38,46,84,56,79 5.将两个各有n 个元素的有序表归并成一个有序表，最少进行（A）次比较。A、nB、2n-1C、2nD、n-1 6.下列排序方法中，排序趟数与待排序列的初始状态有关的是（C）。A、直接插入B、简单选择C、起泡D、堆7.下列排序方法中，不稳定的是（D）。A、直接插入B、起泡C、二路归并D、堆8.若要在 O(nlog2n)的时间复杂度上完成排序，且要求排序是稳
3、定的，则可选择下列排序方法中的（C）。A、快速B、堆C、二路归并D、直接插入9.设有 1000 个无序的数据元素，希望用最快的速度挑选出关键字最大的前10 个元素，最好选用（C）排序法。A、起泡B、快速C、堆D、基数10.若待排元素已按关键字值基本有序，则下列排序方法中效率最高的是（A）。A、直接插入B、简单选择C、快速D、二路归并11.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（C）的两趟排序后的结果。A、选择排序B、冒泡排序C、插入排序D、堆排序12.（A）占用的额外空间的空间复杂性为(1)。A、堆排序算法B、归并排序算法C、快速排序算法D、以上答案都不对名师
4、资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -13.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21（2）15 47 25 84 21（3）15 21 25 84 47（4）15 21 25 47 84 则采用的排序是（A）。A、选择B、冒泡C、快速D、插入14.一个排序算法的时间复杂度与（B）有关。A、排序算法的稳定性B、所需比较关键字的次数C、所采用的存储结构D、所需辅助存储空间的大小15.适合并行处理的排序算法是（B）。A、选择排序B、快速排序C、希尔排序D、基数排序16.下列排序算法中，（A）算
5、法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。A、快速排序B、堆排序C、希尔排序D、起泡排序17.有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是（A）。A、希尔排序B、堆排序C、起泡排序D、快速排序18.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A）。A、直接插入排序B、起泡排序C、简单选择排序D、快速排序19.下列排序算法中，（D）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A、堆排序B、冒泡排序C、快速排序D、插入排序20.下列排序算法中，占用辅助空间最多的是（A）。A、归并排
6、序B、快速排序C、希尔排序D、堆排序21.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。A、插入B、选择C、希尔D、二路归并22.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（C）。A、94,32,40,90,80,46,21,69B、32,40,21,46,69,94,90,80 C、21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,40 23.对序列 15，9，7，8，20，-1，4用希尔排序方法排序，经一趟后序列变为15，-l，4，8，2
7、0，9，7 则该次采用的增量是（B）。A、lB、4C、3D、2 24.在含有 n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D）位置上。A、n/2B、n/2 -1C、1D、n/2 +2 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -25.对 n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（A）。A、每次分区后，先处理较短的部分B、每次分区后，先处理较长的部分C、与算法每次分区后的处理顺序无关D、以上三者都不对26.从堆中删除一个元素的时间复杂度为（B）。A、O(1)B、O(log2n)C、O(n)D、O(nlog2n)名师
8、资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -【计算题】1.设有关键字序列（503，087，512，061，908，170，897，275，653，426），试用下列各内部排序方法对其进行排序，要求写出每趟排序结束时关键字序列的状态。(1)直接插入法；解：初始：503，087，512，061，908，170，897，275，653，426 第一趟：087，503，512，061，908，170，897，275，653，426 第二趟：087，503，512，061，908，170，897，275，653，426 第三趟：061，087，503，512，908，170，89
9、7，275，653，426 第四趟：061，087，503，512，908，170，897，275，653，426 第五趟：061，087，170，503，512，908，897，275，653，426 第六趟：061，087，170，503，512，897，908，275，653，426 第七趟：061，087，170，275，503，512，897，908，653，426(2)希尔排序法，增量序列为（5，3，1）；解：初始：503，087，512，061，908，170，897，275，653，426 第一趟：170，087，275，061，426，503，897，512，653，908
10、第二趟：061，087，275，170，426，503，897，512，653，908 第三趟：061，087，170，275，426，503，512，653，897，908(3)快速排序法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：426，087，275，061，170，503，897，908，653，512第二趟：170，087，275，061，426，503，512，653，897，908第三趟：061，087，170，275，426，503，512，653，897，908 第四趟：061，087，170，275，426，503，51
11、2，653，897，908(4)堆排序法；解：初始：503，087，512，061，908，170，897，275，653，426 第一趟：908，653，897，503，426，170，512，275，061，087 第二趟：897，653，512，503，426，170，087，275，061，908 第三趟：653，503，512，275，426，170，087，061，897，908 第四趟：512，503，170，275，426，061，087，653，897，908 第五趟：503，426，170，275，087，061，512，653，897，908 第六趟：426，275，17
12、0，061，087，503，512，653，897，908 第七趟：275，087，170，061，426，503，512，653，897，908 第八趟：170，087，061，275，426，503，512，653，897，908 第九趟：087，061，170，275，426，503，512，653，897，908 第十趟：061，087，170，275，426，503，512，653，897，908 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -(5)二路归并排序法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟
13、：087，503，061，512，170，908，275，897，426，653第二趟：061，087，503，512，170，275，897，908，426，653第三趟：061，087，170，275，503，512，897，908，426，653第四趟：061，087，170，275，426，503，512，653，897，908名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -【算法题】下列算法题中可能用到的类如下：public class SortTable private int st;public SortTable(int length)int i;st=
14、new intlength;for(i=0;isti+1，则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。解：public void oesort()boolean change=true;int temp;while(change)change=false;for(i=0;ist.length;i+=2)if(sti+1sti)change=true;temp=sti+1;sti+1=sti;sti=temp;/if/for for(i=1;ist.length;i+=2)if(sti+1sti)change=true;temp=sti+1;sti+1=sti;sti=temp
15、;/if/for/while/oesort(2)设待排数据元素的值互不相同，对它们按计数排序法进行排序，方法为：另设数组count，对每个元素 sti，统计关键字值比它小的元素个数存于counti，再依 counti 值的大小对st 中元素进行重排。解：public void countSort()/计数排序算法int c=new int st.length;for(i=0;ist.length;i+)ci=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -for(i=0;ist.length-1;i+)for(j=i+1;jst.length;j+)/对每一对元素i
16、f(aiaj)cj+;else ci+;for(i=0;in;i+)/依次求出关键字最小,第二小,.,最大的记录min=0;for(j=0;jn;j+)if(cjcmin)min=j;/求出最小记录的下标min aiamin;/与第 i 个记录交换cmin=INFINITY;/修改该记录的c 值为无穷大以便下一次选取cicmin;/for/countSort(3)判定 st 中元素序列是否为堆（设st0中未保存有效数据元素）。(4)实现非递归的快排算法。(5)实现改进的归并排序：对st 中数据元素，若有sti sti+1 stj，0ijst.length-1，则把sti.stj 作为一个初始待归并序列，然后进行二路归并。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -