资源描述：
《排序技术第课后习题讲解.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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、,该有序表中有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)建成堆,只需把16与()交换。【解答】50⑻对于键值序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆,必须从键值为
3、()的结点开始。【解答】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[
4、ha,gc,bb]C[gc,ax,eb,cd,bb]ff[da,ha]D[ax,bb,cd,da]ff[eb,gc,ha]【解答】A【分析】此题需要按字典序比较,前半区间中的所有元素都应小于ff,后半区间中的所有元素都应大于ff。⑶对初始状态为递增有序的序列进行排序,最省时间的是(),最费时间的是()。已知待排序序列中每个元素距其最终位置不远,则采用()方法最节省时间。A堆排序B插入排序C快速排序D直接选择排序【解答】B,C,B【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。⑷堆的形状是一棵()。A二叉排序树B满二叉树C完全二叉树D判定树【解答】C【
5、分析】从逻辑结构的角度来看,堆实际上是一种完全二叉树的结构。⑸当待排序序列基本有序或个数较小的情况下,最佳的内部排序方法是(),就平均时间而言,()最佳。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)中的关键码
6、按升序排入已排序序列的一端。交换排序是对列,则()是起泡排序一趟扫描的序列中元素进行一系列比较,当被比结果,()是增量为4的希尔排序一较的两元素为逆序时,进行交换;()趟扫描的结果,()二路归并排序一和()是基于这类方法的两种排序趟扫描的结果,()是以第一个元素方法,而()是比()效率更高的为轴值的快速排序一趟扫描的结果,方法;()法是基于选择排序的一种()是堆排序初始建堆的结果。方法,是完全二叉树结构的一个重要A(F,H,C,D,P,A,M,Q,R,S,Y,应用。X)A选择排序B快速排序C插入排序B(P,A,C,S,Q,D,F,X,R,H,M,D起泡排序E归并排序F堆
7、排序Y)【解答】C,A,D,B,B,D,FC(A,D,C,R,F,Q,M,S,Y,P,H,⑼快速排序在()情况下最不利于X)D(H,C,Q,P,A,M,S,R,D,F,X,发挥其长处。A待排序的数据量太大B待排序的Y)数据中含有多个相同值E(H,Q,C,Y,A,P,M,S,D,R,F,C待排序的数据已基本有序D待排X)【解答】D,B,E,A,C序的数据数量为奇数【解答】C【分析】此题需要按字典序比较,而且需要掌握各种排序方法的执行过【分析】快速排序等改进的排序方法均适用于待排序数据量较大的情况,程。各种排序方法对待排序的数据中是否⑻排序的
