排序技术新版.doc

第 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）建成堆，只需把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。 对初始状态为递增有序的序列进行排序，最省时间的是（ ），最费时间的是（ ）。已知待排序序列中每个元素距其最终位置不远，则采用（ ）方法最节省时间。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，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 待排序的数据数量为奇数【解答】C【分析】快速排序等改善的排序方法均合用于待排序数据量较大的情况，各种排序方法对待排序的数据中是否具有多个相同值，待排序的数据数量为奇数或偶数都没有影响。 （ ）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端。A 归并排序 B 插入排序 C 快速排序 D 选择排序【解答】D3. 判断题 假如某种排序算法是不稳定的，则该排序方法没有实际应用价值。【解答】错。一种排序算法适合于某种特定的数据环境，有时对排序的稳定性没有规定。 当待排序的元素很大时，为了互换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的重要因素。【解答】对。此时着重考虑元素的移动次数。 对n个记录的集合进行快速排序，所需要的附加空间是(n)。【解答】错。最坏情况下是(n)。 堆排序所需的时间与待排序的记录个数无关。【解答】错。堆排序最佳、最坏及平均时间均为(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)，对该数据序列进行排序，写出插入排序、起泡排序、快速排序、简朴选择排序、堆排序以及二路归并排序每趟的结果。【解答】用上述排序方法的每趟结果如下：5对n=7，给出快速排序一个最佳情况和最坏情况的初始排列的实例。【解答】最佳情况：4，7，5，6，3，1，2最坏情况：7，6，5，4，3，2，16判别下列序列是否为堆，如不是，按照堆排序思想把它调整为堆，用图表达建堆的过程。（1，5，7，25，21，8，8，42）（3，9，5，8，4，17，21，6）【解答】序列是堆，序列不是堆，调整为堆（假设为大根堆）的过程如图8-5所示。7已知下列各种初始状态（长度为n）的元素，试问当运用直接插入排序进行排序时，至少需要进行多少次比较（规定排序后的记录由小到大顺序排列）？ 关键码从小到大有序（key1 key2 key2 keyn）。 奇数关键码顺序有序，偶数关键码顺序有序（key1 key3 前半部分元素按关键码顺序有序，后半部分元素按关键码顺序有序，即：（key1 key2 keym，keym+1 keym+2Ai+1，则将两者互换，然后反复上述排序过程，直至整个数组有序。编写算法实现上述奇偶互换排序。【解答】具体算法如下：