《数据结构》吕云翔编著第7章排序习题解答

1、第七章排序课后习题解答一、单项选择题1下列内部排序算法中： A快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序（1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（ ）（4）排序的平均时间复杂度为O(nlogn)的算法是（ ）为O(nn)的算法是（ ）【解答】（1） DC （2）ADF （3）B （4）ACF BDE 2比较次数与排序的初始状态无关的排序方法是( )。A直接插入排序 B起泡排序 C快速排序 D简单选择排序

2、【解答】D3对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入【解答】A4下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A. 选择 B. 冒泡 C. 归并 D. 堆【解答】C5一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A(38,4

3、0,46,56,79,84) B. (40,38,46,79,56,84)C(40,38,46,56,79,84) D. (40,38,46,84,56,79)【解答】C6下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A 冒泡 B. 希尔 C. 快速 D. 堆 【解答】C7. 就平均性能而言，目前最好的内排序方法是( )排序法。A. 冒泡 B. 希尔插入 C. 交换 D. 快速 【解答】 D8. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序【解答】 A9. 若用冒泡排序方法对序列10,14,26,29,41

4、,52从大到小排序，需进行 （ ）次比较。 A. 3 B. 10 C. 15 D. 25 【解答】 C10. 快速排序方法在（ ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序【解答】D11下列四个序列中，哪一个是堆（ ）。A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15【解答】C12. 有一组数据（15，9，7，8，20，-1，7，

5、4），用堆排序的筛选方法建立的初始堆为 （ ）A-1，4，8，9，20，7，15，7 B-1，7，15，7，4，8，20，9C-1，4，7，8，20，15，7，9 DA，B，C均不对。【解答】C二、填空题1.在索引顺序表中首先查找_，然后查找相应的_.其平均查找长度等于_。【解答】索引表，块，查找索引表的平均长度与检索相应块的平均查找长度的和2.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是_的，否则称为_的。【解答】稳定、不稳定3.按照排序过程涉及的存储设备的不同，排序可分为_排序和_排序。【解答】内部、外部4直接插入排序用监视哨的作

6、用是_。【解答】免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。5对n个记录的表r1.n进行简单选择排序，所需进行的关键字间的比较次数为_。【解答】n(n-1)/2三、算法设计题1.一个线性表中的元素为正整数或负整数。设计算法将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少比较次数。 【解答】本题的基本思想是：先设置好上、下界和轴值，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上下界相遇。算法如下voidexampoe(Elemtypean)i=1,j=n;/*i,j为左右边界*/while(ij)while(ij

7、)&(ai0)i+;/*在左边界找正数*/while(i0) j-;/*在右边界找负数*/if(ij)temp=ai;ai=aj;aj=aetmp; /*交换两个元素的值*/i+;j-;2.已知（k1,k2,，kn）是堆，写一个算法将（k1,k2,，kn，kn+1）调整为堆。【解答】3. 给定n个记录的有序序列An和m 个记录的有序序列Bm，将它们归并为一个有序序列，存放在Cm+n中，试写出这一算法。【解答】采用二路归并排序中一次归并的思想，设三个参数i、j和k分别指向两个待归并的有序序列和最终有序序列的当前记录，初始时i、j分别指向两个有序序列的第一个记录，即i=1，j=1，k指向存放归并结

8、果的位置，即k=1。然后，比较i和j所指记录的关键码，取出较小者作为归并结果存入k所指位置，直至两个有序序列之一的所有记录都取完，再将另一个有序序列的剩余记录顺序送到归并后的有序序列中。4.设待排序的记录序列用单链表作存储结构，试写出简单选择排序算法/单链表选择排序算法 public static void selectSort(LinkList L) /p为当前最小,r为此过程中最小,q为当前扫描接点 Node p, r, q; Node newNode = new Node(); newNode.setNext(L.getHead(); L.setHead(newNode); /制造一个最

9、前面的节点newNode，解决第一个节点的没有前续节点需要单独语句的问题。 p = L.getHead(); while (p.getNext().getNext() != null) r = p.getNext(); q = p.getNext().getNext(); while (q.getNext() != null) if (Integer.parseInt(String) q.getNext().getData() 0) int table = new intn; for (int i = 0; i 0) for (int i = 0; i = left; i-) if (tablei tablei - 1) int temp = tablei; tablei = tablei - 1; tablei - 1 = temp; t = i; left = t + 1; /反向部分 for (int i = l