第7章排序习题参考答案.docx
- 文档编号:16920586
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:16
- 大小:59.85KB
第7章排序习题参考答案.docx
《第7章排序习题参考答案.docx》由会员分享,可在线阅读,更多相关《第7章排序习题参考答案.docx(16页珍藏版)》请在冰点文库上搜索。
第7章排序习题参考答案
第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.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.若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的比较和数据元素的移动。
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与r
Nodeswap=r.getNext();
r.setNext(r.getNext().getNext());//r的next指向其后继的后继
swap.setNext(p.getNext());
p.setNext(swap);//p的后继为swap
}
p=p.getNext();
}//while
p.setNext(null);
}
3.试设计算法,实现双向冒泡排序(即相邻两遍向相反方向冒泡)。
参考答案:
//产生随机数方法
publicstaticint[]random(intn){
if(n>0){
inttable[]=newint[n];
for(inti=0;i table[i]=(int)(Math.random()*100); //产生一个0~100之间的随机数 } returntable; } returnnull; } //输出数组元素方法 publicstaticvoidprint(int[]table) { if(table.length>0){ for(inti=0;i } } } //双向冒泡排序方法 publicstaticvoiddbubblesort(int[]table){ inthigh=table.length; intleft=1; intright=high-1; intt=0; do{ //正向部分 for(inti=right;i>=left;i--){ if(table[i] inttemp=table[i]; table[i]=table[i-1]; table[i-1]=temp; t=i; } } left=t+1; //反向部分 for(inti=left;i if(table[i] 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.length<2){ 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;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-low>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.试设计算法,判断完全二叉树是否为大顶堆。 参考答案: 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; } } } 四、上机实践题 1.编写程序,对直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序和归并排序进行测试。 参考答案: packagech07Exercise; importch07.*; publicclassExercise7_4_1{ publicstaticvoidmain(String[]args)throwsException{ int[]d={52,39,67,95,70,8,25,52}; int[]dlta={5,3,1};//希尔排序增量数组 intmaxSize=20;//顺序表空间大小 SeqListL=newSeqList(maxSize);//建立顺序表 for(inti=0;i RecordNoder=newRecordNode(d[i]); L.insert(L.length(),r); } L.display(); Scanners=newScanner(System.in); intxz=s.nextInt(); switch(xz){ case1: L.insertSort(); break;//直接插入排序 case2: L.shellSort(dlta); break;//希尔排序 case3: L.bubbleSort(); break;//冒泡排序 case4: L.quickSort(); break;//快速排序 case5: L.selectSort(); break;//直接选择排序 case6: L.heapSort();//堆排序 break; case7: L.mergeSort();//归并排序 break; } L.display(); } } 运行结果: 2.编写程序,对带监视哨的直接插入排序进行测试。 参考答案: packagech07Exercise; importch07.RecordNode; importch07.SeqList; publicclassExercise7_4_2extendsSeqList{ publicExercise7_4_2(intmaxSize){ super(maxSize); } publicvoiddisplay(){//输出数组元素 for(inti=1;i } } publicstaticvoidmain(String[]args)throwsException{ int[]d={52,39,67,95,70,8,25,52}; intmaxSize=20;//顺序表空间大小 SeqListL=newExercise7_4_2(maxSize);//建立顺序表 RecordNoder=newRecordNode(0); L.insert(L.length(),r); for(inti=0;i r=newRecordNode(d[i]); L.insert(L.length(),r); } L.display(); L.insertSortWithGuard(); L.display(); } } 运行结果: 3.编写程序,要求随机生成10000个数,并比较直接插入排序、直接选择排序、冒泡排序、快速排序和堆排序的排序性能。 参考答案: packagech07Exercise; importch07.*; publicclassExercise7_4_3{ staticintmaxSize=10000;//排序关键码个数 publicstaticvoidmain(String[]args)throwsException{ int[]d=newint[maxSize];//顺序表空间大小 for(inti=0;i d[i]=(int)(Math.random()*100); } SeqListL; L=createList(d); L=createList(d); L=createList(d); L=createList(d); L=createList(d); } privatestaticSeqListcreateList(int[]d)throwsException{ SeqListL=newSeqList(maxSize);//建立顺序表 for(inti=0;i RecordNoder=newRecordNode(d[i]); L.insert(L.length(),r); } returnL; } publicstaticlongtestSortTime(SeqListL,charsortmethod){ longstartTime,endTime,testTime; startTime=System.currentTimeMillis(); switch(sortmethod){ case'i': L.insertSort(); 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; returntestTime; } } 运行结果: 如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。