第7章排序习题参考答案

1、习题七参考答案一、选择题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.插

2、入排序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. 2B. 4C.

3、 6D. 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插入到有序表

4、中时，为寻找插入位置需比较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. 若不考虑基数排序，则在排序过程中，

5、主要进行的两种基本操作是关键字的比较和数据元素的移动。10. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少 的是快速排序，需要内存容量最多的是基数排序 。三、算法设计题1 .试设计算法，用插入排序方法对单链表进行排序。参考答案：public static void in sertSort(L in kList L) Node p, q, r, u;p = L.getHead().getNext();L.getHead().setNext(null);/ 置空表，然后将原链表结点逐个插入到有序表中while (p != null) / 当链表尚未到尾，

6、 p 为工作指针r = L.getHead();q = L.getHead().getNext();while (q != null && (Integer.parseInt(String) q.getData() <=(Integer.parseInt(String) p.getData() /查P结点在链表中的插入位置，这时q是工作指针r = q;q = q.getNext();u = p.getNext();p.setNext(r.getNext();r.setNext(p);p = u;/将P结点链入链表中，r是q的前驱，u是下一个待插入结点的指针2 试设计算法，

7、用选择排序方法对单链表进行排序。参考答案 :/ 单链表选择排序算法public static void selectSort(LinkList L) /p 为当前最小 ,r 为此过程中最小 ,q 为当前扫描接点Node p, r, q;Node newNode = new Node();newNode.setNext(L.getHead();L.setHead(newNode);/制造一个最前面的节点newNode解决第一个节点的没有前续节点需要单独语句的问题。p = L.getHead();while (p.getNext().getNext() != null) r = p.getNext

8、();q = p.getNext().getNext();while (q.getNext() != null) if (Integer.parseInt(String) q.getNext().getData() <=(Integer.parseInt(String) r.getNext().getData() r = q;q = q.getNext();if (r != p) /交换 p 与 rNode swap = r.getNext();r.setNext(r.getNext().getNext(); /r的 next 指向其后继的后继swap.setNext(p.getNext

9、();p.setNext(swap); /p的后继为 swap p = p.getNext();/while p.setNext(null);3 试设计算法，实现双向冒泡排序 ( 即相邻两遍向相反方向冒泡 ) 。 参考答案 :/ 产生随机数方法public static int random(int n) if (n > 0) int table = new intn;for (int i = 0; i < n; i+) tablei = (int) (Math.random() * 100);/ 产生一个 0100 之间的随机数return table;return null;/

10、 输出数组元素方法 public static void print(int table) if (table.length > 0) for (int i = 0; i < table.length; i+) System.out.print(tablei + " ");System.out.println();/ 双向冒泡排序方法 public static void dbubblesort(int table) int high = table.length;int left = 1;int right = high - 1;int t = 0;do /

11、正向部分for (int i = right; i >= left; i-) if (tablei < tablei - 1) int temp = tablei; tablei = tablei - 1; tablei - 1 = temp; t = i;left = t + 1;/ 反向部分for (int i = left; i < right + 1; i+) if (tablei < tablei - 1) int temp = tablei; tablei = tablei - 1; tablei - 1 = temp; t = i;right = t -

12、1; while (left <= right);4 试设计算法，使用非递归方法实现快速排序。 参考答案 :public static void NonrecursiveQuickSort(int ary) if (ary.length < 2) return;/ 数组栈：记录着高位和低位的值int stack = new int2ary.length;/ 栈顶部位置int top = 0;/ 低位，高位，循环变量，基准点/ 将数组的高位和低位位置入栈 stack1top = ary.length - 1; stack0top = 0;top+;/ 要是栈顶不空，那么继续while

13、 (top != 0) /将高位和低位出栈/低位：排序开始的位置top-;int low = stack0top;/高位：排序结束的位置int high = stack1top; /将高位作为基准位置/基准位置int pivot = high;int i = low;for (int j = low; j < high; j+) if (aryj <= arypivot) int temp = aryj; aryj = aryi; aryi = temp; i+;/ 如果 i 不是基准位，那么基准位选的就不是最大值/而 i 的前面放的都是比基准位小的值，那么基准位/的值应该放到 i

14、 所在的位置上if (i != pivot) int temp = aryi; aryi = arypivot; arypivot = temp;if (i - low > 1) / 此时不排 i 的原因是 i 位置上的元素已经确定了， i 前面的都是比 i 小的， i 后面的都 是比 i 大的stack1top = i - 1;stack0top = low;top+;/ 当 high-i 小于等于 1 的时候，就不往栈中放了，这就是外层 while 循环能结束的原因/ 如果从 i 到高位之间的元素个数多于一个，那么需要再次排序if (high - i > 1) / 此时不排 i

15、 的原因是 i 位置上的元素已经确定了， i 前面的都是比 i 小的， i 后面的都 是比 i 大的stack1top = high;stack0top = 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.getR

16、child() != 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(); elsereturn false; else if (p.getLchild() != null && p.getRchild() = null) if (RecordNode)p.getLchild().getData().getKey().compareTo(RecordNode) p.getData().getKey() <= 0) return checkmax(p.