笔试-数据结构与算法1.ppt

《笔试-数据结构与算法1.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、三级数据库技术第2章数据结构与算法本部分占总分的15%主要内容：数据结构与算法基本概念线性表的定义、存储和运算树型结构的定义、存储和运算查找排序22.1基本概念考点1数据结构基本概念1、数据采用计算机能识别、存储和处理的符号总称。是对现实世界事务的描述数据元素数据的基本单位，数据集合的个体一个数据元素由一个或多个数据项组成数据项是数据的最小单位学号姓名性别年龄082011李明男2142、数据结构数据之间的关系数据结构包括三方面内容：逻辑结构、存储结构、在数据上定义的运算集合5数据结构数据的逻辑结

2、构数据的存储结构数据的运算线性结构→线性表→栈和队列非线性结构→树形结构(二叉树、树的遍历)顺序结构链式结构索引结构散列结构插入删除查找－顺序查找、二分法查找排序6数据的逻辑结构什么是数据的逻辑结构？数据的逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。数据的逻辑结构可分成2类线性结构非线性结构春夏秋冬父亲儿子女儿7数据的存储结构什么是数据的存储结构？数据的存储结构又称为物理结构，是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储器中的实现。数据的存储

3、结构可分为哪4类？顺序结构、链式结构、索引结构、散列结构数据的存储结构与逻辑结构的关系同一逻辑结构可以采用不同的存储结构8数据的运算定义在逻辑结构上，实现在存储结构上9考点2主要的数据存储方式顺序存储方式和链式存储方式是最主要的内种存储方式顺序存储方式，主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。（逻辑上相邻物理上也相邻）10线性表（K1,K2,K3,K4,K5)逻辑相邻物理相邻示意图顺序存储结构的主要特点如下：①结点中

4、没有链接信息域，只有自身的信息域，存储密度大，空间利用串高。②数据结构中第i个结点的存储地址Li可由下述公式计算求得。Li＝L1十(i—1)×m其中，L1为第一个节点的存储地址，m为每个节点所占用的存储单元个数。②插入、删除运算会引起相应结点的大量移动。112．链式存储方式线性表（K1,K2,K3,K4,K5)逻辑相邻物理相邻示意图12链式存储方式特点：有表示链接信息的指针,存储空间利用率低,存储密度小，逻辑上相邻的结点在物理上不必邻接，可用于线性表、树和图等多种逻辑结构的存储表示插入、删除操作

5、灵活方便13算法分析与设计算法的五个特征输入（0个或多个输入）输出（1个或多个输出）有穷性（在有限时间内完成）确定性（执行结果确定的）有效性（程序是可以实现的）算法分析---时间代价和空间代价14考题1、下列哪些是数据结构研究内容I、数据的采集与清洗II、数据的逻辑组织III、数据的集成V、数据传输IV、数据的检索A、仅II和IIIB、II和IVC、仅I、II、IVD、I、III和IVB2009.042、下列哪个术语与数据存储结构无关？A、顺序表B、双链表C、线性表D、散列表C153、下列与算法

6、有关的叙述中，哪个不正确？A、运算是数据结构的一个重要方面，运算的实现步骤用算法描述B、算法是精确定义的一系列规则，它指出怎样从给定输入信息经过有限步骤产生输出C、算法设计采用由粗到细，由抽象到具体逐步求精的方法D、对于算法的分析，指的是分析算法运行所要占用的机器时间，即算法的时间代价D2008.094、下列关于链式存储结构叙述中，哪个选项正确？I、逻辑相邻物理上不必相邻II、每个节点都包含恰好一个指针域III、用指针体现元素逻辑联系IV、结点中的指针都不能为空V、可以通过计算直接确定某个结点的

7、存储地址A、仅I和IIB、仅I和IIIC、仅I、III和VD、仅II、IV和VB2008.04165、下列关于数据结构基本概念的叙述中，哪一条是不正确的？A）数据是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述B）数据元素（或称结点、记录等）是数据的基本单位C）一个数据元素至少由两个数据项组成D）数据项是有独立含义的数据最小单位C2007.046、下列关于链式存储结构的叙述中，哪些是正确的？I逻辑上相邻的结点物理上不必邻接II每个结点都包含恰好一个指针域III用指针来体现数据元

8、素之间逻辑上的联系IV可以通过计算机直接确定第i个结点的存储地址V存储密度小于顺序存储结构A）I、II和IIIB）I、II、III和IVC）II、IV和VD）I、III和VD2007.04177、下列关于数据运算的叙述中，哪条不正确？A、数据运算是数据结构的一个重要方面B、数据运算的具体实现在数据的逻辑结构上进行C、检索是一种常用的运算D、插入是一种常用的运算B18填空题1、数据结构包括三方面的内容：数据的逻辑结构、数据的存储结构、数据的【3】运算2006.092、散列存储的基本思想是由节点的【