数据结构第一章习题答案.ppt

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)=5000n 3.5+nlogn 请判断以下断言正确与否： （1） f(n)是O（g(n) ) (2) h(n) 是O（f(n) ) (3) g(n) 是O（n 3.5) (4) g(n) 是O（h(n) (5) h(n) 是O（nlogn) 1.1 简述下列概念：数据、数据元素、数据 类型、数据结构、逻辑结构、存储结构、 线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的 信息载体。 数据元素：就是数据的基本单位，在某些情况下 ，数据元素也称为元素、结点、顶点、记录。数 据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义 的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据 的组织形式。一般包括三个方面的内容:数据的逻 辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言 的实现。 线性结构：数据逻辑结构中的一类，它的特征 是若结构为非空集，则该结构有且只有一个开 始结点和一个终端结点，并且所有结点都最多 只有一个直接前趋和一个直接后继。线性表就 是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它 的逻辑特征是一个结点可能有多个直接前趋和 直接后继。 1.12 设有以下三个函数： f(n)=21n4+n2+1000,g(n)=15n4+500n3,h(n)=5 000n 3.5+nlogn 请判断以下断言正确与否： （1） f(n)是O（g(n) ) 正确 (2) h(n) 是O（f(n) ) 错误 (3) g(n) 是O（h(n) 错误 (4) h(n) 是O（n 3.5) 正确 (5) h(n) 是O（nlogn) 错误 复数抽象数据类型的定义 ADT COMPLEX 数据对象：D=c1,c2|c1R,c2R 数据关系： Z=R*R=| c1R,c2R 基本操作: Create(x,y, /实部 float imagpart; /虚部 Compl; /-基本操作的函数原型说明- void Create( float x,float y,Compl /生成一个实部为x,虚部为y的复数z z.realpart=x; z.imagpart=y; /Create void Add(Compl z1,Compl z2,Compl sum.imagpart=z1.imagpart+z2.imagpart; /Add void Substract(Compl z1,Compl z2,Compl difference.imagpart=z1.imagpart-z2.imagpart; /Substract void Multiply( Compl z1,Compl z2,Comol /Get_RealPart float Get_ImagPart(Compl z) /求得复数z=x+iy的虚部y return (z.imagpart); /Get_ImagPart 1.6 在程序设计中，常用下列三种 不同的出错处理方式： （1）用exit语句终止并报告错误 （2）以函数的返回值区别正确 返回或错误返回 （3）设置一个整型变量的函数参 数以区别正确返回或某种错误返 回 ADT复数的C描述 typedef struct double realpart; double imagpart; Complex; void assign(Complex *pSrc, Complex *pDes) if (pSrc =NULL | pDes=NULL ) return ERROR; pDes-realpart = pSrc-realpart; pDes-imagpart = pSrc-imagpart; Complex *add(Complex *pZ1, Complex *pZ2) Complex *pSum = (Complex *)malloc(sizeof(Complex); if ( pSum=NULL ) return NULL; pSum-realpart = pZ1-realpart + pZ2-realpart; pSum-imagpart = pZ1-imagpart + pZ2- imagpart; return pSum; 题1.6 三种出错处理方式的比较： （1）用exit语句终止执行并报告错误。其优点 是，直观、嵌套层次少；缺点是，中断函数的 执行。故不适宜用在子函数中。 （2）用布尔函数实现算法。其优点是，将错误 返回给调用环境，由调用环境决定程序的下一 步走向。 （3）在函数的参数表中设置整形变量。其优点 同上，并可判别多种类型的错误。 1.7 在程序设计中，可采用下列三 种方法实现输入和输出： （1）通过scanf和printf语句； （2）通过函数的参数显式传递 （3）通过全局变量隐式传递。 试讨论这三种方法的优缺点。 题1.7 (1) 直接和外部环境进行信息交换，复用性 较差，一般仅用在人机对话的用户界面中; (2) 和调用环境进行信息交换，安全性好， 使模块内部出现的错误不外传，进行模块测 试时，只要保证本模块从入口到出口的结果 正确即可。 (3) 交换方式同(2)，但不安全，容易出现各 模块的错误滚动传递。 实现输入和输出的三种方式: