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

(word完整版)山大历年计算机复试笔试题
充一下：
数据库的第二个大题第一问是: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 中至少有片叶.

1.
2007年计算机复试题目
2. 第一部分 离散数学

1.设A,B为非空集合,ρ（A）=ρ（B）,求证A=B

2。S＝｛<x,y〉|存在z 使得xRz且zRy｝
  求证若R为等价关系，则S为等价关系

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

（1)设<G,＊〉为群,R为G上等价关系且对任意x，y,z∈G，若(x＊z)R(y＊z), 则xRy
设H=｛h｜h∈G且hRe},求证<H，*>为<G，*>的子群

(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〉|}证明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，若〈a,b>〈a,c>属于R，则有〈b，c>属于R，证明R是等价关系
3:假设〈G，*〉是群,对于任意a属于G,H={y｜y*a=a*y,y属于G}，证明<H,＊〉是〈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加密算法的基本原理，安全性如何？
3effie—Hellman加密算法的基本原理,安全性如何？
4：好的hash函数有什么特点？在密码学中有什么应用？【4月15日补充】
5:链路加密和端到端加密有什么特点？

山东大学2010年计算机考研复试笔试试题及面试经历
　　离散数学：
　　1：集合A非空，有A*B=A*C 求证:B=C
　　2.符号化下列语句，并证明.
　　（1)一切自然数都是整数
　　（2）存在有理数不是整数
　　结论：存在既不是整数也不是自然数的有理数
　　3。等价
　　是群,H，K是G的子群,定义关系R如下：
　　aRb 当且仅当存在h属于H，k(小写）属于K，满足b=h*a*k
　　求证：R为等价关系
　　4。同构映射
　　题目：为群，定义f为A到A上的映射，a，b属于A，其中f（x)=a＊x＊b
　　证明 f为同构映射
　　5。图
　　题目：图G是简单平面图，|V|=7，|E|=15，求证:G是单连通图
　　数据库
　　跟往年题型差不多，但是本人做的最烂的，出的题还不错
　　1.
　　学生（学号，姓名，性别，年龄)
　　教师（教师编号，课程)
　　课程（课程编号,名称）
　　规定每一个学生属于一个班级，而一个班级统一选修课程.
　　学生有自己的课程分数，每一位教师教授一门课。。.
　　(1)画出E—R图
　　（2）写出关系模型,并且符合某种范式
　　2。某集合G{A,B,C,D，E}满足如下函数依赖
　　AB—>C
　　C—〉B
　　D—>E
　　问：
　　(1）G的一个候选码
　　（2）将G进行无损连接BCNF分解
　　（3)将G进行既符合无损连接有保持函数依赖的3NF分解
　　3。 题目太长 参照往年的
　　有9问，
　　1—-4问 根据关系运算写出结果
　　5——9问 写SQL语句 参照07年的

　　 处好好准备下.

4.