(完整版)山大历年计算机复试笔试题

充一下：

数据库的第二个大题第一问是：R的一个候选码。这个题候选有多个，求一个就行2009-2010

第二学期离散数学（2） 练习一

1、证明在任何有向完全图中，所有顶点入度的平方之和等于所有顶点出度的平方之和。（有向完全图是指无向完全图是底图的有向图）。 2、若图G是不连通的，则G的补图是连通的。

3、画一个有一条Euler回路但没有Hamilton回路的图；画一个没有Euler回路但有一条Hamilton回路的图。

4、假设G是由超过11个顶点构成的简单连通图。证明图G或G的补图是非平面图。

5、假设T是非平凡的无向树，T中度数最大的顶点有2个，并且它们的度数k都大于等于2。证明：T 中至少有2k?2片叶。

1.

2007年计算机复试题目

2. 第一部分 离散数学

1.设A,B为非空集合,ρ(A)=ρ(B),求证A=B

2.S＝{|存在z 使得xRz且zRy} 求证若R为等价关系，则S为等价关系

3.从以下题目中任选一道，多选按最低分计算

(1)设为群,R为G上等价关系且对任意x,y,z∈G,若(x*z)R(y*z), 则xRy 设H={h|h∈G且hRe},求证为的子群

(2)没做，所以不大清楚

4.设T为非平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2

5.一个推理理论的题目.

前提：1.所有学生都得参加考试； 2.通过考试的学生都很高兴；

3.所有学习努力的学生都可以通过考试； 4.有些学生学习努力；

结论：有些学生高兴

第二部分 操作系统 1.名词解释 死锁 原语 系统调用 地址重定位 进程控制块 2.简答

1)进程和线程的联系与特点

2)描述哲学家就餐问题,并给出一种解决方法的程序

3)硬实时系统为什么没有辅助存储器？为什么没有虚拟存储器?为什么没有一般操作系统的大部分功能

4)叙述I/O轮询,中断和DMA的各自特点和优缺点 5)进程调度算法主要有哪几种,并评价其的优缺点

三四部分选做其中之一，如果都做按组成原理算分

第三部分 组成原理

没做，所以也不大清楚了

第四部分 数据库系统概论

1、简述事务的定义以及其主要特点

2、画E-R图

主要是图书馆信息系统，有读者、书籍、管理员。读者要查询书籍、管理员要修改读者信息、管理员要更改借阅信息。

给几个关系及其中元组,求给定查询表达式的值

3、给定关系模式R(A,B,C,D)，其上函数依赖F＝{a-c,c-a,b-ac,d-ac} (1)计算（AD）＋ (2)求Fc

(3)计算R的一个候选码；

(4)将R分解为一个BCNF，且要求无损连接性。

4五道代数运算题目，比较简单

5、有如下关系:S(SNO,SNAME),C(CNO,CNAME),SC(CNO,SNO,SCORE) SNO=学号,SNAME=学生姓名,CNO=课程号,CNAME=课程名,SCORE=分数