2025年严飞_《软件技术基础》沈被娜习题解答.pdfVIP

太上有立德，其次有立功，其次有立言，虽久不废，此谓不朽。——《左传》

第二章

2.1什么是数据结构？它对算法有什么影响？

数据结构是指同一数据对象中各数据元素间存在的关系。

数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据

类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结

构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的

基本部分，它对程序的质量影响很大。

2.2何谓算法？它与程序有何区别？

广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机

算法是通过计算机能执行的算法语言来表达的。

和程序的区别：一个程序包括两个方面的内容：

（1）对数据的描述，即数据结构。

（2）对操作的描述，即算法。

所以算法是程序的一个要素。

2.3何谓频度，时间复杂度，空间复杂度？说明其含义。

频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。

时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的

语句来度量。

空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数

据占用的空间。

2.4试编写一个求多项式Pn=anxn+an-1xn-1+a1x+a0的值Pn(x0)的算法，要求

用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。

A=(a,a……a)

01n

mul＝1//

sum=a

0

fori=1ton

mul＝mul*x//x

sum=A[i]*mul+sum//求和

end(i)

进行了n次

时间复杂度为：2n

2.5计算下列各片段程序中X←X+1执行次数

(1)

fori=1ton

forj=1toi

fork=1toj

x←x+1

end(k)

end(j)

end(i)

执行次数：n*n*n

老当益壮，宁移白首之心；穷且益坚，不坠青云之志。——唐·王勃

(2)

i←1

whileindo

x←x+1

i←i+1

end(while)

执行次数：n-1

(3)

fori=1ton

j←1

fork=j+1ton

x←x+1

end(k)

end(i)

执行次数：n*（n-1）

2.6数据的存储结构主要有哪两种?它们之间的本质区别是什么？

数据的存储结构：向量和链表。

本质区别：

向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前

后件的关系。

链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储

空间中，其元素关系由指针来指向。

其身正，不令而行；其身不正，虽令不从。——《论语》