数据结构—排序.doc

《数据结构—排序.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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，

3、100），用筛选法建堆，必须从键值为（）的结点开始。【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。2.选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。⑵下列序列中，（）是执行第一趟快速排序的结果。A[da，ax，eb，de，bb]ff[ha，gc]B[cd，

4、eb，ax，da]ff[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【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。⑷堆

5、的形状是一棵（）。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

6、，R，D，F，X）中的关键码按升序排列，则（）是起泡排序一趟扫描的结果，（）是增量为4的希尔排序一趟扫描的结果，（）二路归并排序一趟扫描的结果，（）是以第一个元素为轴值的快速排序一趟扫描的结果，（）是堆排序初始建堆的结果。A（F，H，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【分析】此题需要按

7、字典序比较，并且需要掌握各种排序方法的执行过程。⑻排序的方法有很多种，（）法从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端。交换排序是对序列中元素进行一系列比较，当被比较的两元素为逆序时，进行交换；（）和（）是基于这类方法的两种排序方法，而（）是比（）效率更高的方法；（）法是基于选择排序的一种方法，是完全二叉树结构的一个重要应用。A选择排序B快速排序C插入排序D起泡排序E归并排序F堆排序【解答】C，A，D，B，B，D，F

8、⑼快速排序在（）情况下最不利于发挥其长处。A待排序的数据量太大B待排序的数据中含有多个相同值C待排序的数据已基本有序D待排序的数据数量为奇数【解答】C【分析】快速排序等改进的排序方法均适用于待排序数据量较大的情况，各种排序方法对待排序的数据中是否含有多个相同值，待排序的数据数量为奇数或偶数都没有影响。⑽（）方法是从未