江西财经大学2004年研究生入学考试试题数据结构与数据

江西财经大学2004年研究生入学考试试题数据结构与数

据库原理

专 业：计算机应用技术

重要提示：考生必须将所有答案写在答题纸上，本试题上的任何标记均不作判题依据

第一部分：数据库系统原理

一、概念题（每小题3分，共15分）

1、数据模型 2、外码

3、日志文件及其作用 4、数据库设计

5、数据库系统用 ① 描述现实世界的实体及实体间的联系。关系模型是用 ② 表示实体，用 ③ 表示实体间的联系。层将和网状模型是用 ④ 表示实体，用 ⑤ 表示实体间的联系，而用 ⑥ 实现实体间的联系。 其中，第5题供选择的答案有：

数据模型 概念模型 外模型 内模型 结点 表 数据结构 指针 连线 模式 外模式 内模式 数据描述语言 数据操纵语言 高级程序设计语言

二、简答题（每小题5分，共15分）

1、简述数据库系统的三级模式结构。

2、对数据库系统中的故障进行分类，并简述系统故障的恢复过程。 3、简述关系数据库实施完整性约束的内容有哪些?

三、（共14分）有一个成绩管理的数据库，它包含如下三张表： (1) 学生表：STUDENT

学号 姓名 性别 专业

(2) 课程表：COURSE

课程号 课程名 学时 学分 (3) 成绩表：SCORE

学号 课程号 成绩 学期

根据上面三张表，完成以下各题：

1、试用关系代数表示查询2002-2003学年第一学期（“02-03/1”）选修了“数据结构”课程

的学生姓名。（4分）

2、用SQL语句表示查询重修过“计算机原理”课程（即该课程在成绩表中有2条或2条以上记录）的学生姓名及重修次数。（4分） 3、写出下列SQL语句的查询语义（即功能）： SELECT 姓名, 课程名, 成绩

FROM STUDENT S, COURSE C, SCORE SC

WHERE (S.学号=SC.学号) AND (C.课程号=SC.课程号) AND SC.成绩=( SELECT MAX(SCORE.成绩)

FROM SCORE

WHERE SCORE.课程号=SC.课程号)

请给出三个实例关系表（其中学生表至少3个学生、课程表至少2门课程），并根据给出的实例关系表写出该SQL查询的执行结果。（6分） 四、（共13分）设有如下商品库存关系R：

商品编号 A1 A1 A2 A3 A4 商品名称 ABC彩电 ABC彩电 XYZ冰箱 PPP西装 FK自行车 采购批次 1 2 2 1 2 单价 2260 2200 1050 980 450 库存数量 仓库号 5 4 6 8 5 S1 S1 S1 S2 S3 仓库地点 中山路5号 中山路5号 中山路5号 胜利路8号 胜利路8号 请仅在R中已给出数据的范围内分析其函数依赖关系并解答如下问题： 1、R最高为第几范式？为什么？（3分）

2、将它分解为满足3NF范式的关系模式。（5分） 3、分解后比分解前有什么好处？为什么？（5分）

五、叙述在一个DBMS中，事务管理部件（恢复子系统、并发控制子系统）的主要职能及其分

别常用的基本技术和手段。（8分） 六、（共10分）假设数据库中数据项A、B和C的初值均为100。现有两个事务T1和T2，分别包含如下操作：

事务T1：y=Read(C); x=Read(A); x=x+y; Write(A, x);

（即，读数据库中数据项C的值并赋给变量y； 读数据库中数据项A的值并赋给变量x； 变量x的值与变量y的值相加的结果赋给变量x； 将变量x的值写到数据库中数据项A中；）

事务T2：v=Read(C); u=Read(B); u=u+v; Write(A, u);

下面是利用锁机制来实现事务T1、T2的一个并发调度S： T1 T2

Slock C

Slock C

v=Read(C)

2

Unlock C Slock B y=Read(C) Unlock C

Slock A

u=Read(B) Unlock B u=u+v Xlock A x=Read(A) 等待 Unlock A 等待

Write(A, u) （获得排它锁，并实现写） x=x+y Xlock A

等待 Unlock A

（获得排它锁，并实现写） Write(A, x) Unlock A

完成以下解答：

1、调度S是否是可串行化调度？为什么？（4分）

2、利用锁机制给出关于事务T1、T2的一个可串行化并发调度S′(不能是串行调度)，使它与串行调度T1→T2的执行结果等价。并说明等价的理由。（6分）

3

第二部分：数据结构

一、概念题（每小题3分，共9分）

1、栈

2、二叉排序树 3、存储结构

二、简答题(每小题10分，共20分)

1、用类C描述语言定义稀疏矩阵的三元组存储结构，并写出下列矩阵的存储表示。

000M000050200800180000000000000

90001002、若有一个待排序的无序序列为：｛49,38,65,97,76,13,27,49｝，现用堆排序方法对其排序，

请图示初始堆的建立过程。

三、算法填空题（每空3分，共30分）

1、在以下算法中填上适当的类C程序设计语言语句，使之实现求矩阵M的转置矩阵T的功能。其中：矩阵用三元组表示，mu为矩阵行数、nu为矩阵列数，tu为矩阵非零个数，三元组(i, j, e)表示矩阵第i行第j列的值为e。

Status TransposeSMatrix(TSMatrix M, TSMatrix &T) { ______________(1)_____________; if (T.tu){

for (col=1; col<=M.nu; ++col) num[col]=0;

for (t=1; tfor (col=2; colT.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e; _________(5)___________; }//for }//if

return OK;

}// TransposeSMatrix

4

2、完成以下算法，使之实现功能：给有向无环图G中每个顶点赋以一个自然数序号，并

满足以下条件：若从顶点i至顶点j有一条弧，则应使i>j。

注释：有向图的存储结构为邻接表，且在头结点中增加二个数组：一个存放顶点入度的

数组（indegree），一个存放本算法生成的顶点序号No。另设一栈S暂存所有入度为零的顶点。

Status SortDAG( Algraph G) { F对各顶点求入度indegree[0..vexnum-1] InitStack(S);

for (i=0; iif (!indegree[i]) _________(6)__________; ________________(7)______________;

while (_______________(8)___________) { PoP(S,i); No[i]=count; --count;

for (p=G.vertices[i].firstarc; _________(9)________ ; p=p->nextarc) { k=p->adjvex;

if (!(_______________(10)_____________)) Push(S,k); } //for }//while

if (count>0) return ERROR; else return OK; } // SortDAG

(16分)

设计一个递归算法，计算二叉树中叶子结点的数目。 5

四、算法设计题