算法设计与分析C语言描述陈慧南版课后答案VIP专享

第一章1-3. 最大公约数为 1。快 1414 倍。重要考虑循环次数，程序 1-2 的 while 循环体做了 10 次，程序 1-3 的 while 循环体做了 14141 次（14142-2 循环）若考虑其他语句，则没有这么多，也许就 601 倍。第二章2-8.（1）画线语句的执行次数为。。划线语句的执行次数应当理解为一格整体。（2）画线语句的执行次数为 。。（3）画线语句的执行次数为 。。（4）当 n 为奇数时画线语句的执行次数为 ，当 n 为偶数时画线语句的执行次数为 。。 2-10. （ 1 ） 当 时 ，， 所 以 ， 可 选 ，。 对 于，，所以，。（2） 当 时，，所以，可选 ，。对于，，所以，。（3） 由（1）、（2）可知，取，，，当时，有，所以。2-11. (1) 当时，，所以，。可选 ，。对于，，即。注意：是 f(n)和 g(n)的关系。（2） 当 时，，所以 ，。可选 ，。对于 ，，即 。（3）由于 ，。当 时，，。所以，可选 ，，对于，，即 。第二章2-17. 证明：设，则 。 当 时，。所以，。第五章5-4. SolutionType DandC1(int left,int right){while(!Small(left,right)&&leftP[m]) left=m+1; else return S(P) }}5-7. template int SortableList::BSearch(const T&x,int left,int right) const{if (left<=right){int m=(right+left)/3;if (xl[m]) return BSearch(x,m+1,right);else return m;}return -1;}第五章9． 证明：由于该算法在成功搜索的情况下，关键字之间的比较次数至少为，至多为。在不成功搜索的情况下，关键字之间的比较次数至少为，至多为。所以，算法的最佳、最坏情况的时间复杂度为。假定查找表中任何一个元素的概率是相等的，为，那么，不成功搜索的平均时间复杂度为，成功搜索的平均时间复杂度为。其中，是二叉鉴定树的内途径长度，是外途径长度，并且。11.步数012345初始时111111[11]1[11]∞2[1]11[11]∞3111[11]∞4111[1]1∞排序结果11111∞步数01234567初始时5583432∞1[4233]5[85]∞2[323]45[85]∞3[32]345[85]∞4[2]3345[85]∞523345[5]8∞排序结果2334558∞12.（1）证明：当或或时，程序显然对的。当 n=right-left+1>2 时，程序执行下面的语句：int k=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);S...