发布时间 : 星期六 文章数据结构习题集答案(C语言严版)更新完毕开始阅读
1.1解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
1.2 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 解:
1.4 解:ADT Complex{
数据对象:D={r,i|r,i为实数} 数据关系:R={
InitComplex(&C,re,im)
操作结果:构造一个复数C,其实部和虚部分别为re和im DestroyCmoplex(&C)
操作结果:销毁复数C Get(C,k,&e)
操作结果:用e返回复数C的第k元的值 操作结果:改变复数C的第k元的值为e
操作结果:如果复数C的两个元素按升序排列,则返回1,否则返回0 操作结果:如果复数C的两个元素按降序排列,则返回1,否则返回0 操作结果:用e返回复数C的两个元素中值较大的一个 操作结果:用e返回复数C的两个元素中值较小的一个 Put(&C,k,e) IsAscending(C) IsDescending(C) Max(C,&e) Min(C,&e)
}ADT Complex
数据对象:D={s,m|s,m为自然数,且m不为0} 数据关系:R={} 基本操作:
InitRationalNumber(&R,s,m)
操作结果:构造一个有理数R,其分子和分母分别为s和m DestroyRationalNumber(&R)
操作结果:销毁有理数R Get(R,k,&e)
操作结果:用e返回有理数R的第k元的值
ADT RationalNumber{
Put(&R,k,e)
操作结果:改变有理数R的第k元的值为e
操作结果:若有理数R的两个元素按升序排列,则返回1,否则返回0 操作结果:若有理数R的两个元素按降序排列,则返回1,否则返回0 操作结果:用e返回有理数R的两个元素中值较大的一个 操作结果:用e返回有理数R的两个元素中值较小的一个 IsAscending(R) IsDescending(R) Max(R,&e) Min(R,&e)
}ADT RationalNumber
1.6 解:(1)exit常用于异常错误处理,它可以强行中断程序的执行,返回操作系统。 (2)以函数的返回值判断正确与否常用于子程序的测试,便于实现程序的局部控制。 (3)用整型函数进行错误处理的优点是可以给出错误类型,便于迅速确定错误。
1.7 解:(1)用scanf和printf直接进行输入输出的好处是形象、直观,但缺点是需要对其进行格式控制, 较为烦琐,如果出现错误,则会引起整个系统的崩溃。
(2)通过函数的参数传递进行输入输出,便于实现信息的隐蔽,减少出错的可能。
(3)通过全局变量的隐式传递进行输入输出最为方便,只需修改变量的值即可,但过多的全局变量 使程序的维护较为困难。 1.8 解:(1) n-1 (2) n-1 (3) n-1
(4) n+(n-1)+(n-2)+...+1=n(n?1)
2 (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= =1n?i?1ni(i?1)2
1n1n21n 2(i?i)??i??i?i(i?1)?2?2i?12i?12i?1i?1 =
111n(n?1)(2n?1)?n(n?1)?n(n?1)(2n?3) 12412 (6) n (7)
?n? 向下取整
n) count=log2n?2
n=40 n=16
(8) 1100 1.9 解:o(log21.11 解:2 nn?1012 ?1012
10 则对于同样的循环次数n,在这个规模下,第二种算法所花费的代价要大得多。故在这个规模 下,第一种算法更适宜。 1.12 解:(1)对 (2)错 (3)错 (4)对 (5)错
1.13 解:n的增长趋势快。但在n较小的时候,50nlog22n的值较大。
当n>438时,n2?50nlog2n
1.14 解:(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快
1.16 试写一算法,自大至小依次输出顺序读入的三个整数X,Y和Z的值
解:
int max3(int x,int y,int z) { }
1.17 解:k>0为阶数,n为数列的第n项 int Fibonacci(int k,int n) { } 1.18 解:
typedef enum{A,B,C,D,E} SchoolName; typedef enum{Female,Male} SexType; typedef struct{
char event[3]; //项目 SexType sex; SchoolName school; int score;
if(k<1) exit(OVERFLOW); int *p,x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j;
for(i=0;i } for(i=k+1;i return p[k]; x=p[0]; for(j=0;j if(x>z) return x; else return z; if(y>z) return y; else return z; else } Component; typedef struct{ int MaleSum; //男团总分 int FemaleSum; //女团总分 int TotalSum; //团体总分 } Sum; Sum SumScore(SchoolName sn,Component a[],int n) { } 1.19 解: #include #include int i,k; int a[ArrSize]; cout<<\cin>>k; if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ } for(i=0;i<=k;i++){ } return 0; if(a[i]>MAXINT) exit(0); else cout< if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1]; Sum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i; for(i=0;i temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp; if(a[i].school==sn){ } if(a[i].sex==Male) temp.MaleSum+=a[i].score; if(a[i].sex==Female) temp.FemaleSum+=a[i].score;