2022年排序习题参考答案 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年排序习题参考答案 .pdf》由会员分享,可在线阅读,更多相关《2022年排序习题参考答案 .pdf(11页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
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.插入排序D.堆排序5下列排序方法中,( D )所需的辅助空间
2、最大。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
3、 )。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、排序中,若初始记录序列基本有序,则选用直接插入排序 。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、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 11 页 - - - - - - - - - 和数据元素的移动。10在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的是快速排序,需要内存容量最多的是基数排序。三、算法设计题1 试设计算法,用插入排序方法对单链表进行排序。参考答案 : public static void insertSort(LinkList L) Node p, q, r, u; p = L.getHead().getNe
6、xt(); 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()
7、; 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); /制造一个最前面的节点
8、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
9、.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
10、- 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;
11、stack0top = 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 11 页 - - - - - - - - - top+; /要是栈顶不空,那么继续 while (top != 0) /将高位和低位出栈 /低位:排序开始的位置 top-; int low = stack0top; /高位:排序结束的位置 int high = stack1top; /将高位作为基准位置 /基准位置 int pivot = high; int i = low; for (int
12、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; stack0
13、top = 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.getLch
14、ild() != 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 f
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年排序习题参考答案 2022 排序 习题 参考答案
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内