中国人民大学1999年研究生入学考试数据库与数据结构试题
招生专业：计算机应用《
[url=http://book.kaoyantj.com/kaoyanbook_search.asp?shuming=数据库&xuanze=2]数据库[/url]
》部分 一、简答题（每小题3分，共15分） 1．数据模型是由哪几部分组成？简要说明这些部分所定义的是什么？ 2．在嵌入式SQL中游标的作用是什么？ 3．如果对数据库中运行的事务不进行并发控制，数据库会产生哪些不一致？ 4．试述满足BCNF的关系与满足4NF的关系的区别。 5．试述数据库物理设计的内容与步骤。 二、回答题（每小题6分，共12分） 1．在关系数据库系统中为佬要进行查询优化？请说明查询优化的一般策略和一般步骤。 2．试述数据库系统中的完整性概念。在关系数据库系统中是如何定义完整性约束条件的？你认为DBMS中应该怎样实现完整性定义与完整性检查？ 三、现有下面四个关系模式：（共23分） EMP（EMPNO,ENAME,HIREDATE,MONTHSAL,DEPTNO）； DEPT（DEPTNO,DNAME,MGR）； BONUS（WORKPERIOD,MONTHBONUS）； HONOR（HNAME,EMPNO,WINYEAR）； 其中： 雇员表EMP由主码雇员号（EMPNO），以及雇员姓名（ENAME），参加工作的年份（HIREDATE），月工资（MONTHSAL），所在部门（DEPTNO）组成； 部门表DEPT由主码部门号（DEPTNO），以及部门名称（DNAME）和部门经理的雇员号（MGR）组成，一个部门可以有一至两个经理； 奖金表BONUS由主码工龄（WORKPERIOD）和相应的月奖金额（MONTHBONUS）组成，雇员每月的资金数额取决于他的工龄，工龄只精确到年； 荣誉表HONOR由荣誉名（HNAME），获该荣誉称号的职工代码（EMPNO）和相应年份（WIHYEAR）组成。 （一）请用SQL语句完成下列操作： 1．查询每个职工1998年12月的总收入（4分） 2．查询每个部门经理的名字（4分） 3．查询新参加工作人数最多的年份及其人数（4分） 4．查询至少荣获了编号为E901的职工曾荣获过的所有荣誉称号的职工姓名（4分） 5．把查询EMP表（月工资属性除外）的权力授予所有用户（2分） （二）试用关系代数求没有获得任何荣誉称号的职工姓名（3名） （三）试用关系演算求没有获得任何荣誉称号的职工姓名（2分） 《
[url=http://book.kaoyantj.com/kaoyanbook_search.asp?shuming=数据结构&xuanze=2]数据结构[/url]
》部分 一、简答（20分） 1．什么是二叉树的树高（或深度）？简述一种计算树高的算法思想。 2．试分析说明堆排序和快排序的平均时间复杂度。 3．如果只想得到一系列中第M个最小元素之前的部分排序，用什么方法最好？再举出另外一种方法，比较它们的时间复杂度。 4．取哈希函数为H（K）=KMOD13。给定关键字序列为{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的情形）。
页:
[1]