搜索
++QQ:36242702013年山东大学软件专业复试笔试部分第1页共9页2013年山东大学软件专业复试笔试部分第一部分：操作系统概念一、简答题1、在一个请求分页系统中,假如一个作业的页面走向为：4,3,2,1,4,3,5,4,3,2,1,5。当分配给该作业的物理块数M为4时,分别采用最佳置换算法、LRU和FIFO页面置换算法,计算访问过程中所发生的缺页次数和缺页率。答：最佳置换算法的情况如下表：页面走向432143543215物理页0444441物理页133333物理页22222物理页3155缺页否YYYYYY缺页次数为6，缺页率为6/12LRU置换算法的情况如下表：页面走向432143543215物理页044444445物理页13333333物理页2225511物理页311222缺页否YYYYYYYY缺页次数为8，缺页率为8/12FIFO算法的情况如下表：页面走向432143543215物理页04444555511物理页1333344445物理页222223333物理页31111222缺页否YYYYYYYYYY缺页次数为10，缺页率为10/122、描述哲学家进餐问题，并给出一种解决方法问题描述一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭，如图2-10所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。为了防止死锁的发生，可以对哲学家进程施加一些限制条件，比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号，要求奇数号哲学家先抓左边的筷子，然后再转他右边的筷子，而偶数号哲学家刚好相反。正解制定规则如下：假设釆用第二种方法，当一个哲学家左右两边的筷子都可用时，才允许他抓起筷子。semaphorechopstick[5]={1,1,1,1,1};//初始化信号量++QQ:36242702013年山东大学软件专业复试笔试部分第2页共9页semaphoremutex=l;//设置取筷子的信号量Pi(){//i号哲学家的进程do{P(mutex);//在取筷子前获得互斥量P(chopstick[i]);//取左边筷子P(chopstick[(i+1)%5]);//取右边筷子V(mutex);//释放取筷子的信号量eat;//进餐V(chopstick[i]);//放回左边筷子V(chopstick[(i+l)%5]);//放回右边筷子think;//思考}while(1);}此外还可以釆用AND型信号量机制来解决哲学家进餐问题。3、cache有什么用处cache高速缓冲存储器一种特殊的存储器子系统，其中复制了频繁使用的数据以利于快速访问。存储器的高速缓冲存储器存储了频繁访问的RAM位置的内容及这些数据项的存储地址。当处理器引用存储器中的某地址时，高速缓冲存储器便检查是否存有该地址。如果存有该地址，则将数据返回处理器；如果没有保存该地址，则进行常规的存储器访问。因为高速缓冲存储器总是比主RAM存储器速度快，所以当RAM的访问速度低于微处理器的速度时，常使用高速缓冲存储器。4、cache和缓存的区别(1)Cache：缓存区，是高速缓存，是位于CPU和主内存之间的容量较小但速度很快的存储器，因为CPU的速度远远高于主内存的速度，CPU从内存中读取数据需等待很长的时间，而Cache保存着CPU刚用过的数据或循环使用的部分数据，这时从Cache中读取数据会更快，减少了CPU等待的时间，提高了系统的性能。Cache并不是缓存文件的，而是缓存块的(块是I/O读写最小的单元)；Cache一般会用在I/O请求上，如果多个进程要访问某个文件，可以把此文件读入Cache中，这样下一个进程获取CPU控制权并访问此文件直接从Cache读取，提高系统性能。(2)Buffer：缓冲区，用于存储速度不同步的设备或优先级不同的设备之间传输数据；通过buffer可以减少进程间通信需要等待的时间，当存储速度快的设备与存储速度慢的设备进行通信时，存储慢的数据先把数据存放到buffer，达到一定程度存储快的设备再读取buffer的数据，在此期间存储快的设备CPU可以干其他的事情。Buffer：一般是用在写入磁盘的，例如：某个进程要求多个字段被读入，当所有要求的字段被读入之前已经读入的字段会先放到buffer中。5、写出学过的磁盘管理方法，问：磁带用什么方法管理好。（1）磁盘格式化（2）引导块（3）坏块磁带管理方法，如螺旋扫描技术。++QQ:36242702013年山东大学软件专业复试笔试部分第3页共9页6、进程和线程进程：进程是一个具有一定独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单元。动态性：进程是一个动态的概念，而程序是一个静态的概念。程序是指令的有序集合，其本身没有任何运行的含义。而进程是程序在处理机上的一次执行过程，具有生命期，它动态的被创建，并被调度执行，执行完成后销往。并发性。独立性。制约性：主要表现在护持的使用资源和相关进程之间必要的同步和通信。结构性：进程由程序、数据集合和描述其运行过程的数据结构（PCB）组成。线程：进程的引入可以实现并行计算，线程的引入可以进一步提高系统的并发性。一个进程可以拥有多个线程，这些线程共享同一地址空间，他不拥有系统资源，且只需要很少在运行时必不可少的硬件，因此线程在创建，撤销，切换等环节所需要的时空开销比进程要少的多。联系：调度分派。线程是可调度的工作单元，在有线程的进程中，进程不再成为调度的基本单位。资源拥有。进程拥有资源，线程不拥有资源，只是使用进程的资源。地址空间。不同进程的地址空间是相互独立的，同一进程的各线程共享同一地址空间。一个进程可以拥有多个线程，反过来不行。通信关系。进程间的通信需要使用系统的通信机制，同一进程中的各线程可以通过直接读写数据段（如全局变量）来进行通信。7、根据如下死锁状态图，判断是否有死锁，并简述理由解：存在死锁理由：首先看P1，P1申请资源1，但资源1只有1个，且被P2占用，所以P1被阻塞，无法删除P1的边；接着看P2，P2申请资源4，同理，资源4只有一个且被P3占用，所以P2的边也不能删除；最后P3，P3申请资源3和2，资源3有2个，其中一个被P2占用，剩余一个空闲资源，可被P3申请，但资源2中，一个被P1占用，另一个被P3占用，无空++QQ:36242702013年山东大学软件专业复试笔试部分第4页共9页闲资源，所以P3也被阻塞。无法删除P3的边。三个结点经分析后都不能化简为孤立结点，所以形成死锁。第二部分：数据库系统概论一、事务的定义及特点。事务是用户定义的一个数据库操作序列，这些操作要么全做要么全不做，是一个不可分割的工作单位。事务具有4个特性：原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)和持续性(Durability)。这4个特性也简称为ACID特性。原子性：事务是数据库的逻辑工作单位，事务中包括的诸操作要么都做，要么都不做。一致性：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。隔离性：一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能互相干扰。持续性：持续性也称永久性(17ermanence)，指一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其执行结果有任何影响。二、两段锁协议及其特点。两段锁协议是指每个事务的执行可以分为两个阶段：生长阶段（加锁阶段）和衰退阶段（解锁阶段）。加锁阶段：在该阶段可以进行加锁操作。在对任何数据进行读操作之前要申请并获得S锁，在进行写操作之前要申请并获得X锁。加锁不成功，则事务进入等待状态，直到加锁成功才继续执行。解锁阶段：当事务释放了一个封锁以后，事务进入解锁阶段，在该阶段只能进行解锁操作不能再进行加锁操作。三、空值（null）定义及特点。数据库中，空值表示值未知。空值不同于空白或零值。没有两个相等的空值。比较两个空值或将空值与任何其他值相比均返回未知，这是因为每个空值均为未知。四、简述参照完整性。参照的完整性要求关系中不允许引用不存在的实体。与实体完整性是关系模型必须满足的完整性约束条件，目的是保证数据的一致性。参照完整性又称引用完整性。五、根据关系画出E-R图,把E-R图转化成关系模式并进行模式合并和优化，如下++QQ:36242702013年山东大学软件专业复试笔试部分第5页共9页将E-R图转化为表：实体转化成表d(dno,dname)c(cno,cname,property)s(sno,sname,age,sex)t(tno,tname,age,sex)联系转化为表sd(sno,dno)td(tno,dno)sc(sno,cno,score)tc(tno,cno,time)表的合并s+sds(sno,sname,age,sex,dno)t+tdt(tno,tname,age,sex,dno)合并表后的关系模式d(dno,dname)c(cno,cname,property)s(sno,sname,age,sex,dno)t(tno,tname,age,sex,dno)sc(sno,cno,score)tc(tno,cno)六、设有如下关系模式：student(NO,NAME,SEX,BIRTHDAY,CLASS)teacher(NO,NAME,SEX,BIRTHDAY,PROF,DEPART)PROF为职称，DEPART为系别course(CNO,CNAME,TNO)++QQ:36242702013年山东大学软件专业复试笔试部分第6页共9页score(NO,CNO,DEGREE)DEGREE为成绩写出实现以下各题功能的SQL语句：（1）查询至少有2名男生的班号；SelectCLASSfromstudentwhereSEX=’男’GroupbySEXHavingCount(*)=2；（2）查询每个学生的姓名和年龄；SelectNAMEyear(date())-year(BIRTHDAY)asageFromstudent；（3）查询最高分同学的学号，课程号和成绩；Select*fromscorewhereDEGREE=(selectmax(DEGREE)fromscore)；（4）查询所有未讲课的教师的姓名和所在系别；SelectNAMEDEPARTfromteacherwhereNOTEXISTS(select*fromscorewhereteacher.NO=score.TNO)；（5）查询“计算机系”教师所教课程的成绩表；Select*fromscorewhereCNOIN(selectCNOfromcoursewhereTNOin(selectTNOfromteacherwhereDEPART=’计算机系’))；七、范式运算设关系模式RU,F，其中U=｛A,B,C,D,E｝，F＝{A→BC，C→D，BC→E，E→A｝，则分解ρ={R1（ABCE），R2（CD）｝是否满足无损连接性、保持函数依赖？解：先做无损链接的判断。R1∩R2={C}，计算C+。Result=C由于C→D，C∈result，所以result=result∪D=CD可见C是R2的超码，该分解是一个无损分解。再做保持依赖的判断。A→BC，BC→E，E→A都在R1上成立（也就是说每一个函数依赖左右两边的属性都在R1中），C→D在R2上成立，因此给分解是保持依赖的。第三部分：软件工程导论一、增量模型的特点和适用情况优点：能在较短时间内向用户提交可完成部分功能的产品逐步增加产品功能可以使用户有较充裕的时间学习和适应困难：在把每个新的增量构件集成到现有的软件体系结构中，必