一、简答题（每小题3分，共15分）

1．数据模型是由哪几部分组成？简要说明这些部分所定义的是什么？

2．在嵌入式SQL中游标的作用是什么？

3．如果对数据库中运行的事务不进行并发控制，数据库会产生哪些不一致？

4．试述满足BCNF的关系与满足4NF的关系的区别。

5．试述数据库物理设计的内容与步骤。

二、回答题（每小题6分，共12分）

1．在关系数据库系统中为佬要进行查询优化？请说明查询优化的一般策略和一般步骤。

2．试述数据库系统中的完整性概念。在关系数据库系统中是如何定义完整性约束条件的？你认为DBMS中应该怎样实现完整性定义与完整性检查？

三、现有下面四个关系模式：（共23分）

EMP（EMPNO,ENAME,HIREDATE,MONTH SAL,DEPTNO）；

DEPT（DEPTNO,DNAME,MGR）；

BONUS（WORKPERIOD,MONTH BONUS）；

HONOR（HNAME,EMPNO,WIN YEAR）；

其中：

雇员表EMP由主码雇员号（EMPNO），以及雇员姓名（ENAME），参加工作的年份（HIREDATE），月工资（MONTH SAL），所在部门（DEPTNO）组成；

部门表DEPT由主码部门号（DEPTNO），以及部门名称（DNAME）和部门经理的雇员号（MGR）组成，一个部门可以有一至两个经理；

奖金表BONUS由主码工龄（WORKPERIOD）和相应的月奖金额（MONTH BONUS）组成，雇员每月的资金数额取决于他的工龄，工龄只精确到年；

荣誉表HONOR由荣誉名（HNAME），获该荣誉称号的职工代码（EMPNO）和相应年份（WIH YEAR）组成。

（一）请用SQL语句完成下列操作：

1．查询每个职工1998年12月的总收入（4分）

2． 查询每个部门经理的名字（4分） 

3． 查询新参加工作人数最多的年份及其人数（4分） 

4． 查询至少荣获了编号为E901的职工曾荣获过的所有荣誉称号的职工姓名（4分） 

5．把查询EMP表（月工资属性除外）的权力授予所有用户（2分）

（二）试用关系代数求没有获得任何荣誉称号的职工姓名（3名）

（三）试用关系演算求没有获得任何荣誉称号的职工姓名（2分）

《数据结构》部分

一、简答（20分）

1．什么是二叉树的树高（或深度）？简述一种计算树高的算法思想。

2．试分析说明堆排序和快排序的平均时间复杂度。

3．如果只想得到一系列中第M个最小元素之前的部分排序，用什么方法最好？再举出另外一种方法，比较它们的时间复杂度。

4．取哈希函数为H（K）=K MOD 13。给定关键字序列为{19,14,23,01,68,20,84,27,55,11,10,79}试分别用拉链法和线性探测法解决碰撞
构造哈希表,画出示意图(不要求计算过程)。

二、用类PASCAL或SPARKS语言写算法（30分）

1．已知P0，Q0，R0为三条按升序链接的单链表（P0，Q0，R0为相应的链头指针），试写一算法从链表P0中删去那些既出现在Q0中又出现在
R0中的结点。

2．按如下示意图，通过改链的方法将链表P0改成Q0（只考虑结点数为5的倍数的情形）。

3．设有一棵由M叉树转化而得的二叉树，并建立了中序线索。写出从这棵二叉树中删去原M叉树的安自左向右顺序的第J棵子树的算法（自选
并说明存储结构；只考虑1＜J＜M的情形）。

www.kaoyantj.com考研共济网