第10篇排序练习题答案.doc

  1. 1、本文档共6页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第10章排序练习题答案 一、填空题 1. 大多数排序算法都有两个基本的操作: 比较 和 移动 。 2. 在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置至少需比较 3 次。 3. 在插入和选择排序中,若初始数据基本正序,则选用 插入 ;若初始数据基本反序,则选用 选择 。 正序时两种方法移动次数均为0,但比较次数量级不同,插入法:n-1即O(n),选择法:O(n2) 反序时两种方法比较次数量级相同,均为O(n2),但移动次数不同,插入法:O(n2),选择法:3(n-1)即O(n) 4. 在堆排序和快速排序中,若初始记录接近正序或反序,则选用 堆排序 ;若初始记录基本无序,则最好选用 快速排序 。 5. 对于n个记录的集合进行冒泡排序,在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速排序,在最坏的情况下所需要的时间是 O(n2) 。 6. 对于n个记录的集合进行归并排序,所需要的平均时间是 O(nlog2n) ,所需要的附加空间是 O(n) 。 7. 对于n个记录的表进行2路归并排序,整个归并排序需进行 ┌log2n┐ 趟(遍)。 8. 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列,则: 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ; 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X; 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ; 堆排序初始建堆的结果是 Y S X R P C M H Q D F A 。(大根堆) 9. 在堆排序、快速排序和归并排序中, 若只从存储空间考虑,则应首先选取 堆排序 方法,其次选取 快速排序方法,最后选取归并排序方法; 若只从排序结果的稳定性考虑,则应 选取归并排序方法; 若只从平均情况下最快考虑,则应选取快速排序方法; 若只从最坏情况下最快并且要节省内存考虑,则应选取堆排序方法。 二、单项选择题 ( C )1. 排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为 A. 归并排序 B. 冒泡排序 C. 插入排序 D. 选择排序 ( D )2.从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)的一端的方法,称为 A. 冒泡排序 B. 归并排序 C. 插入排序 D. 选择排序 ( B )3.对n个不同的排序码进行冒泡排序,在下列哪种情况下比较的次数最多。 A. 从小到大排列好的 B. 从大到小排列好的 C. 元素无序 D. 元素基本有序 ( D )4.对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为 A. n+1 B. n C. n-1 D. n(n-1)/2 ( C )5.快速排序在下列哪种情况下最易发挥其长处。 A. 被排序的数据中含有多个相同排序码 B. 被排序的数据已基本有序 C. 被排序的数据完全无序 D. 被排序的数据中的最大值和最小值相差悬殊 ( B )6. 对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是 A.O(n) B.O(n2) C.O(nlog2n) D.O(n3) ( C )7.若一组记录的排序码为(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 ( D )8.下列关键字序列中, 是堆。 A. 16, 72, 31, 23, 94, 53 B. 94, 23, 31, 72, 16, 53 C. 16, 53, 23, 9

文档评论(0)

xiaofei2001128 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档