当前位置：文档之家› 数据结构1

数据结构1

1.1 请说明算法具有哪些特性，各是什么含义？
算法的一般性质包括：（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的.（3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4）有穷性算法的执行必须在有限步内结束.
1.2简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类
型和抽象数据类型。

数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。

数据元素（data element）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。

例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（data object）：性质相同的数据元素的集合。

是数据的一个子集。

数据结构(data structure)：相互之间存在一种或多种关系的数据元素的集合。

即包括数据元素的集合和数据元素之间的关系的集合。

存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。

又称为存储结构。

数据类型（data type）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。

抽象数据类型（abstract data type，简称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 (i>j) j++;
else i++;
}
n
注：@语句指的是if…else语句，语句频度为j++和i++执行的次数之和。

1.4请说明下列算法的时间复杂度。

(1) void sf1 (int n)
{ int i, x=0;
for(i=1; i<n+1; i++)
for(j=1; j<=8; j++)
x+=2;
}
(2) void sf2 (int n, int m)
{ for (i=0; i<m; i++)
for(j=0; j<n; j++)
x++;
}
1.1算法的一般性质包括：
（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.
（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的. （3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.
（4）有穷性算法的执行必须在有限步内结束.
1.2
数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。