算法设计与分析课后答案 田翠华著

《算法设计与分析课后答案 田翠华著》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、参考答案127参考答案第1章一、选择题1.C2.A3.C4.CADB5.B6.B7.D8.B9.B10.B11.D12.B二、填空题1.输入；输出；确定性；可行性；有穷性2.程序；有穷性3.算法复杂度4.时间复杂度；空间复杂度5.正确性；简明性；高效性；最优性6.精确算法；启发式算法7.复杂性尽可能低的算法；其中复杂性最低者8.最好性态；最坏性态；平均性态9.基本运算10.原地工作三、简答题1.高级程序设计语言的主要好处是：参考答案127（l）高级语言更接近算法语言，易学、易掌握，一般工程技术人员

2、只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好、重用率高；（4）把复杂琐碎的事务交给编译程序，所以自动化程度高，发用周期短，程序员可以集中集中时间和精力从事更重要的创造性劳动，提高程序质量。2.使用抽象数据类型带给算法设计的好处主要有：（1）算法顶层设计与底层实现分离，使得在进行顶层设计时不考虑它所用到的数据

3、，运算表示和实现；反过来，在表示数据和实现底层运算时，只要定义清楚抽象数据类型而不必考虑在什么场合引用它。这样做使算法设计的复杂性降低了，条理性增强了，既有助于迅速开发出程序原型，又使开发过程少出差错，程序可靠性高。（2）算法设计与数据结构设计隔开，允许数据结构自由选择，从中比较，优化算法效率。参考答案127（3）数据模型和该模型上的运算统一在抽象数据类型中，反映它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，灵活地满足用户要求。（4）由于顶层设计和底层实现局部化，在设计中出现的

4、差错也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、删、改也都是局部的，因而也都容易进行。因此，用抽象数据类型表述的算法具有很好的可维护性。（5）算法自然呈现模块化，抽象数据类型的表示和实现可以封装，便于移植和重用。（6）为自顶向下逐步求精和模块化提供有效途径和工具。（7）算法结构清晰，层次分明，便于算法正确的证明和复杂性的分析。3.算法的复杂度是算法运行所需要的计算机资源的量。4.当问题的规模递增时，将复杂度的极限称为渐进复杂度。5.采用复杂性渐近性态替代算法复杂度，使得在数量级上估计

5、一个算法的执行时间成为可能。四、计算题1.验证下面的关系：O（1）

6、f(n)

7、=

8、O(g(n))

9、定义，可知一定存在两个正的常数C和n0，使得对所有的n≥n0，有f(n)≤Cg(n)。那么，就有f1(n)≤C1

10、，f2(n)≤C2logn，f3(n)≤C3n，f4(n)≤C4nlogn，f5(n)≤C5n2。所以，O(g(n))之间的比较可以通过f(n)之间的比较得以实现。而当n≥n0时，C1

11、(n2)。同理，有：O(2n)

12、集合操作，上界的并取最大者3.求以下各式的渐进表达式:5n2+8n，3n2/11+3n，56+3/n，logn5，6log4n。解答：5n2+8n=O(n2);1参考答案1273n2/11+3n=O(3n);56+3/n=O（1）//O（1）表示常数;logn5=O(logn)；6log4n=O(n)。4.按照渐进阶从低到高的顺序排列下列表达式：n2，logn，3n，45n，6，3n3/2，n！。解答：logn，45n，3n3/2，5n2，3n，n！。5.确定关系：对于下列各组函数