数据结构题集(C语言版)算法设计题答案[1].doc

第一章绪论
1.16
voidprint_descending(intx,inty,intz)//
按从大到小顺序输出三个数
{
scanf("%d,%d,%d",&x,&y,&z);
if(x<y)x<->y;//<->为表示交换的双目运算符,以下同
if(y<z)y<->z;
if(x<y)x<->y;//冒泡排序
printf("%d%d%d",x,y,z);
}//print_descending
1.17
Statusfib(intk,intm,int&f)//求k阶斐波那契序列的第m项的值f
{
inttempd;
if(k<2||m<0)returnERROR;
if(m<k-1)f=0;
elseif(m==k-1)f=1;
else
{
for(i=0;i<=k-2;i++)temp[i]=0;
temp[k-1]=1;//初始化
for(i=k;i<=m;i++)//求出序列第k至第m个元素的值
{
sum=0;
for(j=i-k;j<i;j++)sum+=temp[j];
temp[i]=sum;
}
f=temp[m];
}
returnOK;
}//fib
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).
1.18
typedefstruct{
char*sport;
enum{male,female}
gender;
charschoolname;//校名为'A','B','C','D'或'E'
char*result;
intscore;
}resulttype;
typedefstruct{
intmalescore;
intfemalescore;
inttotalscore;
}scoretype;
voidsummary(resulttyperesult[])//求各校的男女总分和团体总分,假设结果已经储存在result[]数组中
{
scoretypescore;
i=0;
while(result[i].sport!=NULL)
{
switch(result[i].schoolname)
{
case'A':
score[0].totalscore+=result[i].score;
if(result[i].gender==0)score[0].malescore+=result[i].score;
elsescore[0].femalescore+=result[i].score;
break;
case'B':score.totalscore+=result[i].score;
if(result[i].gender==0)score.malescore+=result[i].score;
elsescore.femalescore+=result[i].score;
break;
………………
}
i++；
}
for(i=0;i<5;i++)
{
printf("School%d:\n",i);
printf("Totalscoreofmale:%d\n",score[i].malescore);
printf("Totalscoreoffemale:%d\n",score[i].femalescore);
printf("Totalscoreofall:%d\n\n",score[i].totalscore);
}
}//summary
1.19
Statusalgo119(inta[ARRSIZE])//求i!*2^i序列的值且不超过maxint
{
last=1;
for(i=1;i<=ARRSIZE;i++)
{
a[i-1]=last*2*i;
if((a[i-1]/last)!=(2*i))reurnOVERFLOW;
last=a[i-1];
returnOK;
}
}//algo119
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.
1.20
voidpolyvalue()
{
floatad;
float*p=a;
printf("Inputnumberofterms:");
scanf("%d",&n);
printf("Inputthe%dcoefficientsfroma0toa%d:\n",n,n);
for(i=0;i<=n;i++)scanf("%f",p++);
printf("Inputvalueofx:");
scanf("%f",&x);
p=a;xp=1;sum=0;//xp用于存放x的i次方
for(i=0;i<=n;i++)
{
sum+=xp*(*p++);
xp*=x;
}
print