第二章 2.1 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间存在的关系。 数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 2.2 何谓算法？它与程序有何区别？ 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容： （1）对数据的描述，即数据结构。 （2）对操作的描述，即算法。 所以算法是程序的一个要素。 2.3 何谓频度，时间复杂度，空间复杂度？说明其含义。 频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。 空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。 2.4 试编写一个求多项式 Pn =anxn +an-1 xn-1+a1x+a0 的值Pn(x 0)的算法，要求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。 A=(a0, a1 … … an) mul ＝ 1 // sum=a0 for i=1 to n mul ＝ mul * x // x sum = A[i]*mul + sum //求和 end(i) 进行了n 次 时间复杂度为：2n 2.5 计算下列各片段程序中 X←X+1 执行次数 (1) for i=1 to n for j=1 to i for k=1 to j x←x+1 end(k) end(j) end(i) 执行次数：n*n*n (2) i←1 while i
