1999年中国人民大学信息学院数据库与数据结构
招生专业：计算机应用
《数据库》部分
一、简答题（每小题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的情形）。
