中国人民大学数据库与数据结构1999年考研真题考研试题

中国人民大学 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 。 给 定 关 键 字 序 列 为