排序技术样本.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, 则将二者交换, 然后重复上述排序过程, 直至整个数组有序。编写算法实现上述奇偶交换排序。【解答】具体算法如下: