软件工程作为国家重点扶持的高端紧缺行业，已被越来越多的人所关注。教育部在05年特批了35所示范院校可以进行软件工程硕士的自主的招生，由学校自主命题考试，但考试的科目和试卷的样本仍需上报国家教育部备案，其考试的难度可想而知。软件工程硕士的考试科目主要包括：数学、英语和专业课。专业课程中又以数据结构与操作系统和计算机组成原理为主。下面我们将2008年电子科技大学软件工程硕士数据结构与操作系统公布给大家，以备大家复习备考
考试科目:数据结构和操作系统
一. 简述下列各对术语之间的差异: (10分)
(1) 可重入程序和顺序可重入程序
(2) 进程与线程
(3) 主存贮器与联想存贮器
(4) 死锁与饥饿
(5) 索引文件与索引顺序文件
二. 现有四个进程导入了死锁,请用资源请求分配图画出全部可能的死锁情况. (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
版权声明: 转载时请以超链接形式标明文章原始出处和作者信息