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） 稳定