算法设计与分析-课后习题集答案.doc
文本预览下载声明
第一章
3. 最大公约数为1。快1414倍。
程序1-2的while循环体做了10次，程序1-3的while循环体做了14141次（14142-2循环）
8.（1）画线语句的执行次数为。。
（2）画线语句的执行次数为 。。
（3）画线语句的执行次数为 。。
（4）当n为奇数时画线语句的执行次数为 ，
当n为偶数时画线语句的执行次数为 。。
10.（1） 当 时，，所以，可选 ，。对于，，所以，。
（2） 当 时，，所以，可选 ，。对于，，所以，。
（3） 由（1）、（2）可知，取，，，当时，有，所以。
11. (1) 当时，，所以，。可选 ，。对于，，即。
（2） 当 时，，所以 ，。可选 ，。对于 ，，即 。
（3）因为 ，。当 时，，。所以，可选 ，，对于，，即 。
第二章
2-17. 证明：设，则 。
当 时，。所以，。
第五章
5-4. SolutionType DandC1(int left,int right)
{ while(!Small(left,right)leftright)
{ int m=Divide(left,right);
if(xP(m) right=m-1;
else if(xP[m]) left=m+1;
else return S(P)
}
}
5-7. template class T
int SortableListT::BSearch(const Tx,int left,int right) const
{ if (left=right)
{ int m=left+(right-left+1)/3;
if (xl[m]) return BSearch(x,left,m-1);
else if (xl[m]) return BSearch(x,m+1,right);
else return m;
}
return -1;
}
7．m=left+(right-left+1)/3
不能用：m=(left+right)/3 ，两者不同。
受对半搜索的影响：m=(left+right)/2和m=left+(right-left+1)/2是一样的
9．
证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为，至多为。在不成功搜索的情况下，关键字之间的比较次数至少为，至多为。所以，算法的最好、最坏情况的时间复杂度为。
假定查找表中任何一个元素的概率是相等的，为，那么，
不成功搜索的平均时间复杂度为，
成功搜索的平均时间复杂度为。
其中，是二叉判定树的内路径长度，是外路径长度，并且。
11.
步数 0 1 2 3 4 5 初始时 1 1 1 1 1 1 [1 1] 1 [1 1] ∞ 2 [1] 1 1 [1 1] ∞ 3 1 1 1 [1 1] ∞ 4 1 1 1 [1] 1 ∞ 排序结果 1 1 1 1 1 ∞
步数 0 1 2 3 4 5 6 7 初始时 5 5 8 3 4 3 2 ∞ 1 [4 2 3 3] 5 [8 5] ∞ 2 [3 2 3] 4 5 [8 5] ∞ 3 [3 2] 3 4 5 [8 5] ∞ 4 [2] 3 3 4 5 [8 5] ∞ 5 2 3 3 4 5 [5] 8 ∞ 排序结果 2 3 3 4 5 5 8 ∞
12.（1）证明：当或或时，程序显然正确。
当n=right-left+12时，程序执行下面的语句：
int k=(right-left+1)/3;
StoogeSort(left,right-k);
StoogeSort(left+k,right);
StoogeSort(left,right-k);
①首次递归StoogeSort(left,right-k);时，序列的前2/3的子序列有序。
②当递归执行StoogeSort(left+k,right);时，使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。
③再次执行StoogeSort(left,right-k);使序列的前2/3有序。
经过三次递归，最终使序列有序。
所
显示全部