《数据结构第一章习题答案》由会员分享，可在线阅读，更多相关《数据结构第一章习题答案（20页珍藏版）》请在金锄头文库上搜索。
1、1.1 简述下列术语：数据、数据元素、数据对象、存储结构、数据类型和抽象数据类型。1.3 设有数据结构（D，R），其中D=d1,d2,d3,d4,R=r,r=(d1,d2), (d2,d3),(d3,d4).试按图论中图的画法画出其逻辑结构图1.8 设n为正整数，试确定下列各程序段中前置以记号的语句的频度(7) x=n;y=0; while( x=(y+1)*(y+1) y+; (8) x=91; y=100; while (y0) if (x100) x-=100;y- else x+; 1.12 设有以下三个函数： f(n)=21n4+n2+1000,g(n)=15n4+500n3,h(n
2、)=5000n3.5+nlogn请判断以下断言正确与否：（1）f(n)是O（g(n)(2)h(n)是O（f(n)(3)g(n)是O（n3.5)(4)g(n)是O（h(n)(5)h(n)是O（nlogn)1.1 简述下列概念：数据、数据元素、数据简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。线性结构、非线性结构。数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据类型：是一个值的集合以及在这些值上
3、定义的一组操作的总称。数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。逻辑结构：指各数据元素之间的逻辑关系。存储结构：就是数据的逻辑结构用计算机语言的实现。线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。1.12设有以下三个函数：f(n)=21n4+n2+1000,g(n)=15n4+500n3,h(n)=
4、5000n3.5+nlogn请判断以下断言正确与否：（1）f(n)是O（g(n)正确(2)h(n)是O（f(n)错误(3)g(n)是O（h(n)错误(4)h(n)是O（n3.5)正确(5)h(n)是O（nlogn)错误复数抽象数据类型的定义复数抽象数据类型的定义ADTCOMPLEX数据对象：D=c1,c2|c1R,c2R数据关系：Z=R*R=|c1R,c2R基本操作:Create(x,y,&z)生成一个复数操作结果:对任何一对实数x,y(xR,yR),必可生成一个复数域中的复数z=x+iy。Add(z1,z2,&sum)复数求和。对复数域Z中的任意两个复数z1=x1+iy1z2=x2+iy2,
5、必可求得其和为sum=(x1+x2)+i(y1+y2).Substract(z1,z2,&difference)复数求差。对复数域中的任意两个复数z1=x1+iy1和z2=x2+iy2,必可求得其差为difference=(x1-x2)+i(y1-y2).lMultiply(z1,z2,&product)复数求积复数求积l 对复数域对复数域Z中任意两个复数中任意两个复数z1=x1+iy1 z2=x2+iy2,必可求得其必可求得其积为积为product=(x1*x2-y1*y2)+i(x1*x2+x2*y1)l Get_RealPart(z)取复数的实部取复数的实部l对复数域对复数域Z中任意一个
6、复数中任意一个复数z=x+iy,必可求得其实部必可求得其实部x且且xR。lGet_ImagPart(z)取复数的虚部取复数的虚部l对复数域对复数域Z中任意一个复数中任意一个复数z=x+iy,必可求得其虚部必可求得其虚部y且且yR。lADT COMPLEXl以以上上对对复复数数结结构构的的定定义义及及其其六六种种操操作作的的定定义义构构成成了了抽抽象象数数据据类类型型“复复数数”的的定定义义，或或者者说说是是它它的的规规范范说说明明。不不论论它它在在计计算算机机内内部部如如何何实实现现，对对使使用用它它的的外外部部用用户户来来说说，只只需需要要了了解解并并严严格遵循上述数学特性即可。格遵循上述数
7、学特性即可。下面我们模仿例下面我们模仿例1-7写出写出COMPLEX 抽象数据类型的表示和实现抽象数据类型的表示和实现/类型定义如下：typedef structcmptpfloatrealpart;/实部floatimagpart;/虚部Compl;/-基本操作的函数原型说明-voidCreate(floatx,floaty,Compl&z);/生成一个实部为x,虚部为y的复数zz.realpart=x;z.imagpart=y;/Create voidAdd(Complz1,Complz2,Compl&sum)/求得和sum=z1+z2=(x1+x2)+i(y1+y2).sum.realp
8、art=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;/AddvoidSubstract(Complz1,Complz2,Compl&difference)/求得差difference=z1-z2=(x1-x2)+i(y1-y2).difference.realpart=z1.realpart-z2.realpart;difference.imagpart=z1.imagpart-z2.imagpart;/SubstractvoidMultiply(Complz1,Complz2,Comol&z)/求得其积为produ
9、ct=z1*z2=(x1*x2-y1*y2)+i(x1*x2+x2*y1)略/MultiplyfloatGet_RealPart(Complz)/求得复数z=x+iy的实部x return(z.realpart);/Get_RealPartfloatGet_ImagPart(Complz)/求得复数z=x+iy的虚部yreturn(z.imagpart);/Get_ImagPart1.6在程序设计中，常用下列三种不同的出错处理方式：（1）用exit语句终止并报告错误（2）以函数的返回值区别正确返回或错误返回（3）设置一个整型变量的函数参数以区别正确返回或某种错误返回ADT复数的C描述typed
10、efstructdouble realpart;doubleimagpart;Complex;voidassign(Complex*pSrc,Complex*pDes)if(pSrc=NULL|pDes=NULL)returnERROR;pDes-realpart=pSrc-realpart;pDes-imagpart=pSrc-imagpart;Complex*add(Complex*pZ1,Complex*pZ2)Complex*pSum=(Complex*)malloc(sizeof(Complex);if(pSum=NULL)returnNULL;pSum-realpart=pZ1-r
11、ealpart+pZ2-realpart;pSum-imagpart=pZ1-imagpart+pZ2-imagpart;returnpSum;题题1.6三种出错处理方式的比较：三种出错处理方式的比较：（1）用exit语句终止执行并报告错误。其优点其优点是是，直观、嵌套层次少；缺点是缺点是，中断函数的执行。故不适宜用在子函数中。（2）用布尔函数实现算法。其优点是，将错误返回给调用环境，由调用环境决定程序的下一由调用环境决定程序的下一步走向。步走向。（3）在函数的参数表中设置整形变量。其优点同上，并可判别多种类型的错误并可判别多种类型的错误。1.7在程序设计中，可采用下列三种方法实现输入和输出：
12、（1）通过scanf和printf语句；（2）通过函数的参数显式传递（3）通过全局变量隐式传递。试讨论这三种方法的优缺点。题题1.7(1)直接和外部环境和外部环境进行信息交换，复用复用性较差性较差，一般仅用在人机对话的用户界面中;(2)和调用环境和调用环境进行信息交换，安全性好安全性好，使模块内部出现的错误不外传，进行模块测试时，只要保证本模块从入口到出口的结果正确即可。(3)交换方式同(2)，但不安全不安全，容易出现各模块的错误滚动传递。实现输入和输出的三种方式实现输入和输出的三种方式: :题题1.8学会系统分析的方法学会系统分析的方法(5)for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)语句频度语句频度=则语句频度应为则语句频度应为 n循环条件是(y+1)20)if(x100)x-=10;y-;elsex+;语句语句实质是实质是: :while(x=100)x+;x-=10;y-;内循环次数为内循环次数为10外循环次数为外循环次数为100语句语句的频度的频度应为应为 1100
