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

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.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。 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（h(n)) 错误 (4) h(n) 是O（n 3.5) 正确 (5) h(n) 是O（nlogn) 错误 复数抽象数据类型的定义 ADT COMPLEX{ 数据对象：D={c1,c2|c1∈R,c2∈R} 数据关系： Z=R*R={c1,c2| c1∈R,c2∈R} 基本操作: Create(x,y,z)生成一个复数 操作结果:对任何一对实数x,y(x∈R,y∈R),必可生成一个复数域中的复数 z=x+iy。 Add(z1,z2,sum)复数求和。 对复数域Z中的任意两个复数z1=x1+iy1 z2=x2+iy2,必可求得其和为sum=(x1+x2)+i(y1+y2). Substract(z1,z2,difference)复数求差。 对复数域中的任意两个复数z1=x1+iy1和z2=x2+iy2,必可求得其差为 difference=(x1-x2)+i(y1-y2). 下面我们模仿例1-7写出COMPLEX 抽象数据类型的表示和实现 //类型定义如下： typedef struct cmptp{ float realpart; //实部 float imagpart; //虚部 } Compl; //-----基本操作的函数原型说明----- ┋ void Create( float x,float y,Compl z); //生成一个实部为x,虚部为y的复数z { z.realpart=x; z.imagpart=y; }//Create void Add(Compl z1,Compl z2,Compl sum) //求得和sum=z1+z2=(x1+x2)+i(y1+y2). { sum.realpart=z1.realpart+z2.realpart; sum.imagpart=z1.imagpart+z2.imagpart; }//Add void Substract(Compl z1,Compl z2,Compl difference) //求得差difference=z1-z2=(x1-x2)+i(y1-y2). { difference.realpart=z1.realpart-z2.realpart; difference.imagpart=z1.imagpart-z2.imagpart; }//Substract void Multiply( Compl z1,Compl z2,Comol z) //求得其积为product=z1*z2=(x1*x2-y1*y2)+i(x1*x2+x2*y1) { 略}// Multiply flo