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

真考链接

在选择题中，考核概率为45%。该知识点属于熟记内容，应熟记数据结构的定义、分类，能区分线性结构与非线性结构。

1.数据结构的定义

数据结构是指相互有关联的数据元素的集合，即数据的组织形式。

（1）数据的逻辑结构

所谓数据的逻辑结构，是指反映数据元素之间逻辑关系（即前后件关系）的数据结构。它包括两个要素，即数据元素的集合和数据元素之间的关系。

（2）数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。数据结构的存储方式有：顺序存储方法、链式存储方法、索引存储方法和散列存储方法。而采用不同的存储结构，其数据处理的效率是不同的。因此在进行数据处理时，选择合适的存储结构是很重要的。

数据结构研究的内容主要包括3个方面：

●数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；

●在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

●对各种数据结构进行的运算。

2.数据结构的图形表示

数据元素之间最基本的关系是前后件关系。所谓前后件关系即每一个二元组，都可以用图形来表示。用中间标有元素值的方框表示数据元素，一般称之为数据节点，简称为节点。对于每一个二元组，通常用一条有向线段从前件指向后件。

用图形表示数据结构具有直观、易懂的特点，在不引起歧义的情况下，前件节点到后件节点连线上的箭头可以省去。例如在树形结构中，通常都是用无向线段来表示前后件关系的。

3.线性结构与非线性结构

根据数据结构中各数据元素之间前后关系的复杂程度，一般可将数据结构分为两大类型：线性结构和非线性结构。

如果一个非空的数据结构满足有且只有一个根节点，并且每个节点最多有一个直接前驱和直接后继，则称该数据结构为线性结构，又称线性表。不满足上述条件的数据结构则称为非线性结构。

小提示

需要注意的是：在一个线性结构中插入或删除任何一个节点后还应该是线性结构，否则不能称之为线性结构。

真题精选

下列叙述中正确的是（ ）。

A）程序执行的效率与数据的存储结构密切相关

B）程序执行的效率只取决于程序的控制结构

C）程序执行的效率只取决于所处理的数据量

D）以上3种说法都不对

【答案】A

【解析】在计算机中，数据的存储结构对数据的执行效率有较大的影响，例如在有序存储的表中查找某个数值就比在无序存储的表中查找的效率高很多。