复旦大学1996年数据结构与操作系统考研试题

复旦大学1996年数据结构与操作系统考研试题一.名词解释(10分)1.程序状态字2.可重入程序3.工作集4.无限等待5.作业说明书二.假设并发系统中有8个程序P1,P2,…,P8他们之间具有下述的优先关系，试写出相应的并发程序。（10分）三.一般系统要求以显式打开文件，其目的是什么？有的系统则不必这样，简述这两种方法的优缺点。（10分）四.菲波那契数列由下式所定义：Fn=1(n=1),Fn=1(n=2),Fn=F(n-1)+F(n-2)(n≥3)二叉树T的深度d(T)由下式所定义：d(T)=0(T为空二叉树)，d(T)=max{d(Tl),d(Tr)}+1(T为非空二叉树)上式中Tl和Tr分别为T的根结点的左、右子树。试证明深度为d的平衡二叉树的最少结点个数为Nd=F(d+2)–1（10分）五.对于给定的n阶方阵a[1..n,1..n],我们规定按顺时针盘旋的次序把a中的元素依次存放在b[1..n*m]中（见下图）。如果a[i,j]存放在b[k]中，那么，请给出求解k的计算公式。（10分）六．对于下面给出的程序过程p(a,k,n),如果n=3,a[1]=’a’,a[2]=’b’,a[3]=’c’,那么在执行调用语句p(a,1,3)时，程序将输出什么？程序过程实现什么样的操作？（10分）CONSTmaxn=26；TYPElist=ARRAY[1..maxn]OFchar；VARa：list；n:integer；PROCEDUREp(VARa：list；k,n：integer)；VARt：char；i：integer；BEGINIFk=nTHENBEGINFORi:=1TOnDOwrite(a)；writelnENDELSEFORi:=kTOnDOBEGINt:=a[k]；a[k]:=a；a:=t；p(a,k+1,n)ENDEND；七．对于给定的线性链表head,下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在空框处填上适当的内容，使之成为一个完整的程序过程，每个空框只填一个语句。（20分）TYPEnodeptr=^nodetypenodetype=RECORDdata:integerlink:nodeptrVARhead:nodeptrPROCEDUREsort_output_delete(head:nodeptr)VARp,q,r,s:nodeptrBEGINWHILEheadNILDOBEGINp:=NIL；r:=head；r:=q；s:=q^.data；WHILEsNILDOBEGINIFs^.dataq^.dataTHENBEGIN(1)________(2)________END；r:=s；(3)_________END；write(q^.data:5)；IFp=NILTHEN(4)_________ELSE(5)_________；dispose(q)；END；writelnEND；八．设G是一个用邻接表表示的连通无向图。对于G中某个顶点v，若从G中删去顶点v及与顶点v相关联的边后，G变成由两个或两个以上非空连通分量所组成的图，则称v是原来图G的一个关节顶点。如下图中，只有顶点4和顶点6是关节顶点，而其它顶点都不是关节顶点。试叙述寻找图G的所有关节顶点的算法，并用算法语言（PASCAL或C）编写一个实现你所给出的算法的程序。（20分）