扫码获取更多资源

●基础概念和术语

1、数据：数据是信息的载体，是描述客观事物属性的数，字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。（数值、图像、声音等）。

2、数据元素：数据元素是数据的基本单位，但不是最小单位。在程序中通常作为一个整体来进行考虑和处理，又称为记录。

3、数据项：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。

4、数据对象：数据对象是性质相同的数据元素的集合，是数据的一个子集。

5、数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。1）原子类型。其值不可再分的数据类型（整型 int 、字符型 char )2）结构类型。其值可以再分解为若干成分（分量）的数据类型．

6、抽象数据类型（ abstractdata type ，简称 ADT )：抽象数据类型是抽象数据组织及与之相关的操作，具体包括三部分：数据对象，数据对象上关系的集合，

以及对数据对象的基本操作的集合。

抽象数据类型的形式定义用以下三元组表示：

ADT =( D , SP ) e

其中 D 表示数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何

表示和实现无关。

7、数据结构（ Data Structure )：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

数据结构是指相互之间具有（存在）一种或多种特定关系的数据元素的集合。元素之间的相互联系（关系）称为结构。数据结构包括三方面的内容：逻辑结构，

存储结构和数据运算。

数据结构的形式定义是一个二元组：

Data - Structure =( D , S )

其中： D 是数据元素的有限集， S 是 D 上关系的有限集。

一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

8、数据的逻辑结构

数据的逻辑结构是对数据元素之间关系的描述它与数据的存储无关，同一

种逻辑结构可以有多种存储结构，主要分为两类。

(1）线性结构：结构中的数据元素之间存在一对一的关系。

(2）非线性结构：可细分为集合、树形结构和图状结构。集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。树型结构：结构中的数据元素之间存在一对多的关系。

③图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

●算法设计习题

1．按增长率由小至大的顺序排列这些函数：2100、(3/2)"、(2/3)"、 n "、 n 、 n !、2"、 Ign 、 nlen 、n3/2)

2．多项式 A ( x ）的算法可以根据下列两个公式之一来设计：

(1) A ( x )= a „ x "十 a „-1x"！十…十 ajx 十 a

(2) A ( x )=(...( an x 十 an -1) x 十．.◆十 a X ）十 ao 试根据算法的时间复杂度分析比较这两种算法的优劣。

3．设有3个函数： f ( n )=100n'十 n 十1000, g ( n )=25n十5000n?, h ( n )= n 十5000nlogn。试分析并判断下列关系是否成立：

(1) f ( n )= O ( g ( n ))

(3) h ( n )= O (n5)

(2) g ( n )= O ( f ( n ))

(4) hn )= O ( nlogn )

联系我们：