习题七 参考答案一、选择题1．内部排序算法的稳定性是指( D )A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为 0（n log n）的排序方法D．以上都不对2．下面给出的四种排序算法中，( B )是不稳定的排序A．插入排序 B．堆排序 C．二路归并排序 D．冒泡排序3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（ D ） A．直接插入排序 B．冒泡排序 C．快速排序 D．直接选择排序4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果A．选择排序 B.冒泡排序 C.插入排序 D.堆排序5．下列排序方法中，( D )所需的辅助空间最大A．选择排序 B．希尔排序 C．快速排序 D．归并排序6．一组记录的关键字为（46，79，56，38，40，84） ，则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（ C ） A．(38,40,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)7．在对一组关键字序列{70， 55，100，15，33，65，50 ，40，95} ，进行直接插入排序时，把 65 插入，需要比较( A )次。
A. 2 B. 4 C. 6 D. 88.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序9．当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序10．在待排序序列局部有序时，效率最高的排序算法是( B )A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序二、填空题1. 执行排序操作时，根据使用的存储器可将排序算法分为 内排序 和 外排序 2. 在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第 7 个记录 60 插入到有序表中时，为寻找插入位置需比较 3 次3. 在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用 直接插入排序 4. 在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第 4 次交换和选择后，未排序记录为 {50,70,60,95,80}。
5. n 个记录的冒泡排序算法所需的最大移动次数为 3n(n-1)/2 ，最小移动次数为 0 6. 对 n 个结点进行快速排序，最大的比较次数是 n(n-1)/2 7. 对于堆排序和快速排序，若待排序记录基本有序，则选用 堆排序 8. 在归并排序中，若待排序记录的个数为 20，则共需要进行 5 趟归并9. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是 关键字的比较 和 数据元素的移动 10． 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是 快速排序 ，需要内存容量最多的是 基数排序 三、算法设计题1． 试设计算法，用插入排序方法对单链表进行排序参考答案:public static void insertSort(LinkList L) { Node p, q, r, u;p = L.getHead().getNext();L.getHead().setNext(null); //置空表，然后将原链表结点逐个插入到有序表中while (p != null) { //当链表尚未到尾，p 为工作指针r = L.getHead();q = L.getHead().getNext();while (q != null && (Integer.parseInt((String) q.getData())) 0) {int table[] = new int[n];for (int i = 0; i 0) {for (int i = 0; i = left; i--) {if (table[i] 1) {//此时不排 i 的原因是 i 位置上的元素已经确定了，i 前面的都是比 i 小的，i 后面的都是比 i 大的stack[1][top] = i - 1;stack[0][top] = low;top++;}//当 high-i 小于等于 1 的时候，就不往栈中放了，这就是外层 while 循环能结束的原因//如果从 i 到高位之间的元素个数多于一个，那么需要再次排序if (high - i > 1) {//此时不排 i 的原因是 i 位置上的元素已经确定了，i 前面的都是比 i 小的，i 后面的都是比 i 大的stack[1][top] = high; stack[0][top] = i + 1;top++;}}}5． 试设计算法，判断完全二叉树是否为大顶堆。
参考答案:boolean checkmax(BiTreeNode t) //判断完全二叉树是否为大顶堆{BiTreeNode p = t;if (p.getLchild() == null && p.getRchild() == null) {return true;} else {if (p.getLchild() != null && p.getRchild() != null) {if ((((RecordNode) p.getLchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0 && (((RecordNode) p.getRchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0) { return checkmax(p.getLchild()) && checkmax(p.getRchild());} else {return false;}} else if (p.getLchild() != null && p.getRchild() == null) {if ((((RecordNode) p.getLchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0) {return checkmax(p.getLchild()); } else {return false;}} else if (p.getLchild() == null && p.getRchild() != null) {if ((((RecordNode) p.getRchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0) {return checkmax(p.getRchild());} else {return false;}} else {return false;}}}。