《数据结构与算法教程 习题答案作者 朱明方 吴及 第7章习题解答》由会员分享，可在线阅读，更多相关《数据结构与算法教程 习题答案作者 朱明方 吴及 第7章习题解答（9页珍藏版）》请在金锄头文库上搜索。
1、第7章习题解答7.1 画出采用冒泡排序对字符序列A S O R T I N G A L G O R I T H M进行排序的过程。解答A S O R T I N G A L G O R I T H MA O R S I N G A L G O R I T H M TA O R I N G A L G O R I S H M T TA O I N G A L G O R I R H M S T TA I N G A L G O O I R H M R S T TA I G A L G N O I O H M R R S T TA G A I G L N I O H M O R R S T TA
2、A G G I L I N H M O O R R S T TA A G G I I L H M N O O R R S T TA A G G I I H L M N O O R R S T TA A G G I H I L M N O O R R S T TA A G G H I I L M N O O R R S T T7.2 给出一个例子，使执行冒泡排序时，所需要执行的交换操作最多。解答由冒泡排序的过程可知,对一个完全逆序序列进行冒泡排序时，所做的交换次数是最多的。7.3. 画出采用直接插入排序对字符序列A S O R T I N G A L G O R I T H M进行排序的过程。解
3、答排序过程如图7-1所示。图7-17.4 采用实际序列测试采用两个不同的缩小增量序列进行希尔排序的性能差异(1) hi = 4i+32i-1+1，i1，h0=1;(2) hi = 2i，i0;注意：序列要有一定的长度。7.5 对于一个长度为10000的序列，如果采用下面的缩小增量序列：hi = 4i+32i-1+1，i1，h0=1；进行希尔排序，实验测试增加步长或者减小步长对性能的影响。 注意：选择一个能反映一般情况的例子做。7.6 画出采用选择排序对字符序列A S O R T I N G A L G O R I T H M进行排序的过程。 解答 A S O R T I N G A L G O
4、 R I T H MA S O R T I N G A L G O R I T H MA A O R T I N G S L G O R I T H MA A G R T I N O S L G O R I T H MA A G G T I N O S L R O R I T H MA A G G H I N O S L R O R I T T MA A G G H I N O S L R O R I T T MA A G G H I I O S L R O R N T T MA A G G H I I L S O R O R N T T MA A G G H I I L M O R O R
5、N T T S A A G G H I I L M N R O R O T T S A A G G H I I L M N O R R O T T SA A G G H I I L M N O O R R T T SA A G G H I I L M N O O R R T T SA A G G H I I L M N O O R R T T SA A G G H I I L M N O O R R S T T A A G G H I I L M N O O R R S T T 7.7 在选择排序中，最多需要进行多少次交换操作，平均次数又是多少？解答对规模为n的序列，最多需要进行n-1次交换，
6、平均需要进行n-1次交换。选择排序的交换次数和序列的初始有序性无关。7.8 选择排序是否稳定？请说明理由。解答选择排序的动态性能是不稳定的，因为选择排序中存在非相邻位置数据项的交换，这种交换可能改变两个关键字相等的元素排序之前的相对位置。7.9 设计一种简单的算法，检查一个序列是否已经有序？解答int J-Rnak(a, int n) / 检查表a中的元素是否有序，n表长度 int i, fiag=1 ; / flag=1, a中的元素有序,反之，flag=0 for(i=0; iai+1) flag=0 ; break ; return flag ; 7.10 对于逆序的有序序列，采用哪种基
7、本排序方法排序的时间复杂度最低？解答选择排序。因为选择排序中数据元素的移动次数与待排序序列的有序程度无关，即是否完全逆序不会影响数据元素交换的次数；而对于冒泡排序和插入排序来说，对完全逆序序列排序是效率最低的情况。7.11 对于所有关键字都相同的序列，采用哪一种基本排序方法(冒泡排序，直接插入排序和直接选择排序)，运行得最快？解答 对于所有关键字都相同的序列进行排序，采用冒泡排序比直接插入排序和选择排序效率高。因为对于这种情况冒泡排序只需相邻元素进行一趟比较，即n-1次比较操作；而直接插入排序除了有n-1次比较操作外，还有元素的移动操作， 选择排序则需要进行n(n-1)/2次比较操作。7.12
8、 对于锦标赛排序，在最坏情况下，对于规模为N的待排序序列，最坏情况下需要多少辅助空间？解答最坏情况下，当N=2k11，k足够大时，大约需要3N的辅助空间。7.13 对于关键字序列503，087，512，061，908，170，897，275，653，426，分别采用以下排序算法，请给出每一步的序列状态：(1) 直接插入排序；(2) 快速排序；(3) 堆排序；(4) 自底向上的归并排序。解答(1) 直接插入排序 503，087，512，061，908，170，897，275，653，426，087，503，512，061，908，170，897，275，653，426，087，503，512，0
9、61，908，170，897，275，653，426，061，087，503，512，908，170，897，275，653，426，061，087，503，512，908，170，897，275，653，426，061，087，170，503，512，908，897，275，653，426，061，087，170，503，512，897，908，275，653，426，061，087，170，275，503，512，897，908，653，426，061，087，170，275，503，512，653，897，908，426，061，087，170，275，426，503，512，653，8
10、97，908， (2) 快速排序503，087，512，061，908，170，897，275，653，426275，087，170，061，426，512，897，503，653，908061，087，170，275，426，512，897，503，653，908061，087，170，275，426，512，503，653，897，908061，087，170，275，426，512，503，653，897，908061，087，170，275，426，503，512，653，897，908(3) 堆排序503，087，512，061，908，170，897，275，653，426908，
11、653，897，503，426，170，512，275，061，087897，653，512，503，426，170，087，275，061，908653，503，512，275，426，170，087，061，897，908512，503，170，275，426，061，087，653，897，908503，426，170，275，087，061，512，653，897，908426，275，170，061，087，503，512，653，897，908275，087，170，061，426，503，512，653，897，908170，087，061，275，426，503，512，653
12、，897，908087，061，170，275，426，503，512，653，897，908061，087，170，275，426，503，512，653，897，908(4) 自底向上的归并排序503，087，512，061，908，170，897，275，653，426087，503，061，512，170，908，275，897，426，653061，087，503，512，170，275，897，908，426，653061，087，170，275，503，512，897，908，426，653061，087，170，275，426，503，512，653，897，9087.14 在
13、冒泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？解答如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如，图7-2中的情况。 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向相反方向移动
14、 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 图7-27.15 在快速排序过程中，可以采用对规模小于M的序列调用直接插入排序来改进其性能。请通过实验研究，M的选择对改进快速排序性能的影响。解答随着M的增加，排序性能先提高后降低。当M较小时，使用直接插入排序可以降低快速排序在短序列时递归的次数，使性能提高；而当M较大时，直接插入排序本身需要消耗较多的时间，使性能降低。设计适当的例子进行测试。7.16 基于链表，是否可以实现快速排序？如能，写出实现的方法。算法提示 在每一次递归时，选取某一个元素（如子序列的第一个元素）作为划分元素，将其余的元素逐个与之比较。如果小于划分元素，则把结点插入到划分元素结点之前；否则插入到划分元素结点之后。
