数据结构第九章排序习题及答案文档格式.doc
《数据结构第九章排序习题及答案文档格式.doc》由会员分享,可在线阅读,更多相关《数据结构第九章排序习题及答案文档格式.doc(4页珍藏版)》请在冰点文库上搜索。
![数据结构第九章排序习题及答案文档格式.doc](https://file1.bingdoc.com/fileroot1/2023-5/7/ede8f962-4653-41a5-9df2-ee8c7ea016dd/ede8f962-4653-41a5-9df2-ee8c7ea016dd1.gif)
(3)1521258447(4)1521254784
则采用的排序是()。
A.选择B.冒泡C.快速D.插入
4.下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A.选择B.冒泡C.归并D.堆
5.一组记录的关键码为(46,79,56,38,40,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)
6.下列排序算法中,在待排序数据已有序时,花费时间反而最多的是()排序。
A.冒泡B.希尔C.快速D.堆
7.就平均性能而言,目前最好的内排序方法是()排序法。
A.冒泡B.希尔插入C.交换D.快速
8.下列排序算法中,占用辅助空间最多的是:
()
A.归并排序B.快速排序C.希尔排序D.堆排序
9.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进行()次比较。
A.3B.10C.15D.25
10.快速排序方法在()情况下最不利于发挥其长处。
A.要排序的数据量太大B.要排序的数据中含有多个相同值
C.要排序的数据个数为奇数D.要排序的数据已基本有序
11.下列四个序列中,哪一个是堆()。
A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15
C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,15
12.有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为()
A.-1,4,8,9,20,7,15,7B.-1,7,15,7,4,8,20,9
C.-1,4,7,8,20,15,7,9D.A,B,C均不对。
二、填空题
1.若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保持不变,则称这种排序方法是________的,否则称为________的。
2.按照排序过程涉及的存储设备的不同,排序可分为________排序和________排序。
3.直接插入排序用监视哨的作用是___________________________。
4.对n个记录的表r[1..n]进行简单选择排序,所需进行的关键字间的比较次数为_______。
5.下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。
请在空框处填上适当内容,每个空框只填一个语句或一个表达式:
#include<
stdio.h>
typedefstructnode{chardata;
structnode*link;
}node;
node*select(node*head)
{node*p,*q,*r,*s;
p=(node*)malloc(sizeof(node));
p->
link=head;
head=p;
while(p->
link!
=null)
{q=p->
link;
r=p;
while(
(1)____________)
{if(q->
link->
data<
r->
data)r=q;
q=q->
}
if(
(2)___________){s=r->
r->
link=s->
s->
link=((3)_________);
((4)_________);
}
((5)________);
}
p=head;
head=head->
free(p);
return(head);
}
6.下面的排序算法的思想是:
第一趟比较将最小的元素放在r[1]中,最大的元素放在r[n]中,第二趟比较将次小的放在r[2]中,将次大的放在r[n-1]中,…,依次下去,直到待排序列为递增序。
(注:
-->
)代表两个变量的数据交换)。
voidsort(SqList&
r,intn){
i=1;
while(
(1)______){
min=max=1;
for(j=i+1;
(2)________;
++j)
{if((3)________)min=j;
elseif(r[j].key>
r[max].key)max=j;
}
if((4)_________)r[min]<
---->
r[j];
if(max!
=n-i+1){if((5)_______)r[min]<
r[n-i+1];
else((6)______);
i++;
}//sort
7.下列算法为奇偶交换排序,思路如下:
第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>
a[i+1],将二者交换;
以后重复上述二趟过程,直至整个数组有序。
voidoesort(inta[n])
{intflag,i,t;
do{flag=0;
for(i=1;
i<
n;
i++,i++)
if(a[i]>
a[i+1])
{flag=
(1)______;
t=a[i+1];
a[i+1]=a[i];
(2)________;
for(3)________
if(a[i]>
{flag=(4)________;
t=a[i+1];
a[i]=t;
}while(5)_________;
}
第九章排序
1.
(1)DC
(2)ADF(3)B(4)ACFBDE
2.D
3.A
4.C
5.C
6.C
7.D
8.A
9.C
10.D
11.C
12.C
1.稳定、不稳定
2.内部、外部
3.免去查找过程中每一步都要检测整个表是否查找完毕,提高了查找效率。
4.n(n-1)/2
5.题中为操作方便,先增加头结点(最后删除),p指向无序区的前一记录,r指向最小值结点的前驱,一趟排序结束,无序区第一个记录与r所指结点的后继交换指针。
(1)q->
=NULL
(2)r!
=p(3)p->
link(4)p->
link=s(5)p=p->
link
6..
(1)i<
n-i+1
(2)j<
=n-i+1(3)r[j].key<
r[min].key(4)min!
=i(5)max==i(6)r[max]<
r[n-i+1]
7.
(1)1
(2)a[i]=t(3)(i=2;
=n;
i+=2)(4)1(5)flag