三级数据库技术考试培训——笔试第2,3次数据结构与算法.ppt

三级数据库技术 第2章 数据结构与算法 2.1基本概念 考点1 数据结构基本概念 1、数据 采用计算机能识别、存储和处理的符号总称。是对现实世界事务的描述 数据元素 数据的基本单位，数据集合的个体 一个数据元素由一个或多个数据项组成 数据项是数据的最小单位 2、数据结构 数据之间的关系 数据结构包括三方面内容： 逻辑关系、在计算机中的存储方式、在数据上定义的运算集合 数据的逻辑结构 什么是数据的逻辑结构？ 数据的逻辑结构是指数据元素之间的逻辑关系， 与数据的存储无关，是独立于计算机的。 数据的逻辑结构可分成2类 线性结构 非线性结构 数据的存储结构 什么是数据的存储结构？ 数据的存储结构又称为物理结构，是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储器中的实现。 数据的存储结构可分为哪4类？ 顺序结构、链式结构、索引结构、散列结构 数据的存储结构与逻辑结构的关系 同一逻辑结构可以采用不同的存储结构 数据的运算定义在逻辑结构上，实现在存储结构上 考点2 主要的数据存储方式 顺序存储方式和链式存储方式是最主要的内种存储方式 顺序存储方式，主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 （逻辑上相邻物理上也相邻） 线性表（K1,K2,K3,K4,K5)逻辑相邻 物理相邻示意图 顺序存储结构的主要特点如下： ①结点中没有链接信息域，只有自身的信息域，存储密度大，空间利用串高。 ②数据结构中第i个结点的存储地址Li可由下述公式计算求得。 Li＝L1十(i—1)×m 其中，L1为第一个节点的存储地址，m为每个节点所占用的存储单元个数。 ②插入、删除运算会引起相应结点的大量移动。 2．链式存储方式 线性表（K1,K2,K3,K4,K5)逻辑相邻 物理相邻示意图 链式存储方式特点： 有表示链接信息的指针,存储空间利用率低,存储密度小， 逻辑上相邻的结点在物理上不必邻接，可用于线性表、树和图等多种逻辑结构的存储表示 插入、删除操作灵活方便 算法分析与设计 算法的五个特征 输入（0个或多个输入） 输出（1个或多个输出） 有穷性（在有限时间内完成） 确定性（执行结果确定的） 有效性（程序是可以实现的） 算法分析---时间代价和空间代价 考题 1、下列哪些是数据结构研究内容 I、数据的采集与清洗 II、数据的逻辑组织 III、数据的集成V、数据传输 IV、数据的检索 A、仅II和III B、II和V C、仅I、II、IV D、I、III和IV B 2009.04 2、下列哪个术语与数据存储结构无关？ A、顺序表 B、双链表 C、线性表 D、散列表 C 3、下列与算法有关的叙述中，哪个不正确？ A、运算是数据结构的一个重要方面，运算的实现步骤用算法描述 B、算法是精确定义的一系列规则，它指出怎样从给定输入信息经过有限步骤产生输出 C、算法设计采用由粗到细，由抽象到具体逐步求精的方法 D、对于算法的分析，指的是分析算法运行所要占用的机器时间，即算法的时间代价 D 2008.09 4、下列关于链式存储结构叙述中，哪个选项正确？ I、逻辑相邻物理上不必相邻 II、每个节点都包含恰好一个指针域 III、用指针体现元素逻辑联系 IV、结点中的指针都不能为空 V、可以通过计算直接确定某个结点的存储地址 A、仅I和II B、仅I和III C、仅I、III和V D、仅II、IV和V B 2008.04 5、下列关于数据结构基本概念的叙述中，哪一条是不正确的？ A） 数据是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述 B）数据元素（或称结点、记录等）是数据的基本单位 C）一个数据元素至少由两个数据项组成 D）数据项是有独立含义的数据最小单位 C 2007.04 6、下列关于链式存储结构的叙述中，哪些是正确的？ I逻辑上相邻的结点物理上不必邻接 II 每个结点都包含恰好一个指针域 III 用指针来体现数据元素之间逻辑上的联系 IV 可以通过计算机直接确定第 i 个结点的存储地址 V 存储密度小于顺序存储结构 A）I、II和III B）I、II、III和IV C）II、IV和V D）I、III和V D 2007.04 7、下列关于数据运算的叙述中，哪条不正确？ A、数据运算是数据结构的一个重要方面 B、数据运算的具体实现在数据的逻辑结构上进行 C、检索是一种常用的运算 D、插入是一种常用的运算 B 填空题 1、数据结构包括三方面的内容：数据的逻辑结构、数据的存储结构、数据的?【3】? 运算 2006.09 2、散列存储的基本思想是由节点的【1