数据结构—排序

《数据结构—排序》由会员分享，可在线阅读，更多相关《数据结构—排序（11页珍藏版）》请在金锄头文库上搜索。

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【分析】选择排序在最好、最坏、平均情况下的时间性能均为0（n 2），归并排序在最好、最 坏、平均情况下的时间性能均为 O（nlog2n）。 下列序列中，（ ）是执行第一趟快速排序的结果。A da，ax，eb，de ，bb ff ha，gc B cd，eb，ax，da ff ha，gc，bbC gc，

4、ax，eb， cd，bb ff da，ha D ax，bb，cd，da ff eb，gc，ha【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff,后半区间中的所有元 素都应大于ffo 对初始状态为递增有序的序列进行排序，最省时间的是（ ），最费时间的是（ ）。已 知待排序序列中每个元素距其最终位置不远，则采用（ ）方法最节省时间。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）中的关键码按升序排列，则（） 是起泡排序一趟扫描的结果，（ ）是增量为4 的希尔排

6、序一趟扫描的结果，（ ）二路归并 排序一趟扫描的结果，（ ）是以第一个元素为轴值的快速排序一趟扫描的结果，（ ）是堆 排序初始建堆的结果。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，QPA，MSRDF，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 快速排序在( )情况下最不利于发挥其长处。A 待排序的数据量太大 B 待排序的数据中含有多个相同值C 待排序的数据已基本有序 D 待排序的数据数量为奇数【解答】 C【分析】快

8、速排序等改进的排序方法均适用于待排序数据量较大的情况,各种排序方法对待 排序的数据中是否含有多个相同值,待排序的数据数量为奇数或偶数都没有影响。 ( )方法是从未排序序列中挑选元素,并将其放入已排序序列的一端。A 归并排序 B 插入排序 C 快速排序 D 选择排序【解答】 D3. 判断题 如果某种排序算法是不稳定的,则该排序方法没有实际应用价值。【解答】错。一种排序算法适合于某种特定的数据环境,有时对排序的稳定性没有要求。 当待排序的元素很大时,为了交换元素的位置,移动元素要占用较多的时间,这是影响 时间复杂性的主要因素。【解答】对。此时着重考虑元素的移动次数。 对n个记录的集合进行快速排序，

9、所需要的附加空间是0(n)。【解答】错。最坏情况下是0(n)。 堆排序所需的时间与待排序的记录个数无关。【解答】错。堆排序最好、最坏及平均时间均为0(nlog2n),是待排序的记录个数n的函数。 一般来说,待排序的记录个数越多,排序所消耗的时间也就越多。 设有键值序列(k1, k2,kn),当in/2时，任何一个子序列(ki, ki+1,., kn) 定 是堆。【解答】对。当in/2时，ki, ki+1,. , kn均是叶子结点，所以一定是堆。4已知数据序列为(12, 5, 9, 20, 6, 31, 24),对该数据序列进行排序,写出插入排序 起泡排序、快速排序、简单选择排序、堆排序以及二路

10、归并排序每趟的结果。【解答】用上述排序方法的每趟结果如下：插入扫E序:简单选择扫E序:-1初贻键值序列1259 20 6 31加初贻薩值序列1?5g-2063124;第一趟结果5129 20 8 3124 ! i第一趟结果3E12g20831-.24；第二趟结果5912却 63124 :第二螢结果、工：?2012；31聃；第三趟结果5912206 3124 ；:第三趙结果磴SgE20123124 j；第四趟结果巨 & g12 .20 ；3124 第四逍结果茂.8912E203124;:第五趟结果56912 20 3124 :第五趟结果5S9122031M：第寮趟结果56912 20 ：2431

11、：第六趟结果589122024!:堆挂序;初始键值序列12；g206：3124 1二路归并扫E序:初始裡佰序列12j第一趙结果:初贻逹堆结果31202456912 |；第一趙结果E24201256931 1:第二趟结果E20g12.5的2431：第二趟结果1.5-:第三趟结杲1296.5 202431 :第三趟结果5:第四趟箱果再56J12加24；31 :第五趟结臬5Jg12；20弗31 :第為趟结果6g12202431：9 206 312412 9 20 E6 .31 E249 1 工丽& 24 31691-2 ：20 24 31:初贻键值序列13 59 20631241；初始键值序列125

12、.g2063124 :第一趟结果L6 r? n20；3124:第一趟结果 5g1262024中i:第二趟结果刃6门1220E3124 1第二趟结果 59刃12：202431 :第三趟结果5 691220加31 !第三趟结果 56g12202431 :；第四趟结果5 6g 12202431:第四趟结杲56g12.202431 :n快速扫e序:；丨起泡挂序:I15. 对n=7,给出快速排序一个最好情况和最坏情况的初始排列的实例。【解答】最好情况：4， 7， 5， 6， 3， 1， 2最坏情况：7， 6， 5， 4， 3， 2， 16. 判别下列序列是否为堆，如不是，按照堆排序思想把它调整为堆，用图

13、表示建堆的过程（1）（1, 5，7，25，21，8，8, 42）（3, 9， 5， 8, 4， 17， 21， 6）【解答】序列是堆，序列不是堆，调整为堆（假设为大根堆）的过程如图8-5所示。图&堆调整的过程7. 已知下列各种初始状态(长度为n)的元素，试问当利用直接插入排序进行排序时，至 少需要进行多少次比较(要求排序后的记录由小到大顺序排列)？ 关键码从小到大有序(keylv key2v . v keyn)。 关键码从大到小有序(key1 key2 keyn)。奇数关键码顺序有序，偶数关键码顺序有序(keylv key3v., key2 key4.)。br / 前半部分元素按关键码顺序有序，后半部分元素按关键码顺序有序，即：(key1v key2v . v keym， keym+1v keym+2v .【解答】依题意，最好情况下的比较次数即为最少比较次数。 插入第i(2in)个元素的比较次数为1,因此总的比较次数为：1+1+.+1=n-1 插入第i (2in)个元素的比较次数为i,因此总的比较次数为：