文档来源为从网络收集整理word版本可编辑欢迎下载支持
《算法分析与设计》作业参考答案
作业一
一、名词解释：1递归算法：直接或间接地调用自身的算法称为递归算法。2程序：程序是算法用某种程序设计语言的具体实现。二、简答题：1算法需要满足哪些性质？简述之。
算法是若干指令的有穷序列，满足性质：1）输入：有零个或多个外部量作为算法的输入。2）输出：算法产生至少一个量作为输出。3）确定性：组成算法的每条指令清晰、无歧义。4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。2简要分析分治法能解决的问题具有的特征。分析分治法能解决的问题主要具有如下特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。3简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只
不过人工做了本来由编译器做的事情，优化效果不明显。2）用递推来实现递归函数。3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，但其适用范围有限。三、算法编写及算法应用分析题：1冒泡排序算法的基本运算如下：
fori←1to
1doforj←1to
idoifajaj1the
交换aj、aj1；
分析该算法的时间复杂性。解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与
的关系。1）设比较一次花时间1；

i
2）内循环次数为：
i次（i1…
），花时间为：1
i
3）外循环次数为：
1，花时间为：
T

j1

i



1
2设计一个分治算法计算一棵二叉树的高度。
i1
2
解答：
算法思想：对于二叉树T，若为空树，则其高度为0；否则，分别求其左子树和右子树
的高度，最大者加1即为树T的高度。其描述如下：
i
tBTLe
gthBTT
为了便于描述，假定二叉树类型为BT。T的左子树为Tlchild，右子树为Trchild。

1文档来源为从网络收集整理word版本可编辑欢迎下载支持
f文档来源为从网络收集整理word版本可编辑欢迎下载支持ifTNULLretur
0T为空树retur
maxBTLe
gthTlchildBTLe
gthTrchildr