2016全国计算机四级论述题（数据库）

　　1.(1997年)本题要求设计一个学生试卷成绩输入、查询和成绩单输出系统(简称SRS)的数据结构和算法要点。问题描述如下：

要输入到SRS系统中的每一份试卷成绩反映一个学生选修一门课程的考试结果，它包括以下数据项：学号、姓名、课程名、成绩。由于实行了灵活的选课制度，所以每个学生选修多少门课程，选修哪些课程都可以不同。要输入的多份试卷成绩并未按任何数据项排列顺序，它们以任意的顺序被输入到系统中来。

SRS系统要具有以下功能：①试卷成绩插入，将试卷成绩逐个插入到SRS系统的数据结构中。②学生成绩查询，给出学号查找该学生所选修的各门课程的考试成绩。③成绩单输出，按学号递增的顺序依次输出所有学生的学号、姓名，及其所选修的各门课程的课程名和成绩。(为简单起见，假设上述所有工作都在计算机内存中进行。)

请设计SRS系统的数据结构和算法要点，使上述三项操作都有较高的执行效率。从以下方面阐述你的设计：

(1)SRS系统的数据结构(15分)

①数据结构的Pascal语句描述

②数据结构的示意图

③数据结构的简单文字说明

(2)SRS系统的算法要点(10分)

(只要简单的`文字说明，不必写出Pascal程序)

①试卷成绩插入

②学生成绩查询

③成绩单输出

(3)简单陈述你的上述设计的理由(5分)

答案:

本题可有多种不同的设计方案，下面给出其中一个较好的方案。

(1)数据结构(15分，其中对三种操作的有效支持各4分，叙述的条理性3分。)

①数据结构的Pascal语句描述

TYPEpptr=↑pnode;

pnode=RECORD

cname:string;

score:0..100;

next:pptr

END;

sptr=↑pnode;

snode=RECORD

sno:integer;

sname:string;

llink,rlink:sptr;

plink:pptr

END;

VARt:sptr;

②数据结构的示意图

9508027Liu٨٨

OS72

OS60

9408023Fang٨٨

9508091Chen ٨

9508010Li

DS85

DB66٨

SE89

AI92٨

DS90

OS95

t

③数据结构的简单文字说明

每个学生结点包含学生的学号和姓名，所有学生结点组织成一棵二叉排序树，用link-rlink法存储。

每份试卷成绩作为一个链表结点，包含课程名和成绩，每个学生的所有试卷成绩结点链接成一个单链表，并且二叉排序树的学生结点中有一个指针指向该单链表的第一个结点。

(2)算法要点(10分，三种操作各3分，叙述的条理性1分)

①试卷成绩插入，根据试卷的学号在二叉排序树中查找该学生结点。若找到，则在该学生结点所指的成绩链表中插入一个成绩结点;若未找到，则先在二叉排序树中插入一个新的学生结点，然后再往这个学生结点所指的(空的)成绩链表中插入一个成绩结点。

②学生成绩查询，根据所给学号在二叉排序树中查找该学生结点，再在该结点所指的成绩链表中沿着指针读出所有成绩。

③成绩单输出。对二叉排序树进行对称序周游，在访问到每个学生结点时输出该结点指向的成绩链表中的所有成绩。

(3)设计理由(5分)

①学生结点组织成二叉排序树，使三种操作都有较高的效率:插入n个学生结点O(nlog2n),查找一个学生结点O(log2n),输出所有学生结点O(n)。

②每个学生的所有成绩结点组织成链表，动态空间，适合于每个学生选修的课程数不等的实际情况，节省空间。

　　2.(1998年)

人们在实践中发现，数据库技术是信息资源的整理、保存、管理和使用的最有效的手段。数据库按其数据结构模型分类，通常可分为层次型数据库、型数据库、关系型数据库和面向对象型数据库，各种类似的数据模型都有自身的特点。试从关系数据模型的优点和弱点论述：

(1)为什么人们在开发以事务处理为主的信息系统(例如管理信息系统)时，大多选用关系型数据库作为开发环境?(18分)

(2)在许多含有复杂数据结构或丰富语义的实际应用领域中，为什么要选用面向对象数据库或要对关系型数据库作某些扩充和修改?(12分)

答案:

(1)首先，关系数据模型结构简单，为二维表格结构与目前事务处理系统中数据多以二维表格结构组织和表示相适应。(10分)

其次，关系数据模型的其他优点也适应事务处理的要求：

①表格是一集合，因此集合论等知识可以引入关系型数据模型中，使它具有坚实的数学理论基础。(4分)

②有简单、易懂`易学的关系数据库的标准语言SQL的支持。(2分)

③数据具有较高的独立性。(2分)

(2)在含有复杂数据结构或丰富语义的实际应用领域中，一般选用面向对象数据库，或要对关系数据库作某些扩充和修改是因为：

①关系数据模型不擅长于表示复杂对象数据类型。(4分)

②也不擅长于表示实体间的语义联系。(4分)

③而面向对象数据模型在这两方面有优势。(4分)

3.(2000年)设计一个用于管理会议室的数据库。经调查分析，得到的数据项列出如下：

房间号r#CHAR(4)，部门号d#CHAR(3)，部门名称dnameCHAR(20)，

房间容量contentINT，部门主管dmanagerCHAR(8)，开会日期mdateDATE，

会议名称cnameCHAR(20)，会议主题(subject)CHAR(80)，会议类型(type)，

部门人数dnumINT，当前房间状态stateCHAR(1)，

并确定以会议室(room)信息，部门(department)信息，会议(conference)信息为实体，它们通过“开会(meeting)”联系起来。为了简化问题做如下假定：

l 会议以部门召开，但一个部门在同一会议室不能重复召开同一个会议。

l 会议室按部门借用，且不预借。

l 当前房间状态取值为‘1’表示该会议室当前正在开会，取值为‘0’表示该会议室当前未被借用。

数据库概念设计的只包含主键属性的简化E-R图如下：

cname

r#

会议conference

房间room

部门department

d#

开会meeting

m

n

p

要求：

⑴数据库的逻辑结构设计：给出相应的表名、表的属性名(数据类型可省)、主键。(14分)

⑵给出下列查询的SQL语句：(16分，每小题4分)

a)当前未借用的会议室(房间号)和容量：

