数据结构第一章习题答案.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)=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 R,c2 R 基本操作 : 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)，但 不安全 ，容易出现各 模块的错误滚动传递。 实现输入和输出的三种方式 : 题 1.8 学会系统分析的方法 (5) n i n i i j n i i j j k iij 11 11 1 1 2 )1(1 for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+) 6 )2)(1( 2 )1( 6 )12)(1( 2 1 2 1 11 2 nnn nnnnn ii n i n i 语句频度 = 则语句频度应为 n 循环条件是 (y+1)20) if (x100) x-=10; y-; else x+; 语句 实质是 : while (x=100) x+; x- = 10; y-; 内循环次数为 10 外循环次数为 100 语句 的频度 应为 1100