数据结构 考研，数据结构考研真题
一：基本概念和基本术语
（1）数据
数据：所谓数据，是指信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
比如我们现在常常使用到的搜索引擎，一般会有网页、音乐、图片、视频等分类，他们对应了声音、图像等数据。其中网页其实指的就是全部数据的搜索，也就是说我们这里说的数据指的就是符号，这些符号必须具备两个前提条件
可以输入到计算机中能被计算机程序处理
其中对于整形、浮点型这类的可以进行数值运算，而对于字符这类的数据就要进行非数值运算，像图像、视频这类数据可以通过编码的手段转换为其他数据进行运算
（2）数据元素和数据项
数据元素：数据元素是数据的基本单位，用于描述一个个体，通常作为一个整体进行考虑和处理。一个数据元素可以由若干数据项组成它是构成数据元素的不可分割的最小单位
人类世界中，数据元素就是单个的人畜类中，像牛、马、羊等就是禽类的数据元素
数据项：一个数据元素可以由若干数据项组成，数据项是数据不可分割的最小单位
对于人这样的数据元素，可以有眼、耳、鼻、嘴、手这些数据项，也可以有姓名、年龄、性别、出生地址、联系电话这些数据项。具体有哪些数据项，要视情况而定
（3）数据对象
我们用数据描述这个世界，用数据元素对应某个逻辑个体，对于个体的种种描述又可以拆分为一个一个的数据项
数据对象：我们把属性相同的数据元素所组成的对象称之为数据对象，数据的子集
比如正整数这个数据对象,所反映了这样一个集合N=0,1,2,3,4,5,……
既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性质，在产生混淆的情况下，我们把数据对象简称为数据
（4）数据结构
所谓结构，是指各个组成部分相互搭配和排列的方式
高中化学中的晶型和这个类似
在现实世界中，不同数据元素之间不是独立的，而是存在某种特定的关系，我们就把这个关系称之为结构
开门见山，比如链表结构，树结构，图结构等
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构强调数据与数据之间必须具有某种对应关系。就像财富排行榜，马斯克下面必须是贝索斯，因为马斯克比贝索斯钱多数据对象强调数据与数据之间必须具有相同的属性
数据结构研究的重点并不在于数据本身，而是在研究这些数据在某种结构下的关系！！！
二：数据结构三要素
（1）逻辑结构
逻辑结构：是指数据对象中数据元素之间的相互关系。是从逻辑上描述数据关系，或者说这种关系是人假想的，对于计算机来说不过就是一个存储单元罢了
逻辑结构主要分为线性结构和非线性结构
线性结构：一对一非线性结构：不是一对一
A：集合
集合：该结构中的数据元素除了同属于一个集合外，他们之间没有任何关系
各个数据元素关系平等，类似于数学中的集合
B：线性结构
线性结构：该结构中的数据元素之间是一对一的关系
除了第一个元素外，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继
C：树形结构
树形结构：该结构中的数据元素之间存在一对多的关系
像操作系统的文件目录结构，思维导图都是典型的树形结构
D：图形结构
图形结构：该结构中的数据元素之间存在多对多的关系
（2）物理结构（存储结构）
存储结构 相当于“纸上谈兵”——这个数据应该这样存，他们之间应该具有这样、那样的关系，但是计算机可不管这么多，因为它就那么一个硬盘，还能玩出什么花样？
物理结构（存储结构）：是指数据的存储结构在计算机中的存储形式
数据的物理结构应该正确的反映数据元素之间的逻辑关系，这是实现物理结构的重点和难点。主要分为：顺序存储和链式存储
比如完全二叉树，它逻辑结构上很明显是树，但是在存储上可以用顺序存储（数组）也可以用链式存储（链表）
A：顺序存储结构
顺序存储结构：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。元素之间的关系由存储单元的邻接关系体现
你可以这样理解，有10个人排队坐位置，拟规定好了A后面是B，那么B在坐的时候一定要做到与A相邻的位置最典型的就是数组
B：链式存储结构
链式存储结构：不要求逻辑上相邻的元素也存储在物理位置也相邻的存储单元中。元素之间的关系借助指示元素存储地址的指针来表示
上例中这些元素逻辑上相邻，但所存放的存储单元并不是连续的
C：索引存储结构
顺序存储结构：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称之为索引项，索引项一般形式是关键字+地址
D：散列存储结构（哈希）
散列存储结构：根据元素的关键字直接计算出该元素的地址。计算依靠的方式称之为哈希函数
顺序存储支持随机存取、占用空间最少要求必须整块存储单元、外部碎片多链式存储不会产生碎片额外空间占用大，只支持顺序存取索引存储检索速度快附加信息太多，占用空间多散列存储检索、增加和删除结点速度极快会出现哈希冲突，解决冲突又会增加额外成本
（3）数据运算
数据运算：施加在数据上的元素包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体步骤
增、删、查、改就是我们日后学习数据结构的基本能操作
三：数据类型和抽象数据类型
（1）数据类型
数据类型：是一个值的集合和定义在此集合上的一组操作的总称
原子类型：其值不可再分的数据类型结构类型：其值可以再分解为若干分量的数据类型
比如C++中的bool类型就是原子类型，其值为true或false，所对应的操作可以有与、或、非等
比如C语言中的结构体struct是一种结构类型
struct Coordinate { int x;//横坐标 int y://纵坐标 }
（2）抽象数据类型（ADT）
抽象数据类型：是抽象数据组织及与之相关的操作。定义一个ADT就是在定义一个数据结构这种数据结构有其对应元素和方法
比如图形结构有一种操作就是遍历
数据结构 考研(数据结构考研真题)