第8章+排序习题解析(答).doc

排序习题解析11. 填空题⑴ 排序的主要目的是为了以后对已排序的数据元素进行（查找）⑵ 对n个元素进行起泡排序，在（正序）情况下比较的次数最少，其比较次数为（n-1 ）在（反序）情况下比较次数最多，其比较次数为（n(n-1)/2）⑶ 对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（ 3）次⑷ 对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（ 3）⑸ 对n个待排序记录序列进行快速排序，所需要的最好时间是（O(nlog2n) ），最坏时间是（ O(n2)）⑹ 利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（ n-1）2. 选择题⑴ 下述排序方法中，比较次数与待排序记录的初始状态无关的是（ ）A、插入排序和快速排序 B、归并排序和快速排序C、选择排序和归并排序 D、插入排序和归并排序⑵ 下列序列中，（ ）是执行第一趟快速排序的结果A 、[da，ax，eb，de，bb] ff [ha，gc] B 、[cd，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]⑶ 对初始状态为递增有序的序列进行排序，最省时间的是（B），最费时间的是（C）。

已知待排序序列中每个元素距其最终位置不远，则采用（B ）方法最节省时间A、堆排序 B、插入排序 C、快速排序 D、 直接选择排序⑸ 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（A），就平均时间而言，（D）最佳A 直接插入排序 B 起泡排序 C简单选择排序 D快速排序⑼ 快速排序在（ ）情况下最不利于发挥其长处A、 待排序的数据量太大 B、 待排序的数据中含有多个相同值C、 待排序的数据已基本有序 D、 待排序的数据数量为奇数⑽ （ ）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端A、 归并排序 B、 插入排序 C、 快速排序 D、 选择排序3. 判断题⑴ 如果某种排序算法是不稳定的，则该排序方法没有实际应用价值错⑵ 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素对⑶ 对n个记录的集合进行快速排序，所需要的附加空间是Ο(n)错排序----习题解析2一、选择题1、以下序列不是堆的是 D A、（100，85，98，77，80，60，82，40，20，10，66）B、（100，98，85，82，80，77，66，60，40，20，10）C、（10，20，40，60，66，77，80，82，85，98，100）D、（100，85，40，77，80，60，66，98，82，10，20）2、在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是 A 。

A、直接插入排序 B、冒泡排序 C、简单选择排序 D、归并排序3、在下列算法中， C 算法可能出现下列情况；在最后一趟开始之前，所有的元素都不在其最终的位置上 A、堆排序 B、冒泡排序 C、插入排序D、快速排序4、从未排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为 A 排序法 A、插入 B、选择 C、希尔 D、二路归并5、排序趟数与序列原始状态有关的排序方法是 D或C 排序法 A、插入 B、选择 C、冒泡 D、快速6、下面给出的四种排序方法中， D 排序是不稳定排序法 A、插入 B、冒泡 C、二路归并 D、堆7、快速排序在最坏情况下时间复杂度是O（n2），比 A 的性能差 A、堆排序 B、起泡排序 C、选择排序8、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 C A、快速排序 B、堆排序 C、归并[排序 D、直接插入排序9、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 A A、堆排序<快速排序<归并排序 B、堆排序<归并排序<快速排序C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序E、以上答案都不对10、下面排序方法中，关键字比较次数与记录的初始排列无关的是 D 。

A、希尔排序 B、冒泡排序 C、直接插入排序 D、直接选择排序11、对记录的关键字集合key={50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为： 50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 其使用的排序方法是 C A、快速排序 B、基数排序 C、希尔排序 D、归并排序12、一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为 B A、80，45，50，40，42，85 B、85，80，55，40，42，45C、85，80，55，45，42，40 D、85，55，80，42，45，40 13、在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为 D A、O(1) B、O(nlog2n) C、O(n2) D、O(n) 14、在对n个元素进行快速排序的过程中，第一次划分最多需要移动 D 次元素（包括开始将基准元素移动到临时变量的那一次）。

A、n/2 B、n-1 C、n D、n+1 15、下述几种排序方法中，要求内存量最大的是 D A、插入排序 B、选择排序 C、快速排序 D、归并排序 16、下面排序方法中，时间复杂性不是O(n2)的是 B A、直接插入排序 B、二路归并排序 C、冒泡排序 D、直接选择排序二、判断题 1、快速排序的速度在所有排序方法中为最快，而且所需附加空间最少错 ） 2、内排序的快速排序方法，在任何情况下均可得到最快的排序结果 错 ） 3、基数排序的设计思想是按照对关键字值的比较来实施的错 ） 4、在快速排序算法中，不可以用队列替代栈 错 ） 5、用希尔方法排序时，若关键字饿初始排序杂乱无序，则排序效率较低 错 ） 6、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响复杂度的主要因素 对 ） 7、对于n个记录的集合进行归并排序，在最坏情况下所需要的时间是O(n2)错 ） 8、对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O(n2) 对 ） 9、使用置换选择排序的主要目的是为了增加初始归并段的长度 对 ） 10、对一个堆，按二叉树层次进行遍历可以得到一个有序序列。

错 ）11、有一小根堆，堆中任意结点的关键字均小于它的左、右孩子关键字其具有最大值的结点一定是一个叶结点并可能在堆的最后两层中 对 ）。