第10章排序(参考答案) 选择题 D2.D3.D 15.B 6.B7.CE8A9C 10.C,D, F11.ID,C11.2A,D,F 11:3B14(ACF)(BDE)12CD13A14BD15.D16D17C18.A[19A20.c21.C 22.B23.c24.C25.A26.C27.D28.C|29.B30.C,B31.D32.D33.A34.D|35.A 36.A37.A38.C39.B40.C41.C42.B43.A44.B45.A46.C47.B,D48.D49.D 0.D51.C52.E,G53.B54.C5.C56.B57.B58.A59.1c59.2A59.3D59.4B59.5G 60.1B60.2C60.3A61.1B61.2D61.3B61.4C61.5F 62.A63.A64.B65.A6.A 部分答案解释如下 18.对于后三种排序方法两趟排序后,序列的首部或尾部的两个元素应是有序的两个极值, 而给定的序列并不满足。 20.本题为步长为3的一趟希尔排序。 24.枢轴是73 49.小根堆中,关键字最大的记录只能在叶结点上,故不可能在小于等于n/2」的结点上。 64.因组与组之间已有序,故将n/k个组分别排序即可,基于比较的排序方法每组的时间下 界为0(klog2k),全部时间下界为0( logik) 判断题 1.√|2.×|3.×4.×5.×6.×|7.×8.×9.×|10.11.12.|13 14.15.|16.17.1 部分答案解释如下: 5.错误。例如冒泡排序是稳定排序,将4,3,2,1按冒泡排序排成升序序列,第一趟变成 3,2,1,4,此时3就朝向最终位置的相反方向移动。 12.错误。堆是n个元素的序列, 可以看作是完全二叉树,但相对于根并无左小右大的要求,故其既不是二叉排序树,更不会 是平衡二叉树。 错误。待排序序列为正序时,简单插入排序比归并排序快 三、填空题 1.比较,移动2.生成有序归并段(顺串),归并3.希尔排序、简单选择排序、快速 排序、堆排序等 4.冒泡,快速5.(1)简单选择排序(2)直接插入排序(最小的元素在最后时) 免去查找过程中每一步都要检测整个表是否查找完毕,提高了查找效率 8.题中p指向无序区第一个记录,q指向最小值结点,一趟排序结束,p和q所指结点值交 换,同时向后移p指针。(1)!=null (2)p->next (3r!=null (4)r->data<g->data (5)r->next(6)p->next 9.题中为操作方便,先增加头结点(最后删除),p指向无序区的前一记录,r指向最小值 结点的前驱,一趟排序结束,无序区第一个记录与r所指结点的后继交换指针 (1)g->link!=NULL(2)r!=p (3)p->link (4)p->link=s (5)p=p->link
第 10 章 排序（参考答案） 一、选择题 1.D 2.D 3.D 4.B 5.B 6.B 7.C,E 8.A 9.C 10.C,D,F 11.1D,C 11.2A,D,F 11.3B 11.4(A,C,F)(B,D,E) 12.C,D 13.A 14.B,D 15.D 16.D 17.C 18.A 19.A 20.C 21.C 22.B 23.C 24.C 25.A 26.C 27.D 28.C 29.B 30.C,B 31.D 32.D 33.A 34.D 35.A 36.A 37.A 38.C 39.B 40.C 41.C 42.B 43.A 44.B 45.A 46.C 47.B,D 48.D 49.D 50.D 51.C 52.E,G 53.B 54.C 55.C 56.B 57.B 58.A 59.1C 59.2A 59.3D 59.4B 59.5G 60.1B 60.2C 60.3A 61.1B 61.2D 61.3B 61.4C 61.5F 62.A 63.A 64.B 65.A 66.A 部分答案解释如下： 18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值， 而给定的序列并不满足。 20. 本题为步长为 3 的一趟希尔排序。 24.枢轴是 73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于 n/2 的结点上。 64. 因组与组之间已有序，故将 n/k 个组分别排序即可，基于比较的排序方法每组的时间下 界为 O(klog2k),全部时间下界为 O(nlog2k)。 二、判断题 1.√ 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. 比较,移动 2.生成有序归并段（顺串）,归并 3.希尔排序、简单选择排序、快速 排序、堆排序等 4. 冒泡,快速 5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时） 6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 7. n(n-1)/2 8.题中 p 指向无序区第一个记录，q 指向最小值结点，一趟排序结束，p 和 q 所指结点值交 换，同时向后移 p 指针。(1)!=null (2)p->next (3)r!=null (4)r->data<q->data (5)r->next (6)p->next 9. 题中为操作方便，先增加头结点（最后删除），p 指向无序区的前一记录，r 指向最小值 结点的前驱，一趟排序结束，无序区第一个记录与 r 所指结点的后继交换指针。 (1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link
10.(1)i<n-i+1(2)j<=n-i+1 (3)[j]. key<r [min]. key (4)min (5)max (6)r[max]<-r[n-i+1] 11.(1)N(2)0(3)N-1(4)1(5)R[P].KEY<R[].KEY(6)R[P].LINK (7)(N+2)(N-1)/2 (8)N-1(9)0(10)0(1)(每个记录增加一个字段) (11)稳定(请注意I 的步长为-1) 12.3,(10,7,-9,0,47,23,1,8,98,36) 14.(4,1,3,2,6,5,7) 15.最好每次划分能得到两个长度相等的子文件。设文件长度n=2*-1,第一遍划分得到两个 长度Ln/2」的子文件,第二遍划分得到4个长度Ln/4」的子文件,以此类推,总共进行 k=log2(n+1)遍划分,各子文件长度均为1,排序结束。 16.0(n2) 17. 0(nlog, n) 18.(1)2*i(2)r[j].key>r[+1].key(3)true (4)r[j](5)2*i 19.(1)2*i(2)j=r(3)j←j1(4)x.key>heap[j.key(5)i←j(6)j←2*i 20(1)j: =2*i(2)finished: =false (3)(r[j]. key>r[j+1]. key )(4r[i]: =r[](5)i: =j (6)j:=2*i(7)r[i]:=t; (8)sift(r, i, n) (9)r[1]:=[i] (10)sift(r,1,i-1) 21.④是堆(1)选择(②2)筛选法(3)0(nlog2n)(4)0(1) 2.(1)选择(2)完全二叉树 (3)0(N1og2N)(4)0(1)(5)满足堆的性质 23(1)finish: =false(2)h[i]: =h[j]: i:=j: j: =2*:(3h[i]: =x(4)h, k,n (5)sift(h,1,r-1) 24. D, Q, F, X, A, P, B, N, M,Y, C, Wh 25.(1)p[k]:=j(2)i:=i+1(3)k=0(4)m:=n(5)m<n(6)a[i]:=a[m(7)a[m:=t 26.程序(a)(1)true (2)a[i]:=t 3)2 TO n step 2 (tru (5)NOT flag 程序(b)(1) (2)a[i]=t (3)(i=2;i<=n;i+=2) (5)flag 27.(Q, A, C, S, Q,D,F, X, R, H, M, Y),(F, H, C, D, Q,A,M,Q, R, S, Y, X) 初始归并 段(顺串 29.初始归并段,初始归并段,减少外存信息读写次数(即减少归并趟数),增加归并路数和 减少初始归并段个数 30.「n/m1 31.(1)m,j-1(2)m:=j+1 (3)j+1,n(4)n:=j-1 最大栈空间用量为 0(logn)。 四、应用题 1.假设含n个记录的序列为{R,R2,…,R},其相应的关键字序列为{K,K,…,K}, 这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系Ks≤Ks2≤…≤Ks 按此固有关系将n个记录序列重新排列为{Rs,Rs,…,Rs。}。若整个排序过程都在内存 中完成,则称此类排序问题为内部排序 排序方平均时间 最坏情况 辅助空间稳定不稳定排序举例 直接插 0(n2) 0(n2) 0(1) 稳定
10.(1)i<n-i+1 (2)j<=n-i+1 (3)r[j].key<r[min].key (4)min!=i (5)max==i (6)r[max]<-->r[n-i+1] 11.(1)N (2)0 (3)N-1 (4)1 (5)R[P].KEY<R[I].KEY (6)R[P].LINK (7)(N+2)(N-1)/2 (8)N-1 (9)0 (10)O(1)(每个记录增加一个字段) (11)稳定 （请注意 I 的步长为-1） 12. 3,(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*i 19.(1)2*i (2)j<=r (3)j←j+1 (4)x.key>heap[j].key (5)i ←j (6)j←2*i (7)x 20.(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]:=h[j]; i:=j; j:=2*j; (3)h[i]:=x (4)h,k,n (5)sift(h,1,r-1) 24. {D,Q,F,X,A,P,B,N,M,Y,C,W} 25. (1)p[k]:=j (2)i:=i+1 (3)k=0 (4)m:=n (5)m<n (6)a[i]:=a[m] (7)a[m]:=t 26. 程序(a)(1)true (2)a[i]:=t (3)2 TO n step 2 (4)true (5)NOT flag 程 序 (b)(1)1 (2)a[i]=t (3)(i=2;i<=n;i+=2) (4)1 (5)flag 27.（Q,A,C,S,Q,D,F,X,R,H,M,Y）,(F,H,C,D,Q,A,M,Q,R,S,Y,X) 28. 初始归并 段(顺串) 29. 初始归并段,初始归并段,减少外存信息读写次数（即减少归并趟数）,增加归并路数和 减少初始归并段个数。 30. n/m 31．(1)m,j-1 (2) m:=j+1 (3)j+1,n (4) n:=j-1 最大栈空间用量为 O(logn)。 四、应用题 1. 假设含 n 个记录的序列为{ R1, R2, …，Rn }，其相应的关键字序列为{ K1, K2, …，Kn }， 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 Ks1≤Ks2≤…≤Ksn， 按此固有关系将 n 个记录序列重新排列为{ Rs1, Rs2, …，Rsn }。若整个排序过程都在内存 中完成，则称此类排序问题为内部排序。 2. 排序方 法 平均时间 最坏情况 辅助空间 稳定 性 不稳定排序举例 直接插 O（n 2） O（n 2） O（1） 稳定
入排序 折半插0(n2) 0(n2) 0(1) 稳定 入排序 二路插0(n2) 稳定 入排序 表插入0(n2) 0(n2) 0(1) 稳定 排序 起泡排0(n2) 0(n2) 0(1) 稳定 序 直接选0(n2) 0(n2) 0(1) 不稳 2,2’,1 择排序 定 希尔排0(n23) 0(1) 不稳|3,2,2,1(d=2,d=1) 序 定 快速排0( nlog2n) 0(logn)不稳 2,2’,1 序 定 堆排序0( nlog2n)0( nlog2n) 0(1) 不稳|2,1,1’(极大堆) 定 2-路归0( nlog2n)0( logan) 稳定 并排序 基数排 0(rd)稳定 (d*(rd+n 3.这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前 后发生了变化,而题中叙述和排序中稳定性的定义无关,所以此说法不对。对4,3,2,1 起泡排序就可否定本题结论 4.可以做到。取a与b进行比较,c与d进行比较。设a>b,cd(a<b和c<d情况类似),此 时需2次比较,取b和d比较,若b>d,则有序a>b)d;若b<d时则有序c>d>b,此时已进 行了3次比较。再把另外两个元素按折半插入排序方法,插入到上述某个序列中共需4次比 较,从而共需7次比较。 5.本题答案之一请参见第9章的“四、应用题”第70题,这里用分治法求解再给出另一参 考答案 对于两个数x和y,经一次比较可得到最大值和最小值:对于三个数x,y,z,最多经3 次比较可得最大值和最小值;对于n(n>3)个数,将分成长为n-2和2的前后两部分A和B, 分别找出最大者和最小者:MaxA、Min、Mxs、Min,最后Max=Max,Max}和Min={Min,Min}。 对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。设C(n)是所需的最多 比较次数,根据上述原则,当n>3时有如下关系式 n=3 C(n)=C(n-2)+3n>3 通过逐步递推,可以得到:C(n)「3n/2}2。显然,当n>=3时,2n-3>3n/2-2。事实上, 「3n/22是解决这一问题的比较次数的下限 6.假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个,则描述n个 记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子,则说明尚有两种状态没 有分辨出来。我们知道,若二叉树高度是h,则叶子结点个数最多为2;反之,若有u个
入排序 折半插 入排序 O（n 2） O（n 2） O（1） 稳定 二路插 入排序 O（n 2） O（n 2） O（n） 稳定 表插入 排序 O（n 2） O（n 2） O（1） 稳定 起泡排 序 O（n 2） O（n 2） O（1） 稳定 直接选 择排序 O（n 2） O（n 2） O（1） 不稳 定 2,2’,1 希尔排 序 O（n 1.3） O（n 1.3） O（1） 不稳 定 3,2,2’,1(d=2,d=1) 快速排 序 O（nlog2n） O（n 2） O（log2n） 不稳 定 2,2’,1 堆排序 O（nlog2n） O（nlog2n） O（1） 不稳 定 2,1,1’(极大堆) 2-路归 并排序 O（nlog2n） O（nlog2n） O（n） 稳定 基数排 序 O ( d*(rd+n) ) O ( d*(rd+n) ) O (rd ) 稳定 3. 这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、 后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对 4，3，2，1 起泡排序就可否定本题结论。 4. 可以做到。取 a 与 b 进行比较，c 与 d 进行比较。设 a>b,c>d(a<b 和 c<d 情况类似)，此 时需 2 次比较，取 b 和 d 比较，若 b>d，则有序 a>b>d；若 b<d 时则有序 c>d>b，此时已进 行了 3 次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需 4 次比 较，从而共需 7 次比较。 5. 本题答案之一请参见第 9 章的“四、应用题”第 70 题，这里用分治法求解再给出另一参 考答案。 对于两个数 x 和 y，经一次比较可得到最大值和最小值；对于三个数 x,y,z，最多经 3 次比较可得最大值和最小值；对于 n(n>3)个数，将分成长为 n-2 和 2 的前后两部分 A 和 B， 分别找出最大者和最小者：MaxA、MinA、MaxB、MinB，最后 Max={MaxA,MaxB}和 Min={MinA,MinB}。 对 A 使用同样的方法求出最大值和最小值，直到元素个数不超过 3。设 C(n)是所需的最多 比较次数，根据上述原则，当 n>3 时有如下关系式： C(n)= − + = = ( 2) 3 3 3 3 1 2 C n n n n 通过逐步递推，可以得到：C(n)=3n/2-2。显然，当 n>=3 时，2n-3>3n/2-2。事实上， 3n/2-2 是解决这一问题的比较次数的下限。 6. 假定待排序的记录有 n 个。由于含 n 个记录的序列可能出现的状态有 n!个，则描述 n 个 记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没 有分辨出来。我们知道，若二叉树高度是 h，则叶子结点个数最多为 2 h-1；反之，若有 u 个
叶子结点,则二叉树的高度至少为「1og2u+1。这就是说,描述n个记录排序的判定树必定 存在一条长度为「log2(n!)1的路径。即任何一个籍助“比较”进行排序的算法,在最坏情 况下所需进行的比较次数至少是「log2(m!)。根据斯特林公式,有「log2(n!)1=0(nlog2n) 即籍助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为0ω nlog2n)。证 7.答:拓扑排序,是有向图的顶点依照弧的走向,找出一个全序集的过程,主要是根据与 顶点连接的弧来确定顶点序列:冒泡排序是借助交换思想通过比较相邻结点关键字大小进行 排序的算法。 8.直接插入排序的基本思想是基于插入,开始假定第一个记录有序,然后从第二个记录开 始,依次插入到前面有序的子文件中。即将记录R[i](2<=i<=n)插入到有序子序列R[1.i-1] 中,使记录的有序序列从R[1..i-1]变为R[1.i,最终使整个文件有序。共进行n-1趟插 入。最坏时间复杂度是0(m2),平均时间复杂度是0(n2),空间复杂度是0(1),是稳定排序 简单选择排序的基本思想是基于选择,开始有序序列长度为零,第i(1<=i<n)趟简单选 择排序是,从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录,和第i个记录交换, 使有序序列逐步扩大,最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0(mn2), 平均时间复杂度是0(m2),空间复杂度是0(1),是不稳定排序 二路并归排序的基本思想是基于归并,开始将具有n个待排序记录的序列看成是n个长 度为1的有序序列,然后进行两两归并,得到「n/21个长度为2的有序序列,再进行两两归 并,得到「n/41个长度为4的有序序列。如此重复,经过「1ogn1趟归并,最终得到一个长 度为n的有序序列。最坏时间复杂度和平均时间复杂度都是0( nlogn),空间复杂度是0n) 是稳定排序 9.错误。快速排序,堆排序和希尔排序是时间性能较好的排序方法,但都是不稳定的排序 方法 10.等概率(后插),插入位置0..n,则平均移动个数为n/2 ∑(n-m*(n+1)2)*a-)2n+ 若不等概率,则平均移动个数为a=0 11.从节省存储空间考虑:先选堆排序,再选快速排序,最后选择归并排序 从排序结果的稳定性考虑:选择归并排序。堆排序和快速排序都是不稳定排序; 从平均情况下排序最快考虑:先选择快速排序 (1)堆排序,快速排序,归并排序(2)归并排序(3)快速排序(4)堆排序 13.平均比较次数最少:快速排序;占用空间最多:归并排序;不稳定排序算法:快速排 序、堆排序、希尔排序。 14.求前k个最大元素选堆排序较好。因为在建含n个元素的堆时,总共进行的关键字的比 较次数不超过4n,调整建新堆时的比较次数不超过2logn次。在n个元素中求前k个最大 元素,在堆排序情况下比较次数最多不超过4n+2klog2n 稳定分类是指,若排序序列中存在两个关键字值相同的记录Ri与Rj(Ki=Kj,i≠j)且Ri 领先于Rj,若排序后Ri与Rj的相对次序保持不变,则称这类分类是稳定分类(排序),否 则为不稳定分类 A,C和E是稳定分类(排序),B和D是不稳定分类(排序)
叶子结点，则二叉树的高度至少为 log2u+1。这就是说，描述 n 个记录排序的判定树必定 存在一条长度为 log2(n!) 的路径。即任何一个籍助“比较”进行排序的算法，在最坏情 况下所需进行的比较次数至少是 log2(n!)。根据斯特林公式，有 log2(n!) =O(nlog2n)。 即籍助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为 O(nlog2n)。证 毕。 7. 答：拓扑排序，是有向图的顶点依照弧的走向，找出一个全序集的过程，主要是根据与 顶点连接的弧来确定顶点序列；冒泡排序是借助交换思想通过比较相邻结点关键字大小进行 排序的算法。 8. 直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开 始，依次插入到前面有序的子文件中。即将记录 R[i](2<=i<=n)插入到有序子序列 R[1..i-1] 中，使记录的有序序列从 R[1..i-1]变为 R[1..i] ，最终使整个文件有序。共进行 n-1 趟插 入。最坏时间复杂度是 0(n2 )，平均时间复杂度是 0(n2 )，空间复杂度是 O(1)，是稳定排序。 简单选择排序的基本思想是基于选择，开始有序序列长度为零，第 i(1<=i<n)趟简单选 择排序是，从无序序列 R[i..n]的 n-i+1 记录中选出关键字最小的记录，和第 i 个记录交换， 使有序序列逐步扩大，最后整个文件有序。共进行 n-1 趟选择。最坏时间复杂度是 0(n2 )， 平均时间复杂度是 0(n2 )，空间复杂度是 O(1)，是不稳定排序。 二路并归排序的基本思想是基于归并，开始将具有 n 个待排序记录的序列看成是 n 个长 度为 1 的有序序列，然后进行两两归并，得到 n/2 个长度为 2 的有序序列，再进行两两归 并，得到 n/4 个长度为 4 的有序序列。如此重复，经过 log2n 趟归并，最终得到一个长 度为 n 的有序序列。最坏时间复杂度和平均时间复杂度都是 0(nlog2n)，空间复杂度是 O(n)， 是稳定排序。 9. 错误。快速排序，堆排序和希尔排序是时间性能较好的排序方法，但都是不稳定的排序 方法。 10. 等概率（后插），插入位置 0..n，则平均移动个数为 n/2。 若不等概率，则平均移动个数为 − = + 1 0 (n -i)/(n *(n 1)/2) *(n -i) n i = 3 2n +1 11. 从节省存储空间考虑：先选堆排序，再选快速排序，最后选择归并排序； 从排序结果的稳定性考虑：选择归并排序。堆排序和快速排序都是不稳定排序； 从平均情况下排序最快考虑：先选择快速排序。 12. (1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序 13. 平均比较次数最少: 快速排序; 占用空间最多: 归并排序; 不稳定排序算法:快速排 序、堆排序、希尔排序。 14. 求前 k 个最大元素选堆排序较好。因为在建含 n 个元素的堆时，总共进行的关键字的比 较次数不超过 4n ,调整建新堆时的比较次数不超过 2log2n 次。在 n 个元素中求前 k 个最大 元素，在堆排序情况下比较次数最多不超过 4n+2klog2n。 稳定分类是指，若排序序列中存在两个关键字值相同的记录 Ri 与 Rj(Ki=Kj,i≠j)且 Ri 领先于 Rj，若排序后 Ri 与 Rj 的相对次序保持不变,则称这类分类是稳定分类（排序），否 则为不稳定分类。 A，C 和 E 是稳定分类（排序），B 和 D 是不稳定分类（排序）。 15. a,c,b c,a,b a,b,c a:c b,a,c b:c b,c,a c,b,a b:c a:c a:b
16.(1)此为直接插入排序算法,该算法稳定。 (2)r[0]的作用是监视哨,兔去每次检测文件是否到尾,提高了排序效率 采用x.key<=r[j].key描述算法后,算法变为不稳定排序,但能正常工作。 17.(1)横线内容:①m②1③0 (2)flag起标志作用。若未发生交换,表明待排序列已有序,无需进行下趟排序 (3)最大比较次数n(n-1)/2,最大移动次数3n(n-1)/2 (4)稳定 18.(1)①499②A[j>A[j+1]③b:=true(②2)冒泡排序(3)499次比较,0次交换 (4)n(n-1)/2次比较,n(n-1)/2次交换(相当3n(n-1)/2次移动),本题中n=500,故 有124750次比较和交换(相当373250次移动)。 19.答:此排序为双向起泡排序:从前向后一趟排序下来得到一个最大值,若其中发生交换, 则再从后向前一趟排序,得到一个最小值 12,23,35,16,25,36,19,21,16,47 二趟:12,16,23,35,16,25,36,19,21,47 12,16,23,16,25,35,19,21,36,47 四趟:12,16,16,23,19,25,35,21,36,47五趟:12,16,16,19,23,25,21,35,36,47 六趟:12,16,16,19,21,23,25,35,36,47 七趟: 12,16,16,19,21,23,25,35,36,47 .对冒泡算法而言,初始序列为反序时交换次数最多。若要求从大到小排序,则表现为初 始是上升序 21.证明:起泡排序思想是相邻两个记录的关键字比较,若反序则交换,一趟排序完成得到 一个极值。由题假设知R在R之前且K>R1,即说明R和R1是反序;设对于R之前全部记录 1—R-(其中包括K)中关键字最大为Kmax,则Kmax≥Kj,故经过起泡排序前i-2次后,R1 的关键字一定为Kmax,又因Kmax≥K>R,故R1和R为反序,由此可知R-1和R必定交换 证毕 22.采用直接插入排序算法,因为记录序列已基本有序,直接插入排序比较次数少,且由于 少量次序不对的记录与正确位置不远,使直接插入排序记录移动次数也相对较少,故选直接 插入排序算法。 23.各带标号语句的频度:(1)n (3)(n+2)(n-1)/2 (4)n(n-1)/2 (5)n-1 时间复杂度0(n2),属于直接选择排序 24 6,13,28,39,41,72,85,20 r=7↑ 20<39i=1↑m2↑r=3↑ i=3r=3m=3 r=2i=3 将r+1(即第3个)后的元素向后移动,并将20放入r+1处,结果为 6,13,20,28,39,41,72,85 (1)使用二分法插入排序所要进行的比较次数,与待排序的记录的初始状态无关。不 论待排序序列是否有序,已形成的部分子序列是有序的。二分法插入首先査找插入位置,插 入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。 (2)一些特殊情况下,二分法插入排序要比直接插入排序要执行更多的比较。例如
16. (1)此为直接插入排序算法，该算法稳定。 (2)r[O]的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。 采用 x.key<=r[j].key 描述算法后，算法变为不稳定排序，但能正常工作。 17. (1) 横线内容:①m ②1 ③0 ④1 (2)flag 起标志作用。若未发生交换，表明待排序列已有序，无需进行下趟排序。 (3)最大比较次数 n(n-1)/2，最大移动次数 3n(n-1)/2 (4)稳定 18. (1) ①499 ②A[j]>A[j+1] ③b:=true (2)冒泡排序 (3)499次比较,0次交换 (4) n(n-1)/2 次比较，n(n-1)/2 次交换（相当 3n(n-1)/2 次移动），本题中 n=500,故 有 124750 次比较和交换（相当 373250 次移动）。 19. 答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换， 则再从后向前一趟排序，得到一个最小值。 一趟： 12,23,35,16,25,36,19,21,16,47 二趟：12,16,23,35,16,25,36,19,21,47 三趟： 12,16,23,16,25,35,19,21,36,47 四趟：12,16,16,23,19,25,35,21,36,47 五趟：12,16,16,19,23,25,21,35,36,47 六趟： 12,16,16,19,21,23,25,35,36,47 七趟： 12,16,16,19,21,23,25,35,36,47 20. 对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初 始是上升序。 21. 证明：起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到 一个极值。由题假设知 Rj 在 Ri 之前且 Kj>Ri，即说明 Rj和 Ri 是反序；设对于 Ri 之前全部记录 1—Ri-1(其中包括 Kj)中关键字最大为 Kmax，则 Kmax≥Kj，故经过起泡排序前 i-2 次后，Ri-1 的关键字一定为 Kmax，又因 Kmax≥Kj>Ri，故 Ri-1和 Ri 为反序，由此可知 Ri-1和 Ri 必定交换， 证毕。 22.采用直接插入排序算法，因为记录序列已基本有序，直接插入排序比较次数少，且由于 少量次序不对的记录与正确位置不远，使直接插入排序记录移动次数也相对较少，故选直接 插入排序算法。 23. 各带标号语句的 频度：(1)n (2)n-1 (3)(n+2)(n-1)/2 (4)n(n-1)/2 (5)n-1 时间复杂度 O(n²), 属于直接选择排序。 24. 6, 13, 28, 39, 41, 72, 85, 20 i=1↑ m=4↑ r=7↑ 20<39 i=1↑m=2↑r=3↑ 20>13 i=3 r=3 m=3 20<28 r=2 i=3 将 r+1( 即 第 3 个 ) 后 的 元 素 向 后 移 动 ， 并 将 20 放 入 r+1 处 ， 结 果 为 6,13,20,28,39,41,72,85。 （1）使用二分法插入排序所要进行的比较次数，与待排序的记录的初始状态无关。不 论待排序序列是否有序，已形成的部分子序列是有序的。二分法插入首先查找插入位置，插 入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。 （2）一些特殊情况下，二分法插入排序要比直接插入排序要执行更多的比较。例如