b)2000年4月8日有哪些部门(部门名称)在开会?他们的主管是谁?

c)2000年4月8日‘信息中心’在哪个会议室(房间号)开会?会议名称和主题是什么?

d)当前能够适合‘信息中心’开会的有哪些会议室(房间号)?

答案:

(1)数据库的逻辑结构设计(给出相应的表名,表结构,主键;(14分)

room(r#,content,state)主键:r#(3分)

department(d#,dname,dmanager,dnum)主键:d#(3分)

conference(cname,subject,type)主键:cname(3分)

meeting(r#,d#,cname,mdate)主键(r#,d#,cname)(5分)

(2)给出下列查询的SQL语句:(16分,每小题4分)

a)当前未借用的会议室(房间号)和容量:

selectr#,contentfromroomwherestate=’0’

b)2000年4月8日有哪些部门(部门名称)在开会?他们的主管是谁?

Selectdname,dmanagerfromdepartmentd,meetingm

whered.d#=m.d#andmdate=’2000年4月8日’

或

Selectdname,dmanagerfromdepartmentd

whered.d#=in(selectm.d#=frommeetingmWheremdate=’2000年4月8日’)

c)2000年4月8日’信息中心’在哪个会议室(房间号)开会?会议名称和主题是什么?

Selectr#,e,subjectfromdepartmentd,meetingm,conferencec

whered.d#=m.d#e=eand

Mdate=’2000年4月8日’anddname=’信息中心’

或(注:本题中Selectr#,e,......也可以是Selectr#,e,......

Selectr#,e,subjectfrommeetingm,conferencec

WhereMdate=’2000年4月8日’e=eand

m.d#=(selectd.d#fromdepartmentdwheredname=’信息中心’)

d)当前能够适合’信息中心’开会的有哪些会议室(房间号)?

Selectr#fromroomwherestate=’O’and

content>=(selectdnumfromdepartmentwheredname=’信息中心’)