山大历年计算机复试笔试题

充一下：

数据库的第二个大题第一问是：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=分数

写出以下查询或者修改

1姓名为张明的学生选修的课程的课程号

2选修了学号为10005的学生所修所有课程的学生学号 3所修课程有5门成绩>=90分的学生学号 4所有课程名为数据库系统概论的成绩+10分

3. [他院] 2008年计算机复试试题第一部分离散数学

1，f是A到B上的双射，g是C到D上的双射，有H{|}证明AxC->BxD也是双射（好像是这么回事）

2，证明树的边数等于定点数减一

3，R为A上的等价关系，证明RoR也是定价的 4，n>=2有一系列的数为点的度，d1，d2，d3，d4……dn，且d1+d2+d3+d4+……+dn=2n-2； 证明：存在顶点度为d1，d2，d3，d4……dn的树 第二部分 操作系统

1，进程的定义，状态，状态的转换，转换的条件 2，死锁简述以及相关避免方法，并简述银行家算法

3，pv操作的定义，为什么用原子操作?简述哲学家就餐问题

4，页面置换算法，有三个内存块，有LRu算法，计算以下的缺页数，7012030423032； 什么是虚拟存储系统的抖动！它的主要原因有哪些？ 第三部分 数据库

1，事务的定义；参照完整性；两段协议定义 2，R{sno,sname,cno,cname,bno,bname,tno,tname,}

F{sno->sname;cno->cname;tno->tname,cno,cname;bno->bname;sno,sname,cno,cname->tno,tname}求

1）Fc2）候选码3）bcnf，3nf

3，关系运算（没有记下来）挺简单 4，sql查询

第四部分 组成原理

1，存储器的扩展，以及与cpu的连接 2，JSR（R1）+的操作流程，数据通路 3，关于微程序的（我没有复习，不会写）

ps：操作系统有几个题是本科的考试题 其余的就不太清楚了

有的地方不完整，希望各位补充一下阿

这两天没上网,题目都快忘干净了,趁现在还有些印象,发几个. 笔试: 他院] 09计算机学院复试题目回忆

离散数学;每题十分

1:两个集合A,B,P(A),P(B) 是其幂集,若A是B的子集,证明P(A)是P(B)的子集。

2:假设关系R在集合A上是自反的,且对于任意a,b,c属于A,若属于R,则有属于R,证明R是等价关系

3:假设是群,对于任意a属于G,H={y|y*a=a*y,y属于G},证明是的子群。【这个是上海科学技术文献出版社左孝凌版教材原题:习题5-4(3)】

4:设T为非平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2【这一个是07年原题】

5:一个推理理论的题目.【原题记不住了,不过很简单】离散数学 5推理

1)有些人是学生 2)有些学生通过考试

3}所有通过考试的学生会高兴 推出:有些人会高兴

(p(x):x是人 s(x):x是学生 h(x):x高兴 e(x):x通过考试) 大意是这样,挺简单的.

数据库部分:

【1】10分:每个车间有车间号,地址,电话,有多个职工,且每个职工只能在一个车间工作,职工有职工号,性别,年龄,工种,每个车间有一个车间主任。每个车间可以生产多种产品。且每种产品只能在一个车间生产,产品有产品号,价格。一个产品可以有多种零件组成,每种零件可以组成多种产品。

1:根据语义画出E-R图 2:将上图转化成关系模式 【2】5分

u={A,B,C,D}关系依赖集F={A->B,A->C},将其转换为BCNF,且保持函数依赖和无损连接性。

【3】35分 1:

有学生信息表s,课程表c,选课表sc

给出3个表达式,写出查询结果,每个5分;

(1)snoG[AVG]SC(SCORE).注:AVG是下标,我不会打所以用括号括起来了。 (2) (3)

2:写出以下四个语句的SQL,不要求写出结果,每个5分 1. 2.

3.查询没有选修课程c2的学生学号

4.查询选修了学号为s2的同学选修的所有课程的学生学号 信息安全部分

【1】写出以下定义,任选其中5个,每个2分

MAC,SSL,digital certificate,Firewall,VPN(只记住了我选得5个,另外2个没记住) 【2】5*8

1:分组对称加密算法加密任意长度的明文信息时有几种模式,各有什么特点。 2:RSA加密算法的基本原理,安全性如何?