升研教育考研频道为23考研、24考研的同学们整理了“计算机考研备考资料：数据结构（基本概念）”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

计算机考研专业课一般涉及到四个科目：数据结构、计算机组成原理、操作系统、计算机网络 ，知识点繁多，复习起来也并不失分容易，为了帮助大家复习，本篇为大家整理了一些数据结构中的知识点，供大家参考。

数据结构中的基本概念：

1、数据(data) ：信息的载体，指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。

2、数据元素(data element)：数据元素是组成数据的基本单位。根据需要，有时被称为元素、结点、顶点和记录。

数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项(字段)，故不是组成数据的最小单位。

3、数据项：数据元素一般是由数据项组成的，数据项是数据的不可分割的最小表示单位。

4、数据结构：数据的逻辑结构，数据的存储结构和对数据所施加的运算。

这三个方面的关系为：

1) 数据的逻辑结构独立于计算机，是数据本身所固有的。

2)存储结构也称为物理结构，是逻辑结构在计算机存储器中的映像，必须依赖于计算机。

3)运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。

5、逻辑关系：是指数据元素之间的关联方式或称“邻接关系”

6、逻辑结构：数据元素之间逻辑关系的的整体称为逻辑结构

7、四种逻辑结构的特点：

①集合中任何两个结点之间都没有逻辑关系，组织结构松散。

②线性结构中结点按逻辑关系一次排列成一条“锁链”。

③树型结构具有分支、层次特性，其形态有点象自然界中的树。

④图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。

8、运算：是指在逻辑结构上施加的操作，即对逻辑结构的加工。根据操作的效果，运算可分为加工型运算和引用型运算。查找、读取(排序)是引用型运算，插入、删除和更新(修改)是加工型运算。、

9、数据的存储结构：数据的机内表示称为数据的存储结构。

包括以下三个主要部分：

①存储结点，每个存储结点存放一个数据元素

②数据元素之间关联方式的表示，也就是逻辑结构的机内表示

③附加设施。

10、四种基本存储方式

①顺序存储方式：每个存储结点只含一个数据元素，所有存储结点存放在一块连续的存储区里，用存储结点的位置关系表示数据元素之间的逻辑关系。

②链式存储方式：每个存储结点不仅含有一个数据元素，还包含一个指针，每个指针指向一个与本结点有逻辑关系的结点，即用附加的指针表示逻辑关系。

③索引存储方式：每个存储结点只含一个数据元素，所有存储结点连续存放，此外增设一个索引表以指示各存储结点的存储位置或区间端点。

④散列存储方式：每个存储结点只含一个数据元素，各个结点均匀分布在存储区里，用散列函数指示各存储结点的存储位置或区间端点。

11、算法：对特定问题求解步骤的一种描述，是指令的有限序列。

一个算法具有以下5个特性：

①有穷性：算法应在执行有穷步后结束。

②确定性：每步定义都是确切、无歧义的。

③可行性：每一条运算应可通过已经实现的基本运算执行有限次来实现。

算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性(死循环)，另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。

④有0个或多个输入；

⑤有一个或多个输出。

12、算法的分析与度量:

1)算法的性能标准：

正确性：正确执行的功能和性能要求。

可使用性：算法能够很方便的使用。

可读性：便于理解、测试和修改算法。

效率：计算机资源的消耗，包括存储和运行时间。

健壮性：检错、报错及纠错的功能。

2)算法的事前估计：空间复杂度和时间复杂度

3)算法的后期测试：在算法中的某些部位插装时间函数time ( )，测定算法完成某一功能所花费的时间。

13、最坏情况时间复杂性或最坏情况时间复杂度：算法在所有输入下的计算量的最大值。

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记作

14、平均时间复杂性或平均时间复杂度：算法在所有输入下的计算量的加权平均值。