第10章 排序答案

《第10章 排序答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序（参考答案）一、选择题1.D2.D3.D4.B5.B6.B7.C,E8.A9.C10.C,D,F11.1D,C11.2A,D,F11.3B11.4(A,C,F)(B,D,E)12.C,D13.A14.B,D15.D16.D17.C18.A19.A20.C21.C22.B23.C24.C25.A26.C27.D28.C29.B30.C,B31.D32.D33.A34.D35.A36.A37.A38.C39.B40.C41.C42.B43.A44.B45.A46.C47.B,D48.D49.D50.D51.C52.E,G53.B54.C55.C56.B57.B58.A

2、59.1C59.2A59.3D59.4B59.5G60.1B60.2C60.3A61.1B61.2D61.3B61.4C61.5F62.A63.A64.B65.A66.A部分答案解释如下：18.对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。20.本题为步长为3的一趟希尔排序。24.枢轴是73。49.小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。64.因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。二、判断题1

3、.√2.×3.×4.×5.×6.×7.×8.×9.×10.×11.×12.×13.×14.√15.√16.×17.×18.×19.×20.×21.×22.×23.×24.×25.√26.×27.√28.×29.×30.×31.√部分答案解释如下：5.错误。例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。12.错误。堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。22.错误。待排序序列为正序时，简单插入排序比归并排序快。三、填空题1.比

4、较,移动2.生成有序归并段（顺串）,归并3.希尔排序、简单选择排序、快速排序、堆排序等4.冒泡,快速5.(1)简单选择排序(2)直接插入排序（最小的元素在最后时）6.免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。7.n(n-1)/28.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null(2)p->next(3)r!=null(4)r->datadata(5)r->next(6)p->next9.题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，

5、一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。(1)q->link!=NULL(2)r!=p(3)p->link(4)p->link=s(5)p=p->link10.(1)ir[n-i+1]11.(1)N(2)0(3)N-1(4)1(5)R[P].KEY

6、,(10,7,-9,0,47,23,1,8,98,36)13.快速14.(4,1,3,2,6,5,7)15.最好每次划分能得到两个长度相等的子文件。设文件长度n=2k-1，第一遍划分得到两个长度ën/2û的子文件，第二遍划分得到4个长度ën/4û的子文件，以此类推，总共进行k=log2(n+1)遍划分，各子文件长度均为1，排序结束。16.O(n2)17.O(nlog2n)18.(1)2*i(2)r[j].key>r[j+1].key(3)true(4)r[j](5)2*i19.(1)2*i(2)j<=r(3)j←j+1(4)x.key>heap[j].key(5)i←j(6)

7、j←2*i(7)x20.(1)j:=2*i(2)finished:=false(3)(r[j].key>r[j+1].key)(4)r[i]:=r[j](5)i:=j(6)j:=2*i(7)r[i]:=t;(8)sift(r,i,n)(9)r[1]:=r[i](10)sift(r,1,i-1)21.④是堆(1)选择(2)筛选法(3)O(nlog2n)(4)O(1)22.(1)选择(2)完全二叉树(3)O(Nlog2N)(4)O(1)(5)满足堆的性质23.(1)finish:=false(2)h[i]: