严蔚敏++数据结构习题集答案(10)

6

左子序列递归深度为1，右子序列递归深度为3。 (5) 直接选择排序

初始排列 0 1 i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8

[ 12 2 2 2 2 2 2 2 2 2

2 [ 12 6 6 6 6 6

2 16 16 10 10 10 10 10

3 30 30 30 12 12 12 12 12

4 28 28 28 [ 28 16 16 16 16 16

5 10 10 10 16 16 [ 28 16* 16* 16* 16*

6 16* 16* 16* 16* 16* 16* [ 28 18 16 16

7 20 20 20 20 20 20 20 [ 20 20 20

8 6 6 12 12 30 30 30 30 [ 30 28

9 18 ] 18 ] 18 ] 18 ] 18 ] 18 ] 18 ] 28 ] 28 ] 排序码比较次数 9 8 7 6 5 4 3 2 1

6 [ 16

6 10 [ 30 28 6 10 12

[ 30 ]

(6)基数排序

12 2 16 30 28 10 16* 20 6 18

按最低位分配

r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9]

20 6

2 18 10 16* 12 16 28 30 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]

收集 30 28 10 20 12 2 16 16* 6 18

按最高位分配 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] 18 * 16 16

6 2

2

12 10 28 20 30 10

12

16

18

20

28

30 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]

6

16* 收集

(7) 堆排序

第一步，形成初始的最大堆 (略)，第二步，做堆排序。

12 30 12

2 16 28 16 28 16 **30 28 10 16 20 18 10 16 20 18 10 16*

2 6 12 2 6 30 20 6 18 初始排列，不是最大堆 形成初始最大堆 交换0# 与9# 对象 20 28 6 18 16 20 16 20 16 **12 6 10 16* 12 18 10 16 12 18 10 16 2 28 30 2 6 30 2 28 30 从0# 到8# 重新形成堆 交换0# 与8# 对象 从0# 到 7# 重新形成堆

16* 2 18

12 16 18 16 12 16 **2 6 10 18 12 6 10 16 2 6 10 16

20 28 30 20 28 30 20 28 30 交换0# 与7# 对象 从0# 到6# 重新形成堆 交换0# 与6# 对象

16* 10 16

12 16 12 16 12 10 **2 6 2 6 16 18 2 6 16 18 10 18

20 28 30 20 28 30 20 28 30

从0# 到5# 重新形成堆 交换0# 与5# 对象 从0# 到4# 重新形成堆

2 6 12

12 10 6 10 6 10 2 16 16 18 * 2 16 16 18 * 12 16 16 18 * 20 28 30 20 28 30 20 28 30

交换0# 与4# 对象 从0# 到3# 重新形成堆 交换0# 与3# 对象

2 6 10

6 10 2 10 6 2 ***12 16 12 16 12 16 16 18 16 18 16 18

20 28 30 20 28 30 20 28 30

从0# 到2# 重新形成堆 交换0# 与2# 对象 从0# 到1# 重新形成堆

2 2

6 10 6 10

** 12 16 12 16 16 18 16 18 20 28 30 20 28 30 0# 0# 到 交换与1# 对象 从1# 重新形成堆，得到结果

(8) 二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去，最后得到长度为n的归并结果。

12 2 16 30 28 10 16* 20 6 18

排序码比较5次

2 12 16 30 10 28 6 18 16* 20

12 排序码比较6次 *2 12 16 30 10 16 20 28 6 18

排序码比较7次

* 2 10 12 16 16 20 28 30 6 18

排序码比较9次

* 2 6 10 12 16 16 18 20 28 30

9-3 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如，

57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75

9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把排序码最大的对象放到序列的最后，第二趟把排序码最小的对象放到序列的最前面。如此反复进行。 【解答1】

template void dataList :: shaker_Sort ( ) {

//奇数趟对表Vector从前向后, 比较相邻的排序码, 遇到逆序即交换, 直到把参加比较排序码序列 //中最大的排序码移到序列尾部。偶数趟从后向前, 比较相邻的排序码, 遇到逆序即交换, 直到把 //参加比较排序码序列中最小的排序码移到序列前端。

int i = 1, j; int exchange; while ( i < CurrentSize ) {

exchange = 0;

//起泡排序趟数不超过n-1 //假定元素未交换 //逆向起泡 //发生逆序

//交换, 最小排序码放在Vector[i-1]处 //做“发生了交换”标志 ////当exchange为0则停止排序 //正向起泡 //发生逆序

//交换, 最大排序码放在Vector[n-i]处 //做“发生了交换”标志 //当exchange为0则停止排序

for ( j = CurrentSize-i; j >= i; j-- ) if ( Vector[j-1] > Vector[j] ) { }

if ( exchange == 0 ) break;

exchange = 1;

Swap ( Vector[j-1], Vector[j] );

for ( j = i; j <= CurrentSize-i-1; j++ ) if ( Vector[j] > Vector[j+1] ) { }

if ( …… 此处隐藏：3121字，全部文档内容请下载后查看。喜欢就下载吧 ……