(完整版)严蔚敏版数据结构课后习题答案-完整版.docx
256页
第1章绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型解：数据是对客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理数据对象是性质相同的数据元素的集合，是数据的一个子集数据结构是相互之间存在一种或多种特定关系的数据元素的集合存储结构是数据结构在计算机中的表示数据类型是一个值的集合和定义在这个值集上的一组操作的总称抽象数据类型是指一个数学模型以及定义在该模型上的一组操作是对一般数据类型的扩展1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
1.3设有数据结构(D,R)，其中D={d1,d2,d3,d4}，R=$}，r=鶴1,d2)Q2,d3)Q3,d4)}试按图论中图的画法惯例画出其逻辑结构图解:1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)解:ADTComplex{数据对象：D二{r,i|r,i为实数}数据关系：R={
1) product=1;i=1;while(i<=n){product*=i;i++;}(2) i=0;do{i++;}while((i!=n)&&(a[i]!=x));(3) switch{casex 2) 通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能3) 通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难1.8设n为正整数试确定下列各程序段中前置以记号@的语句的频度：(1) i=1;k=0;while(i<=n-1){@k+=10*i;i++;}(2) i=1;k=0;do{@k+=10*i;i++;}while(i<=n-1);(3) i=1;k=0;while(i<=n-1){i++;@k+=10*i;}(4) k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;}(5) for(i=1;i<=n;i++){for(j=1;j<=i;j++){for(k=1;k<=j;k++)@x+=delta;}(6) i=1;j=0;while(i+j<=n){@if(i>j)j++;elsei++;}⑺x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}(8)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;解：(1)n-1(2)n-1(3) n-1(4) n+(n-1)+(n-2)+...+1=n(n+D2(5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)二£i(i+1)2i=1=-工i(i+1)=-工(i2+i)=1工i2+-工i2222i=1i=1i=1i=1=n(n+1)(2n+1)+n(n+1)=n(n+1)(2n+3)12412(6) n（7）L/n」向下取整（8）11001.9假设n为2的乘幂，并且n>2,试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。 intTime（intn）{count=0;x=2;while（x 2解：n2的增长趋势快但在n较小的时候，50nlogn的值较大2当n〉438时，n2>50nlogn21・14判断下列各对函数f(n)和g(n)，当n卄时,哪个函数增长更快?(1)(2)f(n)=10n2+ln(l!+10n3)g(n)=2n4+n+7f(n)=(ln(n!)+5》，g(n)=13n2.5(3)f(n)g(n)=(ln(n!))2+(4)g(n)=n(n2)+n5解：(1)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快1. 15试用数学归纳法证明：⑴£i2=n(n+1)2n+1)/6(n>0)i=1(2)工xi=J+i-1)/(x一1)(xH1,n>0)i=0⑶工2i-1=2n-1(n>1)i=1⑷工(2i-1)=n2(n>1)i=11. 16试写一算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值解：intmax3(intx,inty,intz){if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;}1.17已知k阶斐波那契序列的定义为f=0，f=0，…，f=0，f=1；01k-2k-1f=f+f+…+f，n=k,k+1,…nn-1n-2n-k试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。 解：k>0为阶数，n为数列的第n项intFibonacci(intk,intn){if(k<1)exit(OVERFLOW);int*p,x;p=newint[k+1];if(!p)exit(OVERFLOW);inti,j;for(i=0;i
