一.单项选择题.(每题2分,共8分)
1.对由n个记录组成的文件排序,如果n较小(n<50)且记录的规模较大,则采用()排序方法节省时间.
A.直接插入
B.直接选择
C.快速
D.堆
2.假定有K个关键字互为同义词,若用线性探测法把这些同义词存入散列表中,至少要进行()次探测.
A.K
B.K2(K的平方)
C.1/2K(K-1)
D.1/2K(K+1)
3.二维数组a[0…8,1…10]按行存放时元素a[8,5]的起始地址与按列存放时元素()的起始地址相同.
A.a[8,5]
B.a[3,10]
C.a[5,8]
D.a[0,9]
4.有6个元素按6,5,4,3,2,1的顺序进栈,下列()不是合法的出栈序列.
A.5,4,3,6,1,2
B.4,5,3,1,2,6
C.3,4,6,5,2,1
D.2,3,4,1,5,6

二.填空题(每题3分,共12分)
1.设P指向二叉树中某个S结点,结点有二个指针域lchild与rchild分别指向该结点的左,右孩子,则执行下列语句可找到结点P?的中序(对放序)后继结点q?(假定该后继结点存在):q:=p?.rchild;______________
2.高度为6的AVL树至少有________结点.(设空二叉树高度为0)
3.用数组Q[0..n-1]存放循环队列,f,r分别为队头,队尾指针,则队列长度的计算公式是__________.队列长度的最大值是____________.
4.高度为h的完全二叉树上至少有_______个结点,至多有_______个结点.

三.简答与画图题(共24分)
1.设二叉树的后根序列为HDEBIFGCA,中根序列是DHBEAIFCG,画出此二叉树和它所对应的森林.(9分)
2.顺序查找,二分法查找和分块查找三种方法对查找表中元素各有什么要求?平均的查找长度各是多少?(假设查找表的长度为n.)(9分)
3.图的广度遍历算法中既可以在一个点入队时对其访问,也可以在顶点出队时对其访问,请问前一种方法有何优点?后一种方法可能产生什么问题?并以下图为例说明.(6分)
V0
V1 V2………Vn
Vn+1

四.算法题.(共31分)
1.清除重复结点.单链表中数据域的值相同的结点称为重复结点.如线性表(2,1,1,3,2,1,)清除重复结点后为(2,1,3).试用C语言写一函数清除单链表head中的重复结点,并指出每个工作指针的作用.(15分)
2.找第k项.n个元素的第k项是把它们从小到大的排序后的第k个元素.如(16,12,99,95,18,87,10)的第4项是18.假定n个整数放在数组a[1..n]中,试写一算法,不经对整个数组排序,找到第k项.并写出此算法在最好和最坏情况下的时间复杂度.(提示,利用快速排序中的划分方法.)(16分)

操作系统部分
一.名词解释(每题2分,共10分)
1.分时与分时系统
2.进程控制块
3.系统颠簸(抖动)
4.位示图
5.设备驱动程序

二.简答题(每题4分,共20分)
1.操作系统的基本特征是什么?
2.什么叫联想存储器?设CPU给出有效地址为(P.D),其中P表示页号,D表示页内位移量,试说明利用联想存储器实现动态地址变换的过程.
3.文件存储空间管理有哪几种常用的方法?
4.试给出两种I/O调度算法,并说明为什么在I/O调度中不能采用时间片轮转法?
5.试说明信号量的物理意义?

三.单项选择题(每题1分,共10分)
1.存储器的段页式管理中,每次从主存中取出一条指令或一个操作数,需要()次访问主存.
A.1
B.2
C.3
D.4
2.设有n个进程共用一个相同的程序段(临界区),如果每次最多允许m个进程(m<n)同时进入临界区.则信号量的初始值为().
A.n
B.m
C.m-n
D.n-m
3.在操作系统中,一方面每个进程具有独立性,另一方面进程之间又具有相互制约性.对于任何两个并发进程,它们()
A.必定无关
B.必定相关
C.可能相关
D.可能相同
4.一个虚拟存储器系统中,设主存的容量为16MB,辅存的容量为1GB,而地址寄存器的位数32位.在这样的系统中,虚存的最大容量是().
A.1GB
B.16MB
C.1GB+16MB
D.4GB
5.采用直接存取法来读写磁盘上的物理记录时,效率最高的是()
A.连续结构的文件
B.索引结构的文件
C.链接结构文件
D.其他结构文件
6.下列算法中可用于进程调度,磁盘调度,I/O调度的是()
A.先来先服务
B.SSTF服务
C.时间片轮转
D.优先级高者优先
7.通道又称I/O处理机,它能完成()之间的信息传输.
A.主存与外设
B.CPU与外设
C.外设与外设
D.主存与CPU
8.死锁的4个必要条件无法破坏的是().
A.互斥条件
B.请求与保持条件
C.非抢夺条件D循环等待条件
9.文件系统采用多级目录结构后,对于不同用户的文件,其文件名().
A.应该相同
B.应该不同
C.可以不同,也可以相同
D.受系统约束
10最容易开成很多小碎片的可变分区分配算法是().
A.首次适应算法
B.最佳适应算法
C.最坏适应算法
D.以上算法都不会

四.改错题(划出下列句子中的错误的地方并改正,简单的否定无分.每小题2分,共10分)
1.进程有三个状态:运行态,就绪态和等待态.
2.在分区存储管理方案中,作业的大小只受主存加辅存之和大小的限制,可以实现虚拟存储.
3.如果CPU正在执行一个P操作的时候,一个最高级中断到来,那么中断处理进程会抢夺CPU.
4.为了正确地按名存取,操作系统规定不同的文件均不能有相同的文件名.
5.通常,一个CPU可以连接多个通道,一个通道可以连接多个设备控制器,一个设备控制器可连接多台外围设备.

五.计算题(25分)
1.设有两个优先权相同的进程,P1,P2如下,令信号量S1,S2的初值均为0,已知Z=2,试问,P1,P2执行结束后,X=?,Y=?,Z=?(6分)
进程P1 进程P2
. .
. .
. .
Y:=1; X:=1;
Y:=Y+Z; X:=X+1;
V(S1); P(S1);
Z:=Y+1; X:=X+Y;
P(S2); V(S2);
Y:=Z+Y; Z:=X+Z;
. .
. .
. .
2.设在单机系统内存中存放三道程序A,B和C,按A,B,C的优先次序运行,其内部计算机I/O操作的时间分配如下图所示.
程序A计算30m->I/O40ms->计算10ms
程序B计算60m->?I/O30ms->计算10ms
程序C计算20m->?I/O40ms->计算20ms
试画出按多道运行时的时间关系图(设有两个通道,取名为通道1,通道2,调度程序的执行时间忽略不计),并计算完成这三道程序共花多少时间及比单道程序运行节省多少时间.(9分)
3.桌子有一个盘子,每次只能放入一个水果,爸爸专向盘中放苹果,妈妈专向盘中放桔子,女儿专等吃盘中的苹果,儿子专等吃盘中的桔子.试用P,V操作写出他们能正确同步的并发程序.(10分).