数据结构与算法教程 习题答案作者 朱明方 吴及 第7章习题解答.doc

《数据结构与算法教程 习题答案作者 朱明方 吴及 第7章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第7章习题解答7.1画出采用冒泡排序对字符序列ASORTINGALGORITHM进行排序的过程。[解答]ASORTINGALGORITHMAORSINGALGORITHMTAORINGALGORISHMTTAOINGALGORIRHMSTTAINGALGOOIRHMRSTTAIGALGNOIOHMRRSTTAGAIGLNIOHMORRSTTAAGGILINHMOORRSTTAAGGIILHMNOORRSTTAAGGIIHLMNOORRSTTAAGGIHILMNOORRSTTAAGGHIILMNOORRSTT7.2给出一个例子，使执行冒泡排序时，所需要执行的交换操作最多。[解答]由冒泡排序的

2、过程可知,对一个完全逆序序列进行冒泡排序时，所做的交换次数是最多的。7.3.画出采用直接插入排序对字符序列ASORTINGALGORITHM进行排序的过程。[解答]排序过程如图7-1所示。图7-17.4采用实际序列测试采用两个不同的缩小增量序列进行希尔排序的性能差异(1)hi=4i+3´2i-1+1，i≥1，h0=1;(2)hi=2i，i≥0;9注意：序列要有一定的长度。7.5对于一个长度为10000的序列，如果采用下面的缩小增量序列：hi=4i+3´2i-1+1，i≥1，h0=1；进行希尔排序，实验测试增加步长或者减小步长对性能的影响。注意：选择一个能反映一般情况的例子做。7.6画出采用

3、选择排序对字符序列ASORTINGALGORITHM进行排序的过程。[解答]ASORTINGALGORITHMASORTINGALGORITHMAAORTINGSLGORITHMAAGRTINOSLGORITHMAAGGTINOSLRORITHMAAGGHINOSLRORITTMAAGGHINOSLRORITTMAAGGHIIOSLRORNTTMAAGGHIILSORORNTTMAAGGHIILMORORNTTSAAGGHIILMNROROTTSAAGGHIILMNORROTTSAAGGHIILMNOORRTTSAAGGHIILMNOORRTTSAAGGHIILMNOORRTTSAAGGH

4、IILMNOORRSTTAAGGHIILMNOORRSTT7.7在选择排序中，最多需要进行多少次交换操作，平均次数又是多少？［解答］对规模为n的序列，最多需要进行n-1次交换，平均需要进行n-1次交换。选择排序的交换次数和序列的初始有序性无关。7.8选择排序是否稳定？请说明理由。［解答］选择排序的动态性能是不稳定的，因为选择排序中存在非相邻位置数据项的交换，这种交换可能改变两个关键字相等的元素排序之前的相对位置。7.9设计一种简单的算法，检查一个序列是否已经有序？［解答］intJ-Rnak(a[],intn)//检查表a中的元素是否有序，n表长度{inti,fiag=1;//flag=1,

5、a中的元素有序,反之，flag=09for(i=0;i<=n-1;i++)//设a中元素若有序，为非递减序if(a[i]>a[i+1]){flag=0;break;}returnflag;}7.10对于逆序的有序序列，采用哪种基本排序方法排序的时间复杂度最低？［解答］选择排序。因为选择排序中数据元素的移动次数与待排序序列的有序程度无关，即是否完全逆序不会影响数据元素交换的次数；而对于冒泡排序和插入排序来说，对完全逆序序列排序是效率最低的情况。7.11对于所有关键字都相同的序列，采用哪一种基本排序方法(冒泡排序，直接插入排序和直接选择排序)，运行得最快？［解答］对于所有关键字都相同的序列进行

6、排序，采用冒泡排序比直接插入排序和选择排序效率高。因为对于这种情况冒泡排序只需相邻元素进行一趟比较，即n-1次比较操作；而直接插入排序除了有n-1次比较操作外，还有元素的移动操作，选择排序则需要进行n(n-1)/2次比较操作。7.12对于锦标赛排序，在最坏情况下，对于规模为N的待排序序列，最坏情况下需要多少辅助空间？[解答]最坏情况下，当N=2k－1＋1，k足够大时，大约需要3N的辅助空间。7.13对于关键字序列{503，087，512，061，908，170，897，275，653，426}，分别采用以下排序算法，请给出每一步的序列状态：(1)直接插入排序；(2)快速排序；(3)堆排序；

7、(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，061，908，170，897，275，653，426，061，087，503，512，908，170，897，275，653，426，061，087，503，512，908，170，89