数据结构习题排序技术
16页1、第 8 章 排序技术课后习题讲解1. 填空题 排序的主要目的是为了以后对已排序的数据元素进行( )。【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。 对n个元素进行起泡排序,在( )情况下比较的次数最少,其比较次数为( )。在( )情况下比较次数最多,其比较次数为( )。【解答】正序,n-1,反序,n(n-1)/2 对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序,当把第7个记录60插入到有序表时,为寻找插入位置需比较( )次。【解答】3【分析】当把第7个记录60插入到有序表时,该有序表中有2个记录大于60。 对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行快速排序,在递归调用中使用的栈所能达到的最大深度为( )。【解答】3 对n个待排序记录序列进行快速排序,所需要的最好时间是( ),最坏时间是( )。【解答】O(nlog2n),O(n2) 利用简单选择排序对n个记录进行排序,最坏情况下,记录交换的次数为( )。【解答】n-1 如果要将序列(50,16,23,68,94,70,73
2、)建成堆,只需把16与( )交换。【解答】50 对于键值序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆,必须从键值为( )的结点开始。【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。2. 选择题 下述排序方法中,比较次数与待排序记录的初始状态无关的是( )。 A插入排序和快速排序 B归并排序和快速排序C选择排序和归并排序 D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2),归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。 下列序列中,( )是执行第一趟快速排序的结果。A da,ax,eb,de,bb ff ha,gc B cd,eb,ax,da ff ha,gc,bbC gc,ax,eb,cd,bb ff da,ha D ax,bb,cd,da ff eb,gc,ha【解答】A【分析】此题需要按字典序比较,前半区间中的所有元素都应小于ff,后半区间中的所有元素都应大于ff。 对初始状态为递增有序的序列进行排序,最省时间的是( ),最费时间的是( )。已知待排序序列中每
3、个元素距其最终位置不远,则采用( )方法最节省时间。A 堆排序 B插入排序 C快速排序 D 直接选择排序【解答】B,C,B【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。 堆的形状是一棵( )。A二叉排序树 B满二叉树 C完全二叉树 D 判定树【解答】C【分析】从逻辑结构的角度来看,堆实际上是一种完全二叉树的结构。 当待排序序列基本有序或个数较小的情况下,最佳的内部排序方法是( ),就平均时间而言,( )最佳。A 直接插入排序 B 起泡排序 C简单选择排序 D快速排序 【解答】A,D 设有5000个元素,希望用最快的速度挑选出前10个最大的,采用( )方法最好。A快速排序 B堆排序 C希尔排序 D 归并排序 【解答】B【分析】堆排序不必将整个序列排序即可确定前若干个最大(或最小)元素。 设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按升序排列,则( )是起泡排序一趟扫描的结果,( )是增量为4的希尔排序一趟扫描的结果,( )二路归并排序一趟扫描的结果,( )是以第一个元素为轴值的快速排序一趟扫描的结果,( )是堆排序初始建堆的结果。A(F,H,
4、C,D,P,A,M,Q,R,S,Y,X) B(P,A,C,S,Q,D,F,X,R,H,M,Y) C(A,D,C,R,F,Q,M,S,Y,P,H,X) D(H,C,Q,P,A,M,S,R,D,F,X,Y) E(H,Q,C,Y,A,P,M,S,D,R,F,X)【解答】D,B,E,A,C【分析】此题需要按字典序比较,并且需要掌握各种排序方法的执行过程。 排序的方法有很多种,( )法从未排序序列中依次取出元素,与已排序序列中的元素作比较,将其放入已排序序列的正确位置上。( )法从未排序序列中挑选元素,并将其依次放入已排序序列的一端。交换排序是对序列中元素进行一系列比较,当被比较的两元素为逆序时,进行交换;( )和( )是基于这类方法的两种排序方法,而( )是比( )效率更高的方法;( )法是基于选择排序的一种方法,是完全二叉树结构的一个重要应用。A 选择排序 B 快速排序 C 插入排序 D 起泡排序 E 归并排序 F 堆排序 【解答】C,A,D,B,B,D,F 快速排序在( )情况下最不利于发挥其长处。A 待排序的数据量太大 B 待排序的数据中含有多个相同值C 待排序的数据已基本有序 D 待排
《数据结构习题排序技术》由会员pu****.1分享,可在线阅读,更多相关《数据结构习题排序技术》请在金锄头文库上搜索。
婚礼新娘父亲致辞
更换SIME高速轴刹车片新
加油站作业许可管理规定
公务员管理处副处长竞选汇报
武汉鹿迪鞋业商贸城可行性研究36DOC
好用的工作实习报告集锦五篇
2022年03月2022浙江绍兴市越城区残联公开招聘编外人员1人强化练习卷(附答案解析)
物业公司工作总结(四篇).doc
(实用模板)公司员工年终工作总结范文
九年级中考适应性考试数学试题
2022年软考-网络管理员考前拔高综合测试题(含答案带详解)第136期
公司办公室年终工作总结(4篇).doc
工作质量责任制考核办法
以高考百日誓师大会为演讲稿全新模板 3篇
钢筋工试题库
CT常见部位扫描
内蒙古省包头五中九年级化学第一学期期中试题试卷人教版
初三班主任第二学期工作计划范文(2篇).doc
xx年小学五年级数学竞赛试题(数学)
某山区一级公路设计毕业设计计算书
2022-12-31 2页
2023-11-24 18页
2023-08-28 5页
2022-08-27 15页
2023-10-25 7页
2022-10-11 2页
2023-06-01 8页
2023-03-22 122页
2023-06-29 8页
2023-10-20 7页