第01章习题答案

《第01章习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？答：数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。【严题集1.3②】设有数据结构（D,R），其中D={d1,d2,d3,d4}，R={r}，r={(d1,d2),(d2,d3),(d3,d4)}试按图论中图的画法惯例画出其逻辑结构图。d1Æd2Æd3Æd4【严题集1.8④】分析下面各程序段的时间复杂度.设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0;while(i

2、k=k+10*i;//n-1(2)i=1;k=0;do{k=k+10*i;i++;}while(i<=n-1);分析：k=k+10*i;//n-1(3)n-1(4)f(n)=n+(n-1)+(n-2)+…+1=(n+1)n/2n(5)f(n)=1+(1+2)+(1+2)+3+…+(1+2+3+…+n)=∑(1ii+)*/2i=1(6)i=1;j=0;while(i+j<=n){if(i>j)j++;elsei++;}分析：通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该

3、程序段的执行时间为：f(n)=n(7)x=n;y=0;//n>1while(x>=(y+1)*(y+1))y++;分析：由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)0)if(x>100){x=x-10;y--;}1elsex++;分析：x=91;//1y=100;//1while(y>0)//1101if(x>100)//1100{x=x-10;/

4、/100y--;//100}elsex++;//1000以上程序段右侧列出了执行次数。【严题集1.17③】求k阶斐波那契序列的第m项的值f方法1：Statusfib(intk,intm,int&f)//求k阶斐波那契序列的第m项的值f{inttemp[m];if(k<2

5、

6、m<0)returnERROR;if(m

7、

8、m==k)f=1;else{for(i=0;i<=k-2;i++)temp[i]=0;temp[k-1]=1;temp[k]=1;//初始化sum=1;j=0;for(i=k+1;i<=m;i++,j++)//求出序列第k至第m个

9、元素的值temp[i]=2*sum-temp[j];f=temp[m];}returnOK;}//fib分析:k阶斐波那契序列的第m项的值f[m]=f[m-1]+f[m-2]+......+f[m-k]=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]=2*f[m-1]-f[m-k-1]所以上述算法的时间复杂度仅为O(m).如果采用递归设计,将达到O(k^m).即使采用暂存中间结果的方法,也将达到O(m^2).2方法2：longfib(longn,longk){if(n

10、

11、(n==k))r

12、eturn1;elsereturn2*fib((n-1),k)-fib((n-k-1),k);}分析:采用递归设计,时间复杂度达到O(k^m).方法3：Statusfib(intk,intm,int&f)//求k阶斐波那契序列的第m项的值f{inttemp[m];if(k<2

13、

14、m<0)returnERROR;if(m

15、sum+=temp[j];temp[i]=sum;}f=temp[m];}returnOK;}//fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).【严题集1.20④】编写算法求一元多项式#include#include#defineN5voidmain(){inta[N];//系数数组intn,i,x,xp;printf("Inputthe%dcoefficientsfroma0to