数据结构课后习题解答第一章 绪论

第一章绪论

1.1 试写一个算法，自大到小依次输出顺序读入的三个数X、Y和Z的值。

void Desceding(int &x, int &y, int &z) {

//将x、y和z按从大到小的顺序排列

if (x

if (x

if (y

}//Desceding

1.2 试编一个算法求一维数组float a[n]中的所有元素之和。

float sum(float a[], int n) {

// 求数组a[n]中所有元素之和

for (i=0; i

return sum;

}//sum

1.3 分析下列各算法的时间复杂度：

（1）void prime(int n){

/* 判断n是否是素数*/

for (i=2; ((n%i)!=0)&&(i

if i>sqrt(n) printf("%d is a prime number", n)

else printf("%d is not a prime number", n);

}/* prime */

最坏情况下O(sqrt(n))

(2) float sum1(int n){

/* 计算1！+2！+…+n! */

p=1; sum1=0;

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

p=p*i; sum1=sum1+p

}

}/* sum1 */

O(n)

(3) float sum2(int n){

/* 计算1！+2！+…+n! */

sum2=0;

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

p=1;

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

sum2=sum2+p;

}

}/* sum2 */

O(n2)

(4) void sort(int a[],int n){

/* 将数组a中的元素按自小到大的顺序排列*/

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

k=i;

for (j=i+1; j<=n; ++j) if (a[j]

if (k<>j) {x=a[i];a[i]=a[k];a[k]=x;}

}

}/* sort */

O(n2)

（5）void matrimult(a[m][n],b[n][l],c[m][l],int m,int n,int l){ /* a为m×n阶的矩阵，b为n×l阶的矩阵，c为m×l阶的矩阵*/ /* 计算c=a*b */

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

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

c[i,j]=0;

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

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

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

c[i,j]=c[i,j]+a[i,k]*b[k,i];

}/* matrimult */

O(n3)

1.16

void print_descending(int x,int y,int z) //按从大到小顺序输出三个数{

scanf("%d,%d,%d",&x,&y,&z);

if(xy; //<->为表示交换的双目运算符,以下同

if(yz;

if(xy; //冒泡排序

printf("%d %d %d",x,y,z);

}//print_descending

1.17

Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f

{

int tempd;

if(k<2||m<0) return ERROR;

if(m

else if (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

temp[i]=sum;

}

f=temp[m];

}

return OK;

}//fib

分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k m).

1.18

typedef struct{

char *sport;

enum{male,female} gender;

char schoolname; //校名为'A','B','C','D'或'E'

char *result;

int score;

} resulttype;

typedef struct{

int malescore;

int femalescore;

int totalscore;

} scoretype;

void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中

{

scoretype score;

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;

else score[ 0 ].femalescore+=result[i].score;

break;

case 'B':

score.totalscore+=result[i].score;

if(result[i].gender==0) score.malescore+=result[i].score;

else score.femalescore+=result[i].score;

break;

}

i++；

}

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

{

printf("School %d:\n",i);

printf("Total score of male:%d\n",score[i].malescore);

printf("Total score of female:%d\n",score[i].femalescore);

printf("Total score of all:%d\n\n",score[i].totalscore);

}

}//summary

1.19

Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint

{

last=1;