2022年排序习题参考答案 .pdf

习题七 参考答案一、选择题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. 8 8.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( 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. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 和数据元素的移动。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() = (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 试设计算法，用选择排序方法对单链表进行排序。参考答案 : / 单链表选择排序算法 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(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 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 = left; i right + 1; i+) if (tablei tablei - 1) int temp = tablei; tablei = tablei - 1; tablei - 1 = temp; t = i; right = t - 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - top+; /要是栈顶不空，那么继续 while (top != 0) /将高位和低位出栈 /低位：排序开始的位置 top-; int low = stack0top; /高位：排序结束的位置 int high = stack1top; /将高位作为基准位置 /基准位置 int pivot = high; int i = low; for (int j = low; j high; j+) if (aryj 1) /此时不排i 的原因是 i 位置上的元素已经确定了，i 前面的都是比i 小的， i 后面的都是比i 大的 stack1top = i - 1; stack0top = low; top+; /当 high-i小于等于 1 的时候，就不往栈中放了，这就是外层while 循环能结束的原因 /如果从 i 到高位之间的元素个数多于一个，那么需要再次排序 if (high - i 1) /此时不排i 的原因是 i 位置上的元素已经确定了，i 前面的都是比i 小的， i 后面的都是比i 大的 stack1top = high; stack0top = i + 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - else return false; 四、上机实践题 1. 编写程序，对直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序和归并排序进行测试。参考答案 : package ch07Exercise; import ch07.*; import java.util.Scanner; public class Exercise7_4_1 public static void main(String args) throws Exception int d = 52, 39, 67, 95, 70, 8, 25, 52; int dlta = 5, 3, 1; /希尔排序增量数组 int maxSize = 20; /顺序表空间大小 SeqList L = new SeqList(maxSize); /建立顺序表 for (int i = 0; i d.length; i+) RecordNode r = new RecordNode(di); L.insert(L.length(), r); System.out.println(排序前： ); L.display(); System.out.println(请选择排序方法：); System.out.println(1-直接插入排序 ); System.out.println(2-希尔排序 ); System.out.println(3-冒泡排序 ); System.out.println(4-快速排序 ); System.out.println(5-直接选择排序 ); System.out.println(6-堆排序 ); System.out.println(7-归并排序 ); Scanner s = new Scanner(System.in); int xz = s.nextInt(); switch (xz) case 1: L.insertSort(); break; /直接插入排序 case 2: L.shellSort(dlta); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - break; /希尔排序 case 3: L.bubbleSort(); break; /冒泡排序 case 4: L.quickSort(); break; /快速排序 case 5: L.selectSort(); break; /直接选择排序 case 6: L.heapSort(); /堆排序 break; case 7: L.mergeSort(); /归并排序 break; System.out.println(排序后： ); L.display(); 运行结果 : 2编写程序，对带监视哨的直接插入排序进行测试。参考答案 : package ch07Exercise; import ch07.RecordNode; import ch07.SeqList; public class Exercise7_4_2 extends SeqList 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - public Exercise7_4_2(int maxSize) super(maxSize); public void display() /输出数组元素 for (int i = 1; i length(); i+) System.out.print( + getRecord()i.getKey().toString(); System.out.println(); public static void main(String args) throws Exception int d = 52, 39, 67, 95, 70, 8, 25, 52; int maxSize = 20; /顺序表空间大小 SeqList L = new Exercise7_4_2(maxSize); /建立顺序表 RecordNode r = new RecordNode(0); L.insert(L.length(), r); for (int i = 0; i d.length; i+) r = new RecordNode(di); L.insert(L.length(), r); System.out.println(排序前： ); L.display(); L.insertSortWithGuard(); System.out.println(排序后： ); L.display(); 运行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 3编写程序，要求随机生成10000 个数 , 并比较直接插入排序、直接选择排序、冒泡排序、快速排序和堆排序的排序性能。参考答案 : package ch07Exercise; import ch07.*; public class Exercise7_4_3 static int maxSize = 10000; /排序关键码个数 public static void main(String args) throws Exception int d = new intmaxSize; /顺序表空间大小 for (int i = 0; i maxSize; i+) di = (int) (Math.random() * 100); SeqList L; L = createList(d); System.out.println(直接插入排序所需时间： + testSortTime(L, i) + 毫秒 ); L = createList(d); System.out.println(冒泡排序所需时间： + testSortTime(L, b) + 毫秒 ); L = createList(d); System.out.println(快速排序所需时间： + testSortTime(L, q) + 毫秒 ); L = createList(d); System.out.println(直接选择排序所需时间： + testSortTime(L, s) + 毫秒 ); L = createList(d); System.out.println(堆排序所需时间： + testSortTime(L, h) + 毫秒 ); private static SeqList createList(int d) throws Exception SeqList L = new SeqList(maxSize); /建立顺序表 for (int i = 0; i d.length; i+) RecordNode r = new RecordNode(di); L.insert(L.length(), r); return L; public static long testSortTime(SeqList L, char sortmethod) long startTime, endTime, testTime; startTime = System.currentTimeMillis(); switch (sortmethod) case i: L.insertSort(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - break; case s: L.selectSort(); break; case b: L.bubbleSort(); break; case q: L.quickSort(); break; case h: L.heapSort(); break; endTime = System.currentTimeMillis(); testTime = endTime - startTime; return testTime; 运行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -