- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第10章排序作业
作业一:
对人意的7个关键字进行排序,至少要进行_______次关键字之间的两两比较。
A. 13 B.11 C.15 D.16 E.19
【参考答案】C
【解题思路】任何一个借助“比较”进行排序的算法,在最坏的情况下所需进行得比较次数至少为[]。[]=15。
排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为_________。
A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序
【参考答案】C
【解题思路】插入排序的思想是:每一趟将一个待排序的记录,按其关键字的大小插入到已经排序的序列中的适当位置。直到全部的记录插入完成为止。
对记录的关键字为{50,26,38,80,70,90,8,30,40,20}进行排序,各趟排序结束时的结果为:
50 26 38 80 70 90 8 30 40 20
50 8 30 40 20 90 26 38 80 70
26 8 30 40 20 80 50 38 90 70
8 20 26 30 38 40 50 70 80 90
其使用的排序方法是_________。
A. 快速排序 B. 希尔排序 C.基数排序 D.归并排序
【参考答案】B
【解题思路】由排序的结果直接可以确知(即使不知道其他几中排序方法)该排序是增量序列为5,3,1的希尔排序。
已知序列{70,83,100,65,10,32,7,9},请给出采用插入排序法对该序列作升序排序时的每一趟的结果。
【参考答案】采用插入排序方法排序的各趟的结果如下:
初始:(70),83,100,65,10,32,7,9
第一趟:(70,83), 100,65,10,32,7,9
第二趟:(70,83,100),65,10,32,7,9
第三趟:(65,70,83,100),10,32,7,9
第四趟:(10,65,70,83,100),32,7,9
第五趟:(10,32,65,70,83,100),7,9
第六趟:(7,10,32,65,70, 83,100),9
第七趟:(7,9,10,32,65,70,83,100)
作业二:
快速排序方法在_____情况下最不利于发挥其长处。
A. 要排序的数据量太大 B.要排序的数据中含有多个相同值
C.要排序的数据已基本有序 D.要排序的数据个数为奇数
【参考答案】C
【解题思路】要排序的数据(个数为n)已基本有序,采用快速排序则需要n-1趟,其时间复杂度升至O(n2)。
用快速排序方法对线性表(24,84,20,47,15,26,68,35,19)进行排序时,写出元素序列的变化情况:
【参考答案】
(1)24,84,20,47,15,26,68,35,19
(2)19,15, 20,24, 47, 26,68, 35 , 84
(3)15, 19, 20,24, 35 , 26,47, 68, 84
(4)15, 19, 20,24, 26, 35 , 47, 68, 84
【解题思路】每一次将一个子序列以第一个元素为基准分为两段。
作业三:
采用简单选择排序,比较的次数与移动次数分别是________.
A.B. C. D.
【参考答案】C
【解题思路】简单选择排序过程是:每趟从n-i+1个记录中选取关键字最小的记录(每趟比较的时间复杂度为O(n)),并和第i个记录交换(每趟移动的时间复杂度为O(1)),因此,总的比较次数与移动次数分别是。
对n个元素的序列进行排序时,堆排序所需要的附加存储空间是_______.
A.B. C. D.
【参考答案】B
【解题思路】堆排序本质上是就地排序。
已知序列{503,87,512,61,908,170,897,275,653,462},给出采用堆排序法对该序列做降序排序时的每一趟的结果。
【参考答案】
排序结果为908,897,653,512,503, 462,275,170,87,61。
作业四:
一组纪录的排序码为{25,48,16,35,79,82,23,40,36,72},其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为_______.
A.16 25 35 48 23 40 79 82 36 72 B.16 25 35 48 79 82 23 36 40 72
C.16 23 48 35 79 82 23 36 40 72 D.16 25 35 48 79 23 36 40 72 82
【参考答案】A
【解题思路】一趟归并过程如下:
就排序的算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是_______。
A. 堆排序快速排序归并排序
B. 堆排序归并排序快速排序
C
文档评论(0)