041003[数据组织与管理].doc

数据组织与管理复习题 一.解释题，解释以下各个概念。 1、数据的线性结构和非线性结构 答：数据的线性结构：指数据结构中前件和后件是1对1的关系，除了根节点只有一个后件，叶节点只有一个前件。 数据的非线性结构：指数据结构中前件和后件是多对多的关系，包括树和图。树是1队多关系，图是多对多关系。 2、文件管理和数据库管理： 答：文件：存储在外存上的由很多记录组成的数据集合称为文件； 数据库：存储在计算机外存上，有规则存放，并实现了最大共享的数据集合。它和文件的区别是文件仅描述客观实体本身，而数据库描述实体本身及其实体之间的联系。 3、树和二叉树 树：只有一个节点无双亲，称为根节点；其它节点都是只有一个双亲，但可能有多个后代。树是指数据结构中前件和后件是1对多的关系 二叉树：是一种特殊的树，指每个节点的度最大为2的树； 4、信息模型和数据模型： 答：信息模型：从客观世界向机器世界转换的中间步骤，是对客观世界的抽象，常常用实体-关系模型来表示； 数据模型：是机器世界中数据结构、数据操作、数据完整性约束条件三方面因素的表示。 5、关系模型的参照完整性和实体完整性： 答：关系模型的参照完整性：指关系中外键的取值要么为零，要么取和相参考的关系中已经存在的主键的值。 关系模型的实体完整性：指关系中的主键是唯一的； 6、循环队列： 答：将队列存储空间的最后一个位置和队列第一个位置连接起来，形成一个环状 队列形式。 7、文件： 答：指数据记录在外部设备上的组织。习惯上称存储在内存中的记录集合为表，称存储在外存中的记录集合为文件。 8、数据库： 答：DB：存贮数据的“仓库”，即数据的集合，存放在计算机的外存贮器上。其定义：有规则存放，去掉不必要的冗余，可以供多用户共享的数据集合。 二、简述下面各个问题 1、简述SQL语言命令的种类。 答：SQL语言的命令分为四类：查询语言(QL)、数据操作语言(DML)、数据定义语言(DDL)和数据控制语言(DCL)。 2、简述SQL语言命令的种类。 答：答：SQL语言的命令分为四类：查询语言(QL)、数据操作语言(DML)、数据定义语言(DDL)和数据控制语言(DCL)。 3、简述关系模型的三类完整性。 答：实体完整性、参照完整性和用户自定义完整性 实体完整性(Entity Integrity)：是关系模型必须满足的约束条件，由系统自动给予支持，并且用于任何基本关系。 参照完整性规则： 4、数据库系统的特点 （1）数据的结构化；（2）数据共享度高，冗余小；（3）数据的逻辑独立性和物力独立性高；（4）数据的安全性高 5、满二叉树 是一种特殊的树，指每个节点的度为2； 6、链表存储结构 表示数据结构的每个节点中包含两部分：一部分存储结点的数据部分，另一部分存储该结点后序结点的物理地址，从而形成一个连标的形式； 7、数据库系统组成 数据库系统的组成包括数据库、数据库管理系统、软硬件环境和用户。 8、关系数据库的完整性 关系数据库的完整性指数据的相容性和正确性，包括实体完整性、参照完整性和用户自定义完整性。 三、写出解决下面问题的算法思想。 1、已知一组元素的排序码为：（46，74，16，53，14，26，40，38，86，65，27，34）， 利用希尔排序方法写出每次交换后的排列结果。 答： 原题： 46 74 16 53 14 26 40 38 86 65 27 34 （1）t=12/2=6 按以上线的尖头，分成六组，各组内排序后得到： 40 38 16 53 14 26 46 74 86 65 27 34 （2）t=6/2=3 各组内排序后得到： 14 16 46 27 26 53 38 34 65 74 86 （3）t=3/2=1 各组内排序后得到： 14 16 26 27 34 38 40 40 53 65 74 86 2、简述树的前序遍历思想,并写出下图前序遍历的结果。 1．思想：若二叉树为空， 则结束返回；否则 访问根结点 前序遍历左子树 前序遍历右子树 124895367 3、已知一组元素的排序码为：（26，05，37，08，63，12，61，15，49，19），写出二叉排序树的构造过程。 4、已知一串电文ABACCDA，每种字符A、B、 C、 D在电文中出现的次数分别为3、1、2、1，请设计其哈夫曼编码。 答：