数据结构第一章习题答案

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 (y>0) { @ if (x>100) { 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)=50 00n 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).

Multiply(z1,z2,&product)复数求积

对复数域Z中

任意两个复数z1=x1+iy1 z2=x2+iy2,必可求得其 积为product=(x1*x2-y1*y2)+i(x1*x2+x2*y1)

Get_RealPart(z)取复数的实部

对复数域Z中任意一个复数z=x+iy,必可求得其实部x且x∈R。 Get_ImagPart(z)取复数的虚部 对复数域Z中任意一个复数z=x+iy,必可求得其虚部y且y∈R。 }ADT COMPLEX

以上对复数结构的定义及其六种操作的定义构成了抽象数据

类型“复数”的定义，或者说是它的规范说明。不论它在计算 机内部如何实现，对使用它的外部用户来说，只需要了解并严 格遵循上述数学特性即可。

下面我们模仿例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; }//Createvoid 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*x2y1*y2)+i(x1*x2+x2*y1) { 略}// Multiply float Get_RealPart( Compl z) //求得复数z=x+iy的 实部x { return(z.realpart); }//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)在函数的参数表中设置整形变量。其优点 同上，并可判别多种类型的错误。