计算机科学导论(第4版)习题答案-第5、6章.pdfVIP

第章算法与复杂性

5

习题

一、选择题

1.B2.D3.C4.A5.B

6.B7.D8.B9.C10.A

11.A12.C13.A14.A

二、简答题

1．什么是算法，算法的特性有哪些？

答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内

终止并产生结果”。算法的特性有：

有穷性可终止性：一个算法必须在有限个操作步骤内以及合理的有限时间内执行

(1)()

完成。

(2)确性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。

有效性可执行性：算法中描述的操作步骤都是可执行的，并能最终得到确的结

(3)()

果。

输入及输出：一个算法应该有零个或多个输入数据、有个或多个输出数据。

(4)1

2．什么是算法的时间复杂度和空间复杂度，如何表示？

答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花

费的时间。记为，Tn，其中，代表求解问题的规模。

()n

算法的空间复杂度(Sacecomlexity)度量算法的空间复杂性、即执行算法的程序在计算

机中运行所占用空间的大小。简单讲，空间复杂度也是与求解问题规模、算法输入相关的

函数。记为，Sn，其中，代表求解问题的规模。

()n

时间复杂度和空间复杂度同样，引入符号“O”来表示Tn、Sn与求解问题规模之

()()n

间的数量级关系。

3．用图示法表示语言处理的过程。

答：语言处理的过程如图所示：

骨架程序

预处理器

源程序编译器可重位目标文件

库

目标汇编程序汇编器

可重位机器代码装配连接编辑

绝对机器码

4．简述算法设计的策略。

答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，

而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的

算法在一台性能很强的计算机上也不一能满足应用的需要，因此，在计算机程序设计中，

算法设计往往处于核心地位。

要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。通常可以利用实

验对比分析、数学方法来分析算法。实验对比分析很简单，两个算法相互比较，它们都能

解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。在算

法设计中，通常采用能近似表达性能的方法来展示某个算法的性能指标。例如，计算机对n2

和n22n的响应速度，当n比较大的时,没什么区别，便可直接认为后者算法的复杂度为

2

n。

基于算法复杂度简化表达的思想基础上，通常会对算法进行最坏情况分析和平均情况

分析。对于一个给的算法，如果能保证它的最坏情况下的性能依然很好，但是在某些情

况下，程序的最坏情况算法的运行时间和实际情况的运行时间相差很大，在实际应用中几

乎不会碰到最坏情况下的输入，那么此时进行最坏情况分析显得有些画蛇添足，特别是分

析最坏情况算法会花费大