2023计算机考研初试在即，在最后阶段建议各位同学将知识点再系统复习一遍，以免有所遗漏！2022计算机考研数据结构第一单元知识点包含数据与数据结构、数据抽象和抽象数据类型、算法分析的基本方法。高顿考研为大家整理了2022计算机考研数据结构第一单元知识点的详细内容，供大家参考复习！
数据与数据结构
数据：计算机加工处理的对象，分为数值数据和非数值数据
数据元素(结点、顶点)：组成数据的基本单位
数据项(字段、域)：组成数据的最小单位
数据结构的概念：
(1)逻辑结构：数据元素间的逻辑关系
(a)集合结构
(b)线性结构
(c)树形结构
(d)图状结构
3类基本的逻辑结构：线性结构，树形结构，图状结构
2类基本的逻辑结构：线性结构，非线性结构
(2)存储结构：数据在计算机中的表示形式
(a)顺序存储结构
(b)链接存储结构
(c)索引存储结构
(d)散列存储结构
(3)运算：在数据上执行的操作
创建、清除、插入、删除等
·数据的逻辑结构和数据的运算定义组成了数据结构的规范。
·数据的存储表示和运算算法的描述构成数据结构的实现。
数据结构的分类：
(1)静态数据结构：一旦创建，其结构不再改变的数据结构。
(2)动态数据结构：允许进行插入删除等操作，其结构是动态变化的数据结构。
数据抽象和抽象数据类型
(1)抽象(降低了问题求解的难度)
数据抽象：只关注数据元素间的逻辑关系，忽略数据在计算机中的具体表示。
过程抽象：只关注数据运算的定义，忽略运算的具体实现方法。
(2)封装与信息隐蔽
(错误局部化，降低问题求解的复杂性，提高程序的可靠性)
封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。
信息隐蔽：对使用者隐藏了数据结构或程序的实现细节。
(3)数据类型和抽象数据类型
数据类型：它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。
抽象数据类型(ADT)：该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离，数据结构是一种抽象数据类型。
算法分析的基本方法
计算机算法：一个有穷的指令序列，它规定了解决某一特定问题的一系列运算。
计算机算法的特征：输入、输出、确定性、能行性、有穷性
“好算法”的特征：正确、简明、健壮、效率
(1)时间复杂度
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)
考点：最好、最坏和平均时间复杂度
(2)空间复杂度
算法执行过程中对存储空间的需求量。
通常是分析最坏的情况。

展开全文