您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第7章-排序-习题参考答案
习题七参考答案一、选择题1.内部排序算法的稳定性是指(D)。A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为0(nlogn)的排序方法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.2B.4C.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插入到有序表中时,为寻找插入位置需比较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.试设计算法,用插入排序方法对单链表进行排序。参考答案:publicstaticvoidinsertSort(LinkListL){Nodep,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.试设计算法,用选择排序方法对单链表进行排序。参考答案://单链表选择排序算法publicstaticvoidselectSort(LinkListL){//p为当前最小,r为此过程中最小,q为当前扫描接点Nodep,r,q;NodenewNode=newNode();newNode.setNext(L.getHead());L.setHead(newNode);//制造一个最前面的节点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())=(Integer.parseInt((String)r.getNext().getData()))){r=q;}q=q.getNext();}if(r!=p){//交换p与rNodeswap=r.getNext();r.setNext(r.getNext().getNext());//r的next指向其后继的后继swap.setNext(p.getNext());p.setNext(swap);//p的后继为swap}p=p.getNext();}//whilep.setNext(null);}3.试设计算法,实现双向冒泡排序(即相邻两遍向相反方向冒泡)。参考答案://产生随机数方法publicstaticint[]random(intn){if(n0){inttable[]=newint[n];for(inti=0;in;i++){table[i]=(int)(Math.random()*100);//产生一个0~100之间的随机数}returntable;}returnnull;}//输出数组元素方法publicstaticvoidprint(int[]table){if(table.length0){for(inti=0;itable.length;i++){System.out.print(table[i]+);}System.out.println();}}//双向冒泡排序方法publicstaticvoiddbubblesort(int[]table){inthigh=table.length;intleft=1;intright=high-1;intt=0;do{//正向部分for(inti=right;i=left;i--){if(table[i]table[i-1]){inttemp=table[i];table[i]=table[i-1];table[i-1]=temp;t=i;}}left=t+1;//反向部分for(inti=left;iright+1;i++){if(table[i]table[i-1]){inttemp=table[i];table[i]=table[i-1];table[i-1]=temp;t=i;}}right=t-1;}while(left=right);}4.试设计算法,使用非递归方法实现快速排序。参考答案:publicstaticvoidNonrecursiveQuickSort(int[]ary){if(ary.length2){return;}//数组栈:记录着高位和低位的值int[][]stack=newint[2][ary.length];//栈顶部位置inttop=0;//低位,高位,循环变量,基准点//将数组的高位和低位位置入栈stack[1][top]=ary.length-1;stack[0][top]=0;top++;//要是栈顶不空,那么继续while(top!=0){//将高位和低位出栈//低位:排序开始的位置top--;intlow=stack[0][top];//高位:排序结束的位置inthigh=stack[1][top];//将高位作为基准位置//基准位置intpivot=high;inti=low;for(intj=low;jhigh;j++){if(ary[j]=ary[pivot]){inttemp=ary[j];ary[j]=ary[i];ary[i]=temp;i++;}}//如果i不是基准位,那么基准位选的就不是最大值//而i的前面放的都是比基准位小的值,那么基准位//的值应该放到i所在的位置上if(i!=pivot){inttemp=ary[i];ary[i]=ary[pivot];ary[pivot]=temp;}if(i-low1){//此时不排i的原因是i位置上的元素已经确定了,i前面的都是比i小的,i后面的都是比i大的stack[1][top]=i-1;stack[0][top]=low;top++;}//当high-i小于等于1的时候,就不往栈中放了,这就是外层while循环能结束的原因//如果从i到高位之间的元素个数多于一个,那么需要再次排序if(high-i1){//此时不排i的原因是i位置上的元素已经确定了,i前面的都是比i小的,i后面的都是比i大的stack[1][top]=high;stack[0][top]=i+1;top++;}}}5.试设计算法,判断完全二叉树是否为大顶堆。参考答案:booleancheckmax(BiTreeNodet)//判断完全二叉树是否为大顶堆{BiTreeNodep=t;if(p.getLchild()==null&&p.getRchild()==null){returntrue;}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){returncheckmax(p.getLchild())&&checkmax(p.getRchild());}else{returnfalse;}}elseif(p.getLchild()!=null&&p.getRchild()==null){if((((RecordNode)p.getLchild().getData()).getKey()).compareTo(((RecordNode)p.getData()).getKey())=0){returncheckmax(p.getLchild());}else{returnfalse;}}elseif(p.getLchild()==null&&p.getRchild()!=null){if((((RecordNode)p.getRchild().getData()).getKey()).compareTo(((RecordNode)p.getData()).getKey())=0){returncheckmax(p.getRchild());}else{returnfalse;}}else{returnfalse;}}}
本文标题:第7章-排序-习题参考答案
链接地址:https://www.777doc.com/doc-5870429 .html