第十章参考答案 、填空 稳定、不稳定 2内部、外部 3.插入排序、交换排序、选择排序、归并排序4键值比较、记录移动、附加空间 直接、折半、表、希尔 70(n2)、O(1) 8n-l、nag=l、n-i 9.O(m 10j-、r[=r、++、r=r、x 11.o(nlog2n)、O(n2) 12.n-1、kj、k!= 13.O(n2) 14n-1、存储区 15叶子、树根、+∝ 17完全二叉树、n/2 l8.O(1)、 o(nlog2n) 19.a[ii] 20.有序 23冒泡排序、快速排序 24插入排序、快速排序 、单项选择 7. 8.④9.①10.③11.② 16.③17.③18 3.③ 四、简答及应用 1.①直接插入排序 序号 关键字834063138435965739796115 i=2408363138435965739796115 i=3406383[138435965739796115 i=4134063838435965739796115] i=5134063838435965739796115] i=6133540638384 [965739796115] 96 i=8133540 i=1013 39405763798384966115 =1113 57616379838496[151 ②直接选择排序 序号1 910 12 关键字83406313 113[4063838435 39 i=21315[63838435965739796140] 1=3131535[838463965739 535398 i=51315353940[63965783796184] i=6131535394057966383796184]
1 第十章 参考答案 二、填空 1．稳定、不稳定 2.内部、外部 3．插入排序、交换排序、选择排序、归并排序 4.键值比较、记录移动、附加空间 5．直接、折半、表、希尔 6.2、r[j]、r[0] 7.O（n 2）、O（1） 8.n-1、flag=1、n-i 9.O(n2 ) 10.j--、r[i]=r[j]、j++、r[j]=r[i]、x 11.O(nlog2n)、O(n2 ) 12.n-1、k=j、k!=I 13.O(n2 ) 14.n-1、存储区 15.叶子、树根、＋∝ 16.n-1、log2n、O(nlog2n) 17.完全二叉树、n/2 18.O(1)、O(nlog2n) 19.a[ii]、ii++、a[j]、j++、m、n、O(n-h+1) 20.有序 21．O(log2n) 22.O(n2 ) 23.冒泡排序、快速排序 24.插入排序、快速排序 三、单项选择 1. ③ 2. ③ 3. ② 4. ② 5. ② 6. ② 7. ③ 8. ④ 9. ① 10. ③ 11. ② 12. ③ 13. ③ 14. ④ 15. ④ 16. ③ 17. ③ 18. ② 19. ④ 20. ④ 21. ④ 22. ② 23. ③ 四、简答及应用 1．①直接插入排序 序号 1 2 3 4 5 6 7 8 9 10 11 12 关键字 83 40 63 13 84 35 96 57 39 79 61 15 i = 2 40 83 [63 13 84 35 96 57 39 79 61 15] i = 3 40 63 83 [13 84 35 96 57 39 79 61 15] i = 4 13 40 63 83 [84 35 96 57 39 79 61 15] i = 5 13 40 63 83 84 [35 96 57 39 79 61 15] i = 6 13 35 40 63 83 84 [96 57 39 79 61 15] i = 7 13 35 40 63 83 84 96 [57 39 79 61 15] i = 8 13 35 40 57 63 83 84 96 [39 79 61 15] i = 9 13 35 39 40 57 63 83 84 96 [79 61 15] i = 10 13 35 39 40 57 63 79 83 84 96 [61 15] i = 11 13 35 39 40 57 61 63 79 83 84 96 [15] i = 12 13 15 35 39 40 57 61 63 79 83 84 96 ②直接选择排序 序号 1 2 3 4 5 6 7 8 9 10 11 12 关键字 83 40 63 13 84 35 96 57 39 79 61 15 i = 1 13 [40 63 83 84 35 96 57 39 79 61 15] i = 2 13 15 [63 83 84 35 96 57 39 79 61 40] i = 3 13 15 35 [83 84 63 96 57 39 79 61 40] i = 4 13 15 35 39 [84 63 96 57 83 79 61 40] i = 5 13 15 35 39 40 [63 96 57 83 79 61 84] i = 6 13 15 35 39 40 57 [96 63 83 79 61 84]
i=713153539405761[638399684] i=81315353940576163[83799684] i=9131535394057616379839684 i=10131535394057616379839684 3539405766379838496] ③快速排序 关键字 83406313843596573979 第一趟排序后[154063136135795739]83 84] 第二趟排序后[13]15[63406135795739]8384[96 第三趟排序后1315[394061355763[79]838496 第四趟排序后1315[35]39[614057]63798384 第五趟排序后13 3539[57406163798384 第六趟排序后1315353940[57]61637983 第七趟排序后13153539405761637983 ④堆排序 关键字:834063138435965739796115 排序成功的序列:968483796361574039351513 排序过程如图简答题8-1.1、8-1.2、8-1.3所示。 ⑤归并排序 关键字 3340631384359657 796115 第一趟排序后[4083[1363][3584][57%6] 第二趟排序后[13406383][35578496][15396179 第三趟排序后[335405763838496][15396179 第四趟排序后131535394057616379838496 2.稳定排序有直接插入、冒泡排序、归并排序 不稳定排序有快速排序、直接选择排序、堆排序。举例如下: ①快速排序 初始状态4065384997651360 排序后 (65表示记录初始位置在65记录位置之后) ②堆排序 初始状态6538759780 排序后1327386565 ③直接排序 初始状态4065384997 排序后1338404960 3.直接选择相对于树形选择排序的优点:算法易懂,容易实现,基本上不需要附加 空间。而树形排序需要附加n-1附加空间 直接选择排序相对于树形选择排序的缺点:直接选择排序每一趟都不保留比较结果比 较次数较多,而树形排序则能利用大部分上一次的比较结果,因此时间性能比直接选择排序 优越 堆排序相对于树形排序的优点:堆排序除建第一个堆费时外,其余元素进行堆比较次 2
2 i = 7 13 15 35 39 40 57 61 [63 83 79 96 84] i = 8 13 15 35 39 40 57 61 63 [83 79 96 84] i = 9 13 15 35 39 40 57 61 63 79 [83 96 84] i = 10 13 15 35 39 40 57 61 63 79 83 [96 84] i = 11 13 15 35 39 40 57 61 63 79 83 84 [96] ③快速排序 关键字 83 40 63 13 84 35 96 57 39 79 61 15 第一趟排序后 [15 40 63 13 61 35 79 57 39] 83 [96 84] 第二趟排序后 [13] 15 [63 40 61 35 79 57 39] 83 84 [96] 第三趟排序后 13 15 [39 40 61 35 57] 63 [79] 83 84 96 第四趟排序后 13 15 [35] 39 [61 40 57] 63 79 83 84 96 第五趟排序后 13 15 35 39 [57 40] 61 63 79 83 84 96 第六趟排序后 13 15 35 39 40 [57] 61 63 79 83 84 96 第七趟排序后 13 15 35 39 40 57 61 63 79 83 84 96 ④堆排序 关键字： 83 40 63 13 84 35 96 57 39 79 61 15 排序成功的序列：96 84 83 79 63 61 57 40 39 35 15 13 排序过程如图简答题 8－1.1、8－1.2、8－1.3 所示。 ⑤归并排序 关键字 83 40 63 13 84 35 96 57 39 79 61 15 第一趟排序后 [40 83] [13 63] [35 84] [57 96] [39 79] [15 61] 第二趟排序后 [13 40 63 83] [35 57 84 96] [15 39 61 79] 第三趟排序后 [13 35 40 57 63 83 84 96] [15 39 61 79] 第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96 2．稳定排序有直接插入、冒泡排序、归并排序。 不稳定排序有快速排序、直接选择排序、堆排序。举例如下： ①快速排序 初始状态 40 65 38 49 97 65 13 60 排序后 13 38 40 49 60 65 65 97 （65 表示记录初始位置在 65 记录位置之后） ②堆排序 初始状态 65 38 75 97 80 13 27 65 排序后 13 27 38 65 65 75 80 97 ③直接排序 初始状态 40 65 38 49 97 65 13 60 排序后 13 38 40 49 60 65 65 97 3．直接选择相对于树形选择排序的优点：算法易懂，容易实现，基本上不需要附加 空间。而树形排序需要附加 n – 1 附加空间。 直接选择排序相对于树形选择排序的缺点：直接选择排序每一趟都不保留比较结果比 较次数较多，而树形排序则能利用大部分上一次的比较结果，因此时间性能比直接选择排序 优越。 堆排序相对于树形排序的优点：堆排序除建第一个堆费时外，其余元素进行堆比较次
数小于等于h(h表示n元素构成的完全二叉树的深度),而树形排序每次比较都是h次。因 此,堆排序时间复杂度小于树形排序。堆排序基本也不需要附加空间。 4.直接插入排序、直接选择排序、快速排序、堆排序和归并排序时空性如表: 平均时间最坏情况辅助空间 直接插入 O(n2) O(n2) O(n1) 直接选择 O(n2) O(1) 快速排序 堆排序 O(nlog2n) O(nlog2) 归并排序「onp2aoag2a)oa) 从上表可以得出:就平均时间性能而言,快速排序最佳,其所需时间最省,但快速排 序在最坏情况下,时间性能不如堆排序和归并排序。而后两者相比的结果是,当n较大时 归并排序所需时间优于堆排序,但它所需辅助空间最多。 注意,在所有排序方法中,没有哪一种是绝对最优的,有的适用于n较大的情况,有适 用于n较小的情况,还有的与关键字的分布和初始位置有关……因此,在实际使用时,需要 根据不同情况适当选用排序方法,甚至可将多种方法结合使用 5.分析:先按序列画出对应的完全二叉树,再看其是否满足堆的定义。按这一思路, 画出的完全二叉树见图简答8-5.1 显然序列(1)是堆,而序列(2)不是堆,值为7的元素应该上调,调整过程见图简答题8-52 6第一趟: 6,58,15,45,90,18,10,62] [46,58,15,45,90,18,10,62 一次交换之后回58,15,45,9.,18,国621 二次交换之后 网15.4.90,18.國621 三次交换之后[10,15,45,90,国58.62 [10,18,15.45 46,58,62] 四次交换之后10.1.1国x 以上“—”表示当前经比较不交换位置的元素。口”表示当前经比较交换位置的元素 第一趟:[10181545]46[905862] 第二趟:10[181545]46[6258] 第三趟:10[15]1845]46[58]6290 1015184546586290 (1)插入排序的每趟的结果 初始值健值序列[12]592063124 i=2 512]92063124 i=3 5912]2063124 5912 631 31l
3 数小于等于 h（h 表示 n 元素构成的完全二叉树的深度），而树形排序每次比较都是 h 次。因 此，堆排序时间复杂度小于树形排序。堆排序基本也不需要附加空间。 4．直接插入排序、直接选择排序、快速排序、堆排序和归并排序时空性如表： 平均时间 最坏情况 辅助空间 直接插入 O(n2) O(n2) O(n1) 直接选择 O(n2) O(n2) O(1) 快速排序 O(nlg2n) O(n2) O(nlog2n) 堆排序 O(nlog2n) O(nlog2) O(1) 归并排序 O(nlog2n) O(nlog2n) O(n) 从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排 序在最坏情况下，时间性能不如堆排序和归并排序。 而后两者相比的结果是，当 n 较大时， 归并排序所需时间优于堆排序，但它所需辅助空间最多。 注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于 n 较大的情况，有适 用于 n 较小的情况，还有的与关键字的分布和初始位置有关……因此，在实际使用时，需要 根据不同情况适当选用排序方法，甚至可将多种方法结合使用。 5．分析：先按序列画出对应的完全二叉树，再看其是否满足堆的定义。按这一思路， 画出的完全二叉树见图简答 8-5.1. 显然序列⑴是堆，而序列⑵不是堆，值为 7 的元素应该上调，调整过程见图简答题 8-5.2. 6.第一趟： [46, 58, 15, 45, 90, 18, 10, 62] [46, 58, 15, 45, 90, 18, 10, 62] . 一次交换之后 [10, 58, 15, 45, 90, 18, 46, 62] 二次交换之后 [10, 46, 15, 45, 90, 18, 58, 62] 三次交换之后 [10, 18, 15, 45, 90, 46, 58, 62] [10, 18, 15, 45, 90, 46, 58, 62] [10, 18, 15, 45, 90, 46, 58, 62] 四次交换之后 [10, 18, 15, 45, 46, 90, 58, 62] 以上“－”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。 第一趟： [10 18 15 45] 46 [90 58 62] 第二趟： 10 [18 15 45] 46 [62 58] 90 第三趟： 10 [15] 18 45] 46 [58] 62 90 结果： 10 15 18 45 46 58 62 90 7． ⑴插入排序的每趟的结果 初始值健值序列 [12] 5 9 20 6 31 24 i=2 [5 12] 9 20 6 31 24 i=3 [5 9 12] 20 6 31 24 i=4 [5 9 12 20] 6 31 24 i=5 [5 6 9 12 20] 31 24 i=6 [5 6 9 12 20 31] 24 i=7 [5 6 9 12 20 24 31]
(2)冒泡排序的每趟的结果 初始键值序列1259206 第一趟之后[591262024 第二趟之后[5961220]2431 第三趟之后[56912]20 第四趟之后5691220 五、算法设计 1分析:每趟从单链表头部开始,顺序查找当前链值最小的结点。找到后,插入到当 前的有序表区的最后。 Void selesort( lklist L) /*设链表L带头结点考 /*指向第一数据前趋* while( q-> next !=NULL i pl=q->nex minp=pl; /*minp指向当前已知的最小数* while( pl-> next I=NULL f if( pl->next->data< minp->data minp=pl->next;/*找到了更小数* pl=pl->next;/*继续往下找* if( minp=q->next)/*将最小数交换到第一个位置上* i rl= minp->next xt=r1->next;/*删除最小数 q->next=r2->next;/*删除当前表中第一个数*/ rI->next=q->next; q->next=r /*将最小数插入到第一个位置上 r2->next=minp->next minp->next=r2 /*将原第一个数放到最小数原位置上* q=q /*选择下一个最小数 2分析:先调用划分函数 quickpass O,以确定中间元素的位置,然后再借助栈分别对 间元素左、右两边的区域进行快速排序。 Void qksort( list A /*n为元素个数* i InitStack(S) /*设置一个栈保存有关参数和变量* *j,h分别指向表头和表尾* while((< h)l(empty(S))) i while(j<h) i quickpass(A j,h, i) /*划分函数 quickpass O参照教材 /*保存变量值* /*设置对左边进行划分的参数*
4 ⑵冒泡排序的每趟的结果： 初始键值序列 [12 5 9 20 6 31 24] 第一趟之后 [5 9 12 6 20 24] 31 第二趟之后 [5 9 6 12 20] 24 31 第三趟之后 [5 6 9 12] 20 24 31 第四趟之后 5 6 9 12 20 24 31 五、算法设计 1.分析：每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入到当 前的有序表区的最后。 Void selesort ( lklist L ) /* 设链表 L 带头结点 */ { q=L; /* 指向第一数据前趋 */ while ( q-> next !=NULL ) { pl = q -> next ; minp =pl; /* minp 指向当前已知的最小数 */ while ( pl -> next != NULL ) { if ( pl -> next -> data < minp -> data ) minp = pl -> next ; /* 找到了更小数 */ pl = pl -> next ; /* 继续往下找 */ } if ( minp != q -> next) /* 将最小数交换到第一个位置上 */ { r1 = minp -> next ; minp -> next = r1 -> next ; /* 删除最小数 */ r2 = q -> next ; q -> next = r2 -> next ; /* 删除当前表中第一个数 */ r1 -> next = q -> next ; q -> next = r1 ; /* 将最小数插入到第一个位置上 */ r2 -> next = minp -> next ; minp -> next = r2 ; /* 将原第一个数放到最小数原位置上 */ } q = q > next ; /* 选择下一个最小数 */ } } 2.分析：先调用划分函数 quickpass () ,以确定中间元素的位置，然后再借助栈分别对 中间元素左、右两边的区域进行快速排序。 Void qksort ( list A ) /* n 为元素个数 */ { InitStack ( S ) ; /* 设置一个栈保存有关参数和变量 */ j = 1 ; h = n ; /* j , h 分别指向表头和表尾 */ while ( ( j < h ) ‖( !empty ( S ) ) ) { while ( j < h ) { quickpass ( A,j,h,i ) ; /* 划分函数 quickpass () 参照教材 */ push ( S,j,h,i ) ; /* 保存变量值 */ h = i – 1 ; /* 设置对左边进行划分的参数 */
S i pop(Sj, h, /*取出变量值* J=1+1 /*设置对右边进行划分的参数* 3.分析:插入排序的基本思想是:每趟从无序区间中取出一个元素,再按键值大小插 入到前面的有序区间中。对于有序区,当然可以用二分查找来确定插入位置。 Void straightsort( listA /*n为元素个数,数组下标从1开始,到n结束。* {for(i=2;i<=n;i++) low=1;high=i-1;/low,high分为当前元素上、下界*/ While( low <=high i mid=( low high)/2 switch .key<=A[mid]key:high=mid-1;/*修改上界* case: A[O]. key>Amid). key: low=mid+1 修改下界* for(j=1-1: j>=mid; j-A[+l=A[jI /*移动数据* 4.分析:本题的算法思想是:先设置好上、下界,然后分别从线性表两端查找正数和负 数,找到后进行交换,直到上、下界相遇。 Void example( datatype A n)) /*i,j为左右边界* while (i<j) i while((i<j)&&(a[i]<0))i++ /*在左边界找正数* while((1<j)&&(A[j]>0)j--; /*在右边界找负数*/ {temp=A[i]A[i]=A[j];A[j]=A[temp];/交换两个元素的值 分析:此问题分为两个算法,第一个算法 shift假设a[1],a[2],…a[k为堆,增加 个无素a[k+1]把数组a[1la[2]-…,a[k+1]调整为堆。第二个算法hep从l开始调 用算法sift将整个数组调整为堆。 Void sift(datatype A[n ], int K) /n>=k+1* x=A[K+1]1; K+1 while(i2>0)&(A[i2>x){A[=A[i/2],i=i/2,}从下往上插入位置*
5 } if ( !empty ( S ) ) { pop ( S,j,h,i ) ; /* 取出变量值 */ j = i + 1 ; /* 设置对右边进行划分的参数 */ } } } 3．分析：插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插 入到前面的有序区间中。对于有序区，当然可以用二分查找来确定插入位置。 Void straightsort ( list A ) /* n 为元素个数，数组下标从 1 开始，到 n 结束。 */ { for ( i =2 ; i <= n ; i + + ) { low = 1 ; high = i – 1 ; /* low ,high 分为当前元素上、下界 */ A[0] . key = A[i] . key ; While ( low <= high ) { mid = ( low + high ) /2 ; switch { case : A[0] . key <= A[mid] . key : high = mid – 1 ; /* 修改上界 */ case : A[0] . key > A[mid] . key : low = mid + 1 ; /* 修改下界 */ } for ( j = i-1 ; j >= mid ; j - -) A [j +1] = A [ j ] ; /* 移动数据 */ A[ mid ] = A[ i ] ; } } } 4．分析：本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找正数和负 数，找到后进行交换，直到上、下界相遇。 Void example ( datatype A [n] ) { i = 1, j = n ; /* i , j 为左右边界 */ while ( i < j ) { while ( ( i < j ) && ( A[ i ] < 0 ) ) i++ ; /* 在左边界找正数 */ while ( (i < j ) && ( A[ j ] > 0 )) j - - ; /* 在右边界找负数 */ if ( i < j) { temp = A[ i ]; A[ i ] = A[ j ]; A[ j ] = A [temp ] ; /*交换两个元素的值 */ i++ ; j - -; } } } 5．分析：此问题分为两个算法，第一个算法 shift 假设 a[ 1] , a[ 2 ],…,a[ k]为堆，增加 一个无素 a[ k + 1 ],把数组 a[ 1 ],a[ 2 ], …,a[ k + 1 ]调整为堆。第二个算法 heep 从 1 开始调 用算法 sift 将整个数组调整为堆。 Void sift (datatype A[ n ] , int K) /* n > = k + 1 */ { x = A[ K+1] ; i = K +1 ; while ( ( i/2 > 0 )&&( A[i/2]>x) ) { A[i]= A[i./2]; i = i/2;} /*从下往上插入位置 */