第 1

    

章 绪 论

2.(1)×(2)×(3)√
3.（1）A（2）C（3）C
5.计算下列程序中 x=x+1 的语句频度
  for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

   for(k=1;k<=j;k++)

     x=x+1;

 【解答】x=x+1 的语句频度为：

T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6

6.

 

编写算法，求 一元多项式 p

n

(x)=a

0

+a

1

x+a

2

x

2

+…….+a

n

x

n

的值 p

n

(x

0

),并确定算法中每一

语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能

使用求幂函数。注意：本题中的输入为 a

i

(i=0,1,…n)、x 和 n,输出为 P

n

(x

0

)

 

。算法的输入和输

出采用下列方法

（1）通过参数表中的参数显式传递

（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种

实现输入输出。

【解答】

（1）通过参数表中的参数显式传递
     优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通

用性强，移置性强。

     缺点：形参须与实参对应，且返回值数量有限。

（2）通过全局变量隐式传递

 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗

 缺点：函数通用性降低，移植性差

算法如下：通过全局变量隐式传递参数

PolyValue()

{ int i,n;

float x,a[],p;

  printf(“\nn=”);

  scanf(“%f”,&n);

  printf(“\nx=”);

  scanf(“%f”,&x);

for(i=0;i<n;i++)

  scanf(“%f ”,&a[i]);    /*执行次数：n

 

次 */

      p=a[0];

      for(i=1;i<=n;i++)

{  p=p+a[i]*x;          /*执行次数：n 次*/

     x=x*x;}

printf(“%f”,p);

  }

算法的时间复杂度：T(n)=O(n)

通过参数表中的参数显式传递
float  PolyValue(float  a[ ],  float  x,  int  n)

 {

float p,s;

int i;
p=x;  

s=a[0];
for(i=1;i<=n;i++)

{s=s+a[i]*p;            /*执行次数:n 次*/ 

1