《数据结构》吕云翔编著第7章排序习题解答

《《数据结构》吕云翔编著第7章排序习题解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、单项选择题1.下列内部排序算法屮:A.C.E.(1)B.直接插入排序D.简单选择排序F.堆排序(2)不稳定的排序算法是()(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k«n)的情况下，排序效率最高的算法是()(4)排序的平均时间复杂度为0(n-logn)的算法是(()【解答】(1)DC(2)ADF(3)B2.比较次数与排序的初始状态无关的排序方法是(B.起泡排序C.快速排序(2)ADF(4)ACF)为O(n*n)的算法是BDE)。D.简单选3.对一组数据(84,47,25,15,的变化为(1)

2、8447251521(2)15(3)1521258447(4)15则采用的排序是()OA.选择B.冒泡47252125A.直接插入排序择排序【解答】D【解答】A4.下列排序算法中(位置上。A.选择【解答】C21)排序，数据的排列次序在排序的过程屮84214784C.快速D.插入)排序在一趟结束后不一定能选出一个元素放在其最终B.冒泡C.归并D.堆第七章排序课后习题解答快速排序二路归并排序起泡排序其比较次数与序列初态无关的算法是()84),则利用快速排序的方法,5.一组记录的关键码为(46,79,56,38,40,以第一

3、个记录为基准得到的一次划分结果为(A.(3&40,46,56,79,84)B.(40,38,46,79,56,84)C.(40,3&46,56,79,84)D.(40,38,46,84,56,79)【解答】C6.卡切排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。A.冒泡B.希尔C.快速D.堆【解答】C7.就平均性能而言，目前最好的内排序方法是()排序法。A.冒泡B.希尔插入C.交换D.快速【解答】D&下列排序算法中，占用辅助空间最多的是：()A.归并排序B.快速排序C.希尔排序D.堆排序【解答】A9.

4、若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行()次比较。A.3B.10「解公JC10.S速排序方法在(C.15D.25)情况下最不利于发挥其长处。A.要排序的数据量太大C.要排序的数据个数为奇数【解答】D11・下列四个序列屮，哪一个是堆'A.75,65,30,15,25,45,20,10C.75,45,65,30,15,25,20,10【解答】C12.有一组数据(15,9,7,8,20,始堆为(A.-1,B.D.)4,8,9,20,7,15,7要排序的数据中含有多个相同值要排序的数据

5、己基木有序)。B.75,65,45,10,30,25,20,15D.75,45,65,10,25,30,20,15-1,7,4),用堆排序的筛选方法建立的初B.-1,7,15,7,4,8,20,9C・—1,4,7,8,20,15,7,9D・A,B,C均不对。【解答】C二、填空题1.在索引顺序表中首先查找,然后查找相应的・其平均查找长度等于。【解蓉】-索引表，块，查找索引表的平均长度与检索相应块的平均查找长度的和2.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是的

6、，否则称为的。【解答】稳定、不稳定3.按照排序过程涉及的存储设备的不同，排序可分为排序和排序。【解答】内部、外部4.直接插入排序用监视哨的作用是o【解答】免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。5.对n个记录的表进行简单选择排序，所需进行的关键字间的比较次数为o【解答】n(n-l)/2三、算法设计题1・一个线性表中的元素为正整数或负整数。设计算法将止整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少比较次数。【解答】本题的基本思想是：先设置好上、下界

7、和轴值，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上下界相遇。算法如下voidexampoe(Elemtypea[n]){i二l,j二n;/*i,j为左右边界*/while(i0))j—;/*在右边界找负数*/{tcmp=a[i];a[i]=a[j];a[j]=a[etmp];/*交换两个元素的值*/i++；j一一；2.已知(kl,k2,kn)是堆，写一个算法将(kl,k2,…,kn,k

8、n+1)调整为堆。【解答】3.给定n个记录的有序序列A[n]和ni个记录的有序序列B[m],将它们归并为一个有序序列，存放在C[m+n]中，试写出这一算法。【解答】采用二路归并排序中一次归并的思想，设三个参数i、j和k分别指向两个待归并的有序序列和最终有序序列的当前记录，初始时i、j分别指向两个有序序列的第一个记录，即i二1,j二