中级软件设计师填空集试卷（中级软件设计师）_10.docVIP

试卷第 PAGE 1 页共 NUMPAGES 3 页 中级软件设计师填空集试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、阅读下列函数说明和C代码，将应填入 (n) 处的字句写在对应栏内。[说明]函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：typedef struct Gnode /*邻接表的表结点类型*/int adjvex； /*邻接顶点编号*/int weight； /*弧上的权值*/struct Gnode*nextarc；/*指示下一个弧的结点*/Gnode；typedef struct Adj list /*邻接表的头结点类型*/char vdata； /*顶点的数据信息*/struct Gnode *Firstadj；/*指向邻接表的第一个表结点*/Adjulist；typedef struct LinkedWDigraph/*图的类型*/int n，e； /*图中顶点个数和边数*/struct Adjlist *head； /*指向图中第一个顶点的邻接表的头结点*/LinkedWDigraph；例如，某AOE网如图21-1所示，其邻接表存储结构如图21-2所示。[本题函数]int Toplogical(LinkedWDigraph G)Gnode *p；int j，W，top=0；int *Stack，*ve，*indegree；ve=(int *)malloc((G.n+1) *sizeof(int))；indegree=(int*)maZZoc((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*//*while*/return (5) ；/*Toplogical*/1（ ） 2、阅读下列函数说明和C代码，将应填入 (n) 处的字句写在对应栏内。[说明]函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：typedef struct Gnode /*邻接表的表结点类型*/int adjvex； /*邻接顶点编号*/int weight； /*弧上的权值*/struct Gnode*nextarc；/*指示下一个弧的结点*/Gnode；typedef struct Adj list /*邻接表的头结点类型*/char vdata； /*顶点的数据信息*/struct Gnode *Firstadj；/*指向邻接表的第一个表结点*/Adjulist；typedef struct LinkedWDigraph/*图的类型*/int n，e； /*图中顶点个数和边数*/struct Adjlist *head； /*指向图中第一个顶点的邻接表的头结点*/LinkedWDigraph；例如，某AOE网如图21-1所示，其邻接表存储结构如图21-2所示。[本题函数]int Toplogical(LinkedWDigraph G)Gnode *p；int j，W，t