资源描述
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)=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|c1R,c2R 数据关系： Z=R*R=| c1R,c2R 基本操作: Create(x,y, /实部 float imagpart; /虚部 Compl; /-基本操作的函数原型说明- ,void Create( float x,float y,Compl /Add,void Substract(Compl z1,Compl z2,Compl /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),for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+),语句频度 =,(7),(8),X=91; y=100; while (y0) if (x100) x-=10; y-; else x+;,语句实质是: while (x=100) x+; x- = 10; y-;,内循环次数为10,外循环次数为100,语句的频度 应为 1100,
展开阅读全文