Question

全国计算机等级考试三级数据库考点分析之数据结构算法[1]

Answer 1

第二章 数据结构算法
2.1基本概率

考点1数据结构的基本概念

1.数据

在计算机系统中，数据不仅包含了通常的数值概念，还有更广泛的含义我们把采用计算机对客观事物进行识别、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的信息

数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位，又称为关键码，其值能够确定一个数据元素的数据项。

2.数据结构

数据结构包括3个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式，以及在这些数据上定义的运算的集合。

(l)数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树型结构。

(2)数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。

(3)数据的运算。数据的各种逻辑结构都有相对应的运算，每一种逻辑结构都有一个运算的集合。数据运算主要包括查找(检索)、排序、插人、更新及删除等。

　　考点2主要的数据存储方式

实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储结构是两种最主要的存储方式。

1.顺序存储结构

顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据。顺序存储结构的主要特点如下。

(1)由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自身的信息域，存储密度大，空间利用率高。

(2)数据结构中第i个节点的存储地址乙可由下述公式计算求得：

L¬i＝L¬0＋(i－1)×K

L¬0为第一个节点存储地址，左为每个节点所占的存储单元数。

(3)插人、删除运算会引起相应节点的大量移动各节点的物理地址是相邻的，每一次插人、删除运算会引起相应节点物理地址的重新排列。

2.链式存储结构

链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中链式存储结构的每个节点中至少有一个节点域，来体现数据之间逻辑上的联系。

链式存储结构的主要特点包括以下几个方面。

(1)节点中除自身信自、外，还有表示链接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低。

(2)：罗辑上相邻的节点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构的存储表示。

(3)插人、删除等操作灵活方便，不需要大量移动节点，只需将节点的指针值修改即可。

　　考点3算法设计与分析

在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算，它是解决特定问题的方法。一个算法所占用的计算机资源包括时间代价和空间代价两个方面

时间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法运行时所耗费的时间也以某种单位由f( 1)增至f(n)，则称该算法的时间代价为f(n)。

空间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现时所占用的空间也以某种单位由到g(1)增至g(n)，则称该算法的空间代价为g(n)。

　　2.2线性表

线性表的逻辑结构是由n个数据元素组成的一个有限序列。线性表中所包含元素的个数叫线性表的长度．它是可变的．可同线性表中增加或删除元素。线性表包括顺序表、链表、散列表和串等。

线性表的基本运算有：置表空、求表长、读表元素、插人、删除及检索等操作。

　　考点4顺序表和一维数组

线性表的顺序存储是线性表的一种最简单的存储结构。其存储方法是：在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于或等于线性表的长度，让线性表的第一个元素存储在这个存储空间的第一个单元中，第二个元素存储在第二个单元中，其他元素依次类推。一般情况下，若长度为n的顺序表，在任何位置土插入或删除的概率相等，元素移动的平均次数均为n/2。