2、方法是()。A.直接插入排序B.起泡排序C.快速排序D.简单选择排序【解答】D3.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序的过程中的变化为(1)8447251521(2)1547258421(3)1521258447(4)1521254784则采用的排序是()。A.选择B.冒泡C.快速D.插入【解答】A4.下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆【解答】C5.一组记录的关键码为(46,79,56,38,40
3、,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为()。A.(38,40,46,56,79,84)B.(40,38,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)【解答】C6.下列排序算法中,在待排序数据已有序时,花费时间反而最多的是()排序。A.冒泡B.希尔C.快速D.堆【解答】C7.就平均性能而言,目前最好的内排序方法是()排序法。A.冒泡B.希尔插入C.交换D.快速【解答】D8.下列排序算法中,占用辅助空间最
4、多的是:()A.归并排序B.快速排序C.希尔排序D.堆排序【解答】A9.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进行()次比较。A.3B.10C.15D.25【解答】C10.快速排序方法在()情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序【解答】D11.下列四个序列中,哪一个是堆()。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,2
5、0,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,15【解答】C12.有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为()A.-1,4,8,9,20,7,15,7B.-1,7,15,7,4,8,20,9C.-1,4,7,8,20,15,7,9D.A,B,C均不对。【解答】C二、填空题1.在索引顺序表中首先查找________,然后查找相应的_______.其平均查找长度等于____。【解答】索引表,块,查找
6、索引表的平均长度与检索相应块的平均查找长度的和2.若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保持不变,则称这种排序方法是________的,否则称为________的。【解答】稳定、不稳定3.按照排序过程涉及的存储设备的不同,排序可分为________排序和________排序。【解答】内部、外部4.直接插入排序用监视哨的作用是___________________________。【解答】免去查找过程中每一步都要检测整个表是否查找完毕,提高了查找效率。5.对n
7、个记录的表r[1..n]进行简单选择排序,所需进行的关键字间的比较次数为_______。【解答】n(n-1)/2三、算法设计题1.一个线性表中的元素为正整数或负整数。设计算法将正整数和负整数分开,使线性表的前一半为负整数,后一半为正整数。不要求对这些元素排序,但要求尽量减少比较次数。【解答】本题的基本思想是:先设置好上、下界和轴值,然后分别从线性表两端查找正数和负数,找到后进行交换,直到上下界相遇。算法如下void exampoe (Elemtype a[n]) { i=1,j=n; /*i,
8、j为左右边界*/ while(i0)) j--; /*在右边界找负数*/ if(i