数据结构1

1.1请说明算法具有哪些特性，各是什么含义？算法的一般性质包括：（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的.（3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4）有穷性算法的执行必须在有限步内结束.1.2简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素（dataelement）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（dataobject）：性质相同的数据元素的集合。是数据的一个子集。数据结构(datastructure)：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合和数据元素之间的关系的集合。存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（datatype）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。抽象数据类型（abstractdatatype，简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。1.3设n为正整数。试确定下列各程序段中前置以记号@的语句频度：(1)x=n;y=0;//n为不小于1的常数while(x=(y+1)*(y+1)){@y++;}n1/2向下取整(2)i=1;j=0;while(i+j=n){@if(ij)j++;elsei++;}n注：@语句指的是if…else语句，语句频度为j++和i++执行的次数之和。1.4请说明下列算法的时间复杂度。(1)voidsf1(intn){inti,x=0;for(i=1;in+1;i++)for(j=1;j=8;j++)x+=2;}(2)voidsf2(intn,intm){for(i=0;im;i++)for(j=0;jn;j++)x++;}1.1算法的一般性质包括：（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的.（3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4）有穷性算法的执行必须在有限步内结束.1.2数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素（dataelement）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（dataobject）：性质相同的数据元素的集合。是数据的一个子集。数据结构(datastructure)：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合和数据元素之间的关系的集合。存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（datatype）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。抽象数据类型（abstractdatatype，简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。1.3(1)n1/2向下取整(2)n1.4(1)o(8*n)去常数项就是o(n)(2)o（m*n）