第2章数据结构与算法24考点1数据结构基本概念1、数据采用计算机能识别、存储和处理的符号总称。是对现实世界事务的描述数据元素数据的基本单位，数据集合的个体一个数据元素由一个或多个数据项组成数据项是数据的最小单位学号姓名性别年龄082011李明男2152、数据结构数据之间的关系数据结构包括三方面内容：逻辑结构、存储结构、在数据上定义的运算集合6数据数据结构结构数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构数据的运算数据的运算线性结构线性结构→→线性表线性表→→栈和队列栈和队列非线性结构非线性结构→→树形结构树形结构((二叉树、树的遍历二叉树、树的遍历))顺序结构顺序结构链式结构链式结构索引结构索引结构散列结构散列结构插入插入删除删除查找－顺序查找、二分法查找查找－顺序查找、二分法查找排序排序7数据的逻辑结构什么是数据的逻辑结构？什么是数据的逻辑结构？数据的逻辑结构是指数据元素之间的逻辑关系数据的逻辑结构是指数据元素之间的逻辑关系，，与数据的存储无关，是独立于计算机的。与数据的存储无关，是独立于计算机的。数据的逻辑结构可分成数据的逻辑结构可分成22类类线性结构线性结构非线性结构非线性结构春夏秋冬父亲儿子女儿8数据的存储结构什么是数据的存储结构？什么是数据的存储结构？数据的存储结构又称为物理结构数据的存储结构又称为物理结构，是指数据元素及，是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储器中的实现。在计算机存储器中的实现。数据的存储结构可分为哪数据的存储结构可分为哪44类？类？顺序结构、链式结构、索引结构、散列结构顺序结构、链式结构、索引结构、散列结构数据的存储结构与逻辑结构的关系数据的存储结构与逻辑结构的关系同一逻辑结构可以采用不同的存储结构同一逻辑结构可以采用不同的存储结构9数据的运算定义在逻辑结构上，实现在存储结构上10考点2主要的数据存储方式顺序存储方式和链式存储方式是最主要的内种存储方式顺序存储方式，主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。（逻辑上相邻物理上也相邻）11线性表（K1,K2,K3,K4,K5)逻辑相邻物理相邻示意图顺序存储结构的主要特点如下：①结点中没有链接信息域，只有自身的信息域，存储密度大，空间利用串高。②数据结构中第i个结点的存储地址Li可由下述公式计算求得。Li＝L1十(i—1)×m其中，L1为第一个节点的存储地址，m为每个节点所占用的存储单元个数。②插入、删除运算会引起相应结点的大量移动。122．链式存储方式线性表（K1,K2,K3,K4,K5)逻辑相邻物理相邻示意图13链式存储方式特点：有表示链接信息的指针,存储空间利用率低,存储密度小，逻辑上相邻的结点在物理上不必邻接，可用于线性表、树和图等多种逻辑结构的存储表示插入、删除操作灵活方便14算法分析与设计算法的五个特征输入（0个或多个输入）输出（1个或多个输出）有穷性（在有限时间内完成）确定性（执行结果确定的）有效性（程序是可以实现的）算法分析---时间代价和空间代价15考题1、下列哪些是数据结构研究内容I、数据的采集与清洗II、数据的逻辑组织III、数据的集成V、数据传输IV、数据的检索A、仅II和IIIB、II和IVC、仅I、II、IVD、I、III和IVB2009.042、下列哪个术语与数据存储结构无关？A、顺序表B、双链表C、线性表D、散列表C163、下列与算法有关的叙述中，哪个不正确？A、运算是数据结构的一个重要方面，运算的实现步骤用算法描述B、算法是精确定义的一系列规则，它指出怎样从给定输入信息经过有限步骤产生输出C、算法设计采用由粗到细，由抽象到具体逐步求精的方法D、对于算法的分析，指的是分析算法运行所要占用的机器时间，即算法的时间代价D2008.094、下列关于链式存储结构叙述中，哪个选项正确？I、逻辑相邻物理上不必相邻II、每个节点都包含恰好一个指针域I