[ post][/hide]复旦大学1998年数据结构与操作系统考研试题
考试科目:数据结构和操作系统
一. 简述下列各对术语之间的差异: (10分)
(1) 可重入程序和顺序可重入程序
(2) 进程与线程
(3) 主存贮器与联想存贮器
(4) 死锁与饥饿
(5) 索引文件与索引顺序文件
二. 现有四个进程导入了死锁,请用资源请求分配图画出全部可能的死锁情况. (10分)
三.
. 如图所示,一座只能行使一辆车的桥连接被河流阻隔的双车道公路.先用管程实现交通管理,以防塞车,并说明算法地公平性 (10分)
四. 试证明,在具有n(n>=!)个结点的m次树中,有n(m-1)+1个指针是空的 (8分)
五. 对于任何一棵非空的二叉树,假设叶子接点的个数为n0,而次数为的2结点个数为n2,请给出n0和n2之间所满足的关系式n0=f(n2).要求给出推导过程 (8分)
六. 下面的邻接表表示一个给定的无向图 (10分)
(1) 给出从顶点v1开始,对图G用深度优先搜索法进行遍历的顶点序列
(2) 给出从顶点v1开始,对图用广度优先搜索法进行遍历时的顶点序列
在下面的第七第八题中填上适当的内容,每一个空框只填一个语句或一个表达式
七.下面的程序对于给定的链表p进行快速排序,与对顺序存贮的线性表进行快速排序相类似,采用分治法进行处理,以链表的第一个结点值作为基准,把其他结点按小于或大于基准结点值分为两组,再递归对两组结点分别进行快速排序序，最后链接所有的链表。程序中为全程的指针变量，它指向已排序链表的最后一个结点 (14分)
typedef struct node{int data; struck node*link;} NODE;
NODE *last;
NODE *quick-sort(p);
NODE *p;
{NODE low-head,low-tail,*mid-head,*mid-tail,*high-head,*head-tail;
if p:=NULL {last=NULL; return(P);}
low-head=low-tail=NULL;
mid-head=mid-tail=NULL;
high-head=head-tail=NULL;
if(mid-head=NULL) mid-head=p;
else mid-tail→link=p; mid-tail=p;p=p→link;
while
{if(p→data
{if low-head=NULL} low-head=p;
else low-tail→link=p;low-tail=p;
}
else if(p→data=mid-head→data)
{if (mid-head=NULL}high-head=p;
else
}
else{if(high-tail=NULL) high-head=p;
else high-tail→link=p;high-tail=p;
}
}
if(low-head=NULL)
{low-tail→link=NULL;
=quicksort(low-head);
last→link=mid-head;
}
else p=mid-head;
if(high-head=NULL)high-tail→link=NULL;
=quick-sort(high-head);
if(last=NULL)last=mail;
;
}
(八) 下面的程序对给定的二叉树t，借助链接栈求出二叉树的深度。这里约定：若t为空的二叉树，则树t的深度为-1。程序中使用类型见下一页。 (14分)
Int depth-tree(t)
NODE*t;
{SNODE.*top=NULL,*p;
int d,maxd;
maxd=d=-1;
while( )
{while( )
{if( )maxd=d;
p=(SNODE*)malloc(sigeof(SNODE));
p→addr=t;p→dep=d;
p→link=top;top=p;
;
}
if( )
{ ;d=top→dep;
p=top;top=top→link;free(p);
;
}
}
}
return(maxd);
上面程序所使用的类性为：
ypedef struct node{char data;struck node*lchild,*rchild;}NODE;
ypedef struct snode{NODE*addr;struck snode*link;}SNODE;
(九)填数问题：从整数一至十中任取九个不同的数，填入右图九个不同的格子中，使所有左，右相邻和上，下相邻的两个格子中的数之和是素数(质数)。例如在图中所填的数就是其中一个解。试编写一个求上面填数问题的所有解的程序.
要求给出详细算法,然后再写出程序,不给出详细算法整题不得分.
程序可用c语言编写,也可用pascal语言编写. (16分)
1 2 5
4 3 8
7 10 9 |
收藏
点赞!
反对!