中科院计算机技术研究所1998年硕士生入学试题
数据结构和程序设计
(要求：算法题目写注解)
一.填空(15分,每空一分)
1.用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是__和__; 若只设尾指针,则出队和入队的时间复杂度分别是__和__.
2.设广义表L=( (),() ) ,则head(L)是___;tail(L)是___;L的长度是___;深度是___.
3.深度为h的完全二*树至少有__个结点;至多有__个结点;h和结点总数n之间的关系是__.
4.在n个记录的有序顺序表中进行折半查找,最大的比较次数是___.
5.在一棵m阶B+树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是___.
6.n个顶点的连通图用邻接矩阵表示时,该矩阵至少有__个非零元素.
二.请在下列各题中选择一个正确的答案(20分,每题2分)
1.算法的时间复杂度取决于
a.问题的规模
b.待处理数据的初态
c.both a and b
2.消除递归不一定需要使用栈,此说法
a.true
b.false
3.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?
a.k-1
b.k
c.k=1
d.k(k+1)/2
4.若需要在O(nlog2(n))的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是:
a.快速排序
b.堆排序
c.归并排序
d.直接插入排序
5.用ISAM和VSAM组织文件属于:
a.顺序文件
b.索引文件
c.散列文件
6.若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列
a.存在
b.不存在
7.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是
a.n
b.2n-1
c.2n
d.n-1
8下述二*树中,那一种满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序:
a.二*排序树
b.哈夫曼树
c.AVL树
d.堆
9.以知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的个元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下限应为:
a.O(klog2(k))
b.O(klog2(n))
c.O(nlog2(k))
d.O(nlog2(n))
10.在叶子数目和权值相同的所有二*树中,最优二*树定是完全二*树,该说法:
a.正确
b.错误
三.设二*排序树T中各结点关键字互不相同,x^是T的叶子,y^是x^的双亲.证明y^.key是T中大于x^.key的所有关键字中的最小者,或是小于x^.key的所有关键字的最大者.(10分)
四.(共15分)设数组A的长度为2N,前N个元素A[1..N]递减有序,后N个元素A[N+1..2N]递增有序,且2N是2的整数次幂,即k=log2(2N) 为整数.例如A[1..8]=[90,85,50,10,30,65,80,100] 满足上述要求,这里N=4,k=3,A的前4个元素和后4个元素分别递减和递增有序.用次例调用如下的Demo过程,并要求: (1).给出for循环中每次执行PerfectShuffle(A,N)和CompareExchange(A,N)的结果.(10分) (2)解释Demo的功能.(2分) (3)给出Demo的时间复杂度.(3分) Procedure PerfectShuffle (Var A:arraytype; N:integer){
i:=1; j:=1;
while i<=N do {
B[j]:=A[i];
B[j+1]:=A[i+N];
i:=i+1;
j:=j+2;
}
A[1..2N]:=B[1..2N];//B copy to A
}
Procedure CompareExchange(Var A:arraytype; N:integer){
j:=1;
while j<2N do{
if A[j]>A[j+1] then
A[j]<->A[j+1];//exchange A[j] and A[j+1]
j:=j+2;
}
}
Procedure Demo(Var A:arraytype; N:integer){
//the length of A is 2N,k=log2(N) is integer
for i:=1 to log2(2N) do
{PerfectShuffle(A,N);
CompareExchange(A,N);
}
}
五.(共20分)
(1).设二*排序中关键字由1至1000的整数构成,现要检索关键字为363的结点,下述关键字序列中那些可能是二*排序树上搜索到的序列,那些不可能是二*排序树上搜索到的序列?(5分)
(a)2,252,401,393,330,344,397,363 (b)924,220,911,244,898,258,362,363
(c)925,202,911,240,912,245,363 (d)2,399,387,219,266,382,381,278,363
(2).通过对(1)的分析,写一个算法判定给定的关键字序列(假定关键字互不相同)是否可能是二*排序树的搜索序列.若可能是返回真,否则返回假.可假定被判定的序列已存入数组中.(15分)
六.(共20分)图的D-搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入出
队列的操作改为入出栈的操作.即当一个顶点的所有邻接点被搜索后,下一个搜索的出发点应该是最近入栈(栈顶)的顶点.
(1)用邻接表做存储结构,写一个D-搜索算法(15分)
(2)用D-搜索方法搜索右图,设初始出发点为1,写出顶点的访问次序和响应的生成树,当从某顶点出发搜索他的邻接点是，请按邻接点序号递增序搜索,以使答案唯一.(5分)
编译原理和操作系统
一.(10分)某操作系统下合法的文件名为device:name.extension其中第一部分(device:)和第三部分(.extension)可缺省,若device,name和extension都是字母串,长度不限,但至少为1,画出实现这种文件名的确定有限自动机.
二.(10分)下面的二义文法描述命题演算公式,为他写一个等价的非二义文法.
S->S and S|S or S|not S|p|q|(S)
三.(10分)把表达式- (a+b)*(c+d)+(a+b+c)翻译成四元式.
四.(10分)由于文法二义引起的LR(1)分析动作冲突,可以根据消除二义的规则而得到LR(1)分析表,根据此表可以正确识别输入串是否为响应语言的句子.对于非二义非LR(1)文法引起的LR(1)分析动作的冲突,是否也可以根据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表,并且根据此表识别相应语言的句子?若可以,你是否可以给出这样的规则?
五.(10分)下面程序的结果是120.但是如果把第5行的abs(1)改成1的话,则程序结果为1.试分析为什么会有这不同的结果.
int fact(){
static int i=5;
if(i=0) {return(1); }
else { i=i-1; return(( i+abs(1))*fact()); }
}
main(){
printf("factor or 5=%d\n",fact());
}
六.名词解释(每小题2分,共10分)
1) 线程2)管程3)管道4)I/O重定向5)动态地址重定位
七.填空(每空0.5分, 共10分)
1.为了赋予操作系统以某些特权,使得操作系统更加安全可靠地工作,实际操作系统中区分程序执行的两种不同的运行状态是___;___态程序不能执行特权指令.
2.引起进程调度的原因有:___,___和___.
3.在一个请求式页式存储系统中,一个程序的页面走向为1,2,1,4,3,2,3,5,1,2,1,3.假定分配给该程序的存储块数为4,则采用FIFO,LRU和LFU 页面置换算法时,访向过程中的缺页次数分别为___,___和___.
4.通道技术的引入,实现了___与___的并行;___与___的并行;___与___的并行.
5.设备分配程序除了向提出I/O请求的进程分配设备外,还要为他分配___,___,___
6.文件系统通常向用户提供的接口有__接口和__接口.
7.UNIX文件系统中通过引入__索引结点来提高文件的检索效率.
八.简答题(共10分)
1.(5分)试述缺页中断的处理步骤;与一般中断相比,主要的区别是什么?
2.(5分)UNIX文件系统使用的地址索引结构是什么?与一般的地址索引结构相比有什么优点?付出的代价是什么?
九.算法题(共10分)
遵循同步机制的四条准则,写出用锁机制实现的解决读者--写者问题的同步算法.
十.(10分)简述UNIX系统V中块设备数据缓冲池的管理技术,给出缓冲池的结构和缓冲区的分配与释放操作.。