2010年软件水平考试软件设计师考前练习题(5)

　　试题4(15分)

　　阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

　　【说明】函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：

　　typedef struct Gnode{ /*邻接表的表结点类型*/

　　int adjvex; /*邻接顶点编号*/

　　int weight; /*弧上的权值*/

　　struct Gonde*nextare;　 /*指示下一个弧的结点*/

　　} Gnode;

　　typedef struct Adjlist{ 　 /*邻接表的头结点类型*/

　　char vdata;　 /*顶点的数据信息*/

　　struct Gnode*Firstadj;　 /*指向邻接表的第1个表结点*/

　　} Adjlist;

　　typedef struct LinkedWDigraph{ /*图的类型*/

　　int n ,e;　 /*图中顶点个数和边数*/

　　struct Adjlist head; /*指向图中第1个顶点的邻接表的头结点*/

　　} LinkedWDigraph;

　　【函数】

　　int Toplogical(LinkedWDigraph G)

　　{ Gnode *p;

　　int j,w,top=0;

　　int *Stack,*ve,*indegree;

　　ve=(int *)mallloc(G.n+1)*sizeof(int)};

　　indegree=(int *)malloc((G.n+1)*sizeof(int)); /*存储网中个顶点的入度*/

　　Stack=(int *)malloc((G.n+1)*sizeof(int)); /*存储入度为0的顶点的编号*/

　　if (!ve || !indegree || !Stack)

　　exit(0);

　　for (j=1;j<=G.n;j++){

　　ve[j]=0; indegree[j]=0;

　　}/*for*/

　　for (j=1;j<=G.n;j++) { 　/*求网中各顶点的入度*/

　　p=G.head[j].Firstadj;

　　while (p) {

　　(1) ; p=p->nextarc;

　　} /*while*/

　　} /*for*/

　　for (j=1;j<=G.n;j++) /求网中入度为0的顶点并保存其编号*/

　　if (!indegree[j])　Stack[++top]=j;

　　while (top>0){

　　w= (2) ;

　　printf(“%c”,G.head[w].vdata);

　　p=G.head[w].Firstadj;

　　while (p) {

　　(3) ;

　　if (!indegree[p->adjvex])

　　Stack[++top]=p->adjvex;

　　if( (4) )

　　ve[p->adjvex]=ve[w]+p->weight;

　　p=p->nextarc;

　　}/*while*/

　　return (5) ;

　　} /*Toplogical*/