北航计算机（操作系统）2001
北京航空航天大学数据库与操作系统试题
(2001年)
一、请给出以下名词的定义(2’x5)
1.实体 2.关系 3.关系键 4.传递函数依赖 5.关系规范化
二、问答题(4’x2)
1.试述相对于文件系统来说，数据库系统具有哪些优点。
2.试数数据独立性的概念，以及数据库系统是如何实现数据独立性的。
三、设有如下关系(2’x4)
R S T
A B C D A B C D C D
a1 b1 c1 3 a1 b2 c3 6 c1 3
a1 b1 c2 5 a2 b1 c2 7 c2 4
a1 b2 c3 6
a2 b2 c1 3
a2 b2 c2 4
a3 b3 c3 8
试求：
1. 2.R-S 3. 4.
四、(3’x2)
设R(ABC)和S(DE)，其中B，C，D来自同一个域，请把表达式 转换为：
1.元组演算表达式
2.SQL语言
五、试证明：(3’x2)
1.若存在函数依赖X→Y及W→Z，则必有函数依赖XW→YZ。
2.若存在函数依赖X→YZ及→CW，则必有函数依赖X→CWYZ。
六、设有一个投资股票公司的数据库，它包含以下属性：(4’x3)
B(broker，即经纪人)
O(office，即经纪人工作的办公室)
I(investor，即投资人)
S(stock，即投资人所拥有的某种股票)
Q(quantity，即投资人所拥有的上数股票数量)
D(dividend，即股息，上述股票的利息率)
假设有以下函数依赖，S→D，IS→Q，I→B，B→O，请：
1.找出关系模式R(BOISQD)的关系键，请给出求解过程。
2.如果把上述关系模式分解为R1(ISQD)，R2(IBO)，试说明：
a.R1，R2满足的最高范式，为什么？
b.上述两个关系模式存在什么弊端，为什么？
3.找出关系模式R(BOISQD)到3NF的一个无损分解，并给出规范化过程。
七、名词解释题(4’x3)
1.进程 2.临界区 3.重定位
八、判断题(1’x8)
1.在作用调用时，采用最高响应比优先的作业调度算法可以得到最短的作业平均周转时间。( )
2.在虚存系统中只要磁盘空间无限大，作业就能拥有任意大的编址空间。( )
3.在内存为M的分时系统中，当注册的用户有N个时，每个用户拥有M/N的内存空间。( )
4.当一个进程从等待态变成就绪态，则一定有一个进程从就绪态变成运行态。( )
5.由于P、V操作描述同步、互斥等
问题的能力不足，所以有必要引入其它的通讯原语或机制，如send，receive或Monitor等。( )
6.引入当前目录是为了减少启动磁盘的次数。( )
7.是式系统中的作业周转时间有严格的限制。( )
8.磁盘机是一类典型的块设备。( )
九、并发问题(10’)
设有两个优先级相同的进程P1，P2如下。令信号S1，S2的初值为0，已知z=2，试问P1，P2并发运行结束后x=？y=？z=？
进程P1 进程P2
y:=1； x:=1；
y:=y+2； x:=x+1；
V(S1)； P(S1)；
z:=y+1； x:=x+y；
P(S2)； V(S2)；
y:=z+y； z:=x+z；
十、进程同步问题(10’)
面包师有很多面包，由n个销售人员推销。每人顾客进店后先取一个号，并且等待叫号。当一个销售人员空闲下来时，就叫下一个号。试设计一个使销售人员和顾客同步的算法。
十一、设某进程的页面走向为：5、4、3、2、4、3、1、4、3、2、1、5请完成下表：(10’)
进程分得页数缺页次数算法 1 2 3 4
LRU(最近最久不用页面置换)
FIFO
北京航空航天大学数据库与操作系统试题
(2002年)
一、解释下列名词(2’x5)
1.关系模式 2.导出表 3.概念模式 4.连接操作 5.聚集
二、填空题(2’x5)
1.关系的性质要求关系中的任意两元组__________，且任意两个不同的列必须有__________属性名(但可出自同一域)。
2.关系的每个分量必须是__________，这被称为__________关系。
3.在关系模式R(U)中，XÎU，YÎU，X®Y，如果X的任意真子集X’都有X’®Y，则称Y对X的函数依赖是__________，记作__________。
4.满足BCNF的关系将消除任何属性(主属性和非主属性)对键的部分依赖和__________，因此属于BCNF关系必属于__________。
5.关系模型的最大特点在于描述的一致性，不仅用__________描述__________，而且用__________描述__________。
三、问答题(5’x2)
1.试述实体完整性约束和参照完整性约束的定义，并举例说明。
2.试述关系数据库设计的主要步骤和每一步骤需要解决的主要问题。
四、(2’x5)
给定下列三个关系模式：S(S#，SN，SEX，AGE，DEPT)；C(C#，CN)；SC(S#，C#，GRADE)。
其中：
S：学生表；C：课程表；SC：学生选课表；
S#：学号；SN：姓名；SEX：性别；AGE：年龄；DEPT：学生所在系；
C#：课程编号；CN：课程名称；GRADE：学生所选课程成绩。
请写出以下问题的SQL计算序列。
1. 创建S表，C表和SC表(字段名、类型和长度可自定义)，并指出主键；
2. 查询所有学生的姓名、年龄和所选课程的名称；
3. 查询选修了所有课程的学生的姓名；
4. 查询至少选修了3门课程的学生的学号、姓名
和所选课程的门数。
5. 查询所有姓李的学生的姓名、性别、年龄和所在系。
五、(10’)
给定关系模式UN(S#，CN，G，SDN，SL)。
其中：
UN：关系名；S#：学号；CN：课程名；G：成绩；
SDN：所在系名；SL：学生住处。
语义为：(1)一个系有若干学生，但一个学生只属于一个系；
(2)一个系的学生只住在一个住处；
(3)一个学生可选修多门课，每秒可可有若干学生选修；
(4)每个学生学习每门课有一个成绩。
请分析和回答以下问题：
1. 试分析UN的函数依赖关系，画出依赖图，指出主键。
2. 试分析UN模式属于第几范式？存在何种异常。
3. 将UN规范为符合3NF的一组关系模式，其投影分解是无损的且保持原函数依赖关系，要求写出规划化过程。
六、简答题(5’x4)
1.操作系统的基本特征是什么？
2.什么是死锁？死锁的原因是什么？
3.信号量的物理意义是什么？
4.什么是进程？进程的基本特征？
七、判断题(1’x5)
1.当一个进程从等待态变成就绪态，就一定有一个进程从就绪态变成运行态。
2.在请求页式存储管理中，页面淘汰所花费的时间不属于系统开销。
3.在中断处理过程中，必须屏蔽中断。
4.在有虚拟存储器的系统中，可以运行比主存容量还大的程序。
5.打印机是一类典型的字符设备。
八、(10’)
考虑一仅460个字节的程序的下述内存的访问序列(该序列的下标均从0开始)10，11，104，170，73，309，185，245，246，434，458，364且页面大小为100字节，则(1)写出页面的访问序列。(2)假设内存中仅有200字节可供程序使用且采用FIFO算法，那么共发生多少次缺页中断？(3)如果采用最近最久未使用算法(LRU)，则又会发生多少次缺页中断？
九、(10’)
在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用P、V操作实现司机与售票员之间的同步。
十、(5’)
下面是两个并发执行的进程。它们能正确运行吗？若不能请举例说明，并改正之：
parbegin
var x:integer;
process P1 process P2
var y, z:integer; var t, u:integer;
begin begin
x:=1; x:=0;
y:=0; t:=0;
if x≥1 then y:=y+1; if x≤1 then t:=t+2;
z:=y; u:=t;
end end
parend