作业7解答.doc

排序 作业7 一、单项选择题 1．堆排序的时间复杂度是（　　　）。（东部名校经典试题） A）O(1) B）O(n) C）O(n2) D）O(nlogn) 【分析】堆排序是一种高级排序，其时间复杂度应为O(nlogn)。 【答案：D】 2．在下述排序算法中，所需辅助存储量最多的是（　　　）。（北方名校经典试题） A）快速排序 B）归并排序 C）堆排序 D）链式基数排序 【分析】在各中排序方法中，归并排序需和待排记录等数量的辅助空间，需要的空间辅助空间最大。 【答案：B】 3．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（　　　）。 A）冒泡排序 B）简单选择排序C）希尔排序 D）直接插入排序 【分析】所有选择排序都是不稳定的排序方法，对于简单选择排序每一趟都能选出一个元素放在其最终位置上，所以本题应选择B。 【答案：B】 4．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（　　　）。（北方名校经典试题） A）直接插入排序 B）起泡排序 C）简单选择排序D）基数排序 【分析】对直接插入排序而言，算法时间复杂度为O(n2)，但若待排记录序列为“正序”时，其时间复杂度可提高至O(n)。若待排记录序列按关键字“基本有序”，直接插入排序的效率就可大大提高，此外由于直接插入排序算法简单，在n值很小时效率也高。 【答案：A】 5．快速排序执行一遍之后，已经到位的元素个数是（　　　）。 A）1 B）3 C） D） 【分析】快速排序的基本思想是任选取序列中的一记录（通常可选第一个记录），以它的关键字和待排序序列的所有剩余记录的关键字进行比较，将所有关键字较它小的记录都排在它前面，将所有关键字较它大的记录都排在它之后，经过一趟排序后，由此可知快速排序执行一遍之后，已经到位的元素个数是1。 【答案：A】 6．数据表中有10000个元素，如果仅需求出其中最大的10个元素，则采用（　　　）排序算法最节省时间。 A）快速排序 B）希尔排序 C）堆排序 D）直接选择排序 【分析】本题中堆排序与直接选择排序每一趟都可选择出一个当前元素中的最大者，显然采用堆排序最节省时间。 【答案：C】 二、综合题 1．判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则将它调整为堆。（东部名校经典试题） 【解答】初始序列对应的完全二叉树如图8-1所示： 初始序列不是堆，调整为小顶堆如图8-2所示： 图8-1　初始序列对应的完全二叉树　　　　　　　　　图8-2　调整为小顶堆 调整后得到小顶堆为：（12，24，33，65，33，56，48，92，86，70） 2．给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。（东部名校经典试题） （1）希尔排序（第一趟排序的增量为6） （2）快速排序（选第一个记录为枢轴） 【解答】 （1）（12,2,10,20,6,18,4,16,30,8,28） （2）（6,2,10,4,8,12,28,30,20,16,18） 【例12】请回答下列关于推的一些问题：（北方名校经典试题） （1）堆的存储表示是顺序的，还是链接的？ （2）设有一个小根堆，则具有最大值的元素可能在什么地方？ 【解答】 （1）因为堆所对应的二叉树为完全二叉树，完全二叉树一般采用顺序存储，所以堆的存储表示用顺序的。 （2）小根堆的最小值元素必在堆顶，只有叶子结点可能是最大值元素。 3．利用比较的方法进行排序，在最坏情况下，能达到的最好的时间复杂度是什么？（东部名校经典试题） 【解答】由于含n个记录的序列可能出现的初始状态有n！个，则描述n个记录排序过程的判定树必须有n!个叶子结点。由于若二叉树的高度为h，则叶子结点的个数不超过2h-1；反之，若有m个叶于结点，则二叉树的高度至少为。所以 n个记录排序的判定树上必定存在一条长度至少为的路径。可知任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为。根据斯特林公式有=O(nlogn)。 4．有一种简单的排序算法，叫做计数排序（Count Sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为C，那么，这个记录在新的有序表中的合适的存放位置即为C。（北方名校经典试题） （1）给出适用于计数排序的数据表定义。 （2）编写实现计数排序的算法。 注：此题选做。 【解答】 （1）C