数据结构教程李春葆课后答案第10章内排序.pdf

《数据结构教程李春葆课后答案第10章内排序.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第10章内排序教材中练习题及参考答案1.直接插入排序算法在含有n个元素的初始数据正序、反序和数据全部相等时，时间复杂度各是多少？答：含有n个元素的初始数据正序时，直接插入排序算法的时间复杂度为O(n)。2含有n个元素的初始数据反序时，直接插入排序算法的时间复杂度为O(n)。含有n个元素的初始数据全部相等时，直接插入排序算法的时间复杂度为O(n)。2.回答以下关于直接插入排序和折半插入排序的问题：（1）使用折半插入排序所要进行的关键字比较次数，是否与待排序的元素的初始状态有关？（2）在一些特殊情况下，折

2、半插入排序比直接插入排序要执行更多的关键字比较，这句话对吗？答：（1）使用折半插入排序所要进行的关键字比较次数，与待排序的元素的初始状态无关。无论待排序序列是否有序，已形成的部分子序列是有序的。折半插入排序首先查找插入位置，插入位置是判定树失败的位置（对应外部节点），失败位置只能在判定树的最下两层上。（2）一些特殊情况下，折半插入排序的确比直接插入排序需要更多的关键字比较，例如，在待排序序列正序的情况下便是如此。3.有以下关于排序的算法：voidfun(inta[],intn){inti,j,d,tm

3、p;d=n/3;while(true){for(i=d;i=0&&tmp

4、量递减为1/3的希尔排序方法对a数组中元素进行递增排序。（2）当a[]={5，1，3，6，2，7，4，8}时，执行fun(a，8)的过程如下：d=2：21364758d=1：12345678共有两趟排序。4.在实现快速排序的非递归算法时，可根据基准元素，将待排序序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。答：由快速排序的算法可知，所需递归工作栈的深度取决于所需划分的最大次数。在排序过程中每次划分都把整个待排序序列根据基准元素划

5、分为左、右两个子序列，然后对这两个子序列进行类似的处理。设S(n)为对n个记录进行快速排序时平均所需栈的深度，则：nn112S(n)=(S(k1)S(nk))S(i)nnk1i0当n=1时，所需栈空间为常量，由此可推出：S(n)=O(log2n)。实际上，在快速排序中下一趟首先对较短子序列排序，并不会改变所需栈的深度，所以所需栈的深度仍为O(log2n)。5.将快速排序算法改为非递归算法时通常使用一个栈，若把栈换为队列会对最终排序结果有什么影响？答：在执行快速排序算法时，用栈保存每趟

6、快速排序划分后左、右子区间的首、尾地址，其目的是为了在处理子区间时能够知道其范围，这样才能对该子区间进行排序，但这与处理子区间的先后顺序没什么关系，而仅仅起存储作用（因为左、右子区间的处理是独立的）。因此，用队列同样可以存储子区间的首、尾地址，即可以取代栈的作用。在执行快速排序算法时，把栈换为队列对最终排序结果不会产生任何影响。6.在堆排序、快速排序和二路归并排序中：（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？（2）若只从排序结果的稳定性考虑，则应选

7、取哪种排序方法？（3）若只从最坏情况下的排序时间考虑，则不应选取哪种排序方法？答：（1）若只从存储空间考虑，则应首先选取堆排序（空间复杂度为O(1)），其次选取快速排序（空间复杂度为O(log2n)），最后选取二路归并排序（空间复杂度为O(n)）。（2）若只从排序结果的稳定性考虑，则应选取二路归并排序，其他两种排序方法是不第10章内排序3稳定的。（3）若只从最坏情况下的排序时间考虑，则不应选取快速排序方法。因为快速排序方2法最坏情况下的时间复杂度为O(n)，其他两种排序方法在最坏情况下的时间复杂度为O

8、(nlog2n)。7.如果只想在一个有n个元素的任意序列中得到其中最小的第k（k<