首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下: ty
函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下: ty
admin
2015-06-03
68
问题
函数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网如图15-2所示,其邻接表存储结构如图15-3所示。
【函数代码】
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*)malloc((G.n+1)*si zeof(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)indegree[p->adjvex]++。 (2)Stack[top--]。 (3)indegree[p->adjvex]--。 (4)(Ve[w]+p->weight)>ve[p->adjvex]。 (5)Ve[w]。
解析
此C语言程序题考点为拓扑排序和关键路径。在解题之前,先了解几个概念。
(1)AVO网络。
一个大工程中有许多项目组,有些项目的实行存在先后关系,某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示,工程的项目称为活动,有向图的顶点表示活动,有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络,简称AOV网络,图15-4所示是一个AOV网络。
(2)拓扑排序。
对AOV网络的顶点进行拓扑排序,就是对全部活动排成一个拓扑序列,使得如在AOV网络中存在一条弧(i,j),则活动i排在活动j之前。对图15-4中的顶点进行拓扑排序,可以得到多个不同的拓扑序列,如02143567,01243657,02143657,01243567。
(3)AOE网络。
利用AOV网络,对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间,为了能估算某个活动的开始时间,找出那些影响工程完成时间最大的活动,需要利用带权的有向图。图中的顶点表示一个活动结束的事件,图中的边表示活动,边上的权表示完成该活动所需的时间,这种用边表示活动的网络称为AOE网络。图15-5所示为一个具有8个活动的某个工程的AOE网络。图中,有6个顶点,分别表示事件V1~V6,其中V1是工程的开始状态,V4是工程的结束状态。边上的权表示完成该活动所需的时间。
(4)关键路径。
在AOE网络中某些活动可以并行地进行,所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度,称从开始顶点到结束顶点的最长路径为关键路径,关键路径上的活动为关键活动。如图15-5的AOE网络的关键路径为V1—V2—V6—V4,关键路径长度为80。
了解了上面的这些概念以后,解题就非常容易了。
从程序中的注释可知下段程序的作用是求网中各顶点的入度。
for( j = 1; j<=G.n; j++ ){
p=G.head[j].Firstadj;
while( p ){
(1)
p=p->nextarc;
}
}
从已知的代码结合邻接表来看,首先p指向了邻接表弟1个结点V1的Firstadj域,然后用while循环遍历了V1的Firstadj指向的链表。链表中的记录的,是当前结点可到达的结点,只要统计这些结点在邻接表中所有链表中出现的次数,就可知道其入度。又因为程序前面有:
indegree=(int*)malloc( (G.n+1)*sizeof(int) );/*存储网中各顶点的入度*/
所以第(1)空应填indegree[p->adjvex]++。
接下来看第(2)空,第(2)空是给w赋值,接下来是打印第w号结点的数据,这也就意味着w号结点是拓扑排序选出来的结点,所以w必是一个入度为0的结点。然而在此之前已经有程序把所有的入度为0的结点保存在Stack数组中了,而且Stack数组是模拟的一个栈,其控制指针只有top,所以我们应该从Stack中取出栈顶元素赋值给w。所以第(2)空填Stack[top-]。注意这里不能用“Stack[-top]”,因为前面有入栈语句
“Stack[++top].j;”。
接下来看下面的程序段。
while(p){
(3);
if( !indegree[p->adjvex] )
stack[++top] :p->adjvex;
if (4)
Ve[p->adjvex] =Ve[w]+p->weight;
p=p->nextarc;
}
此段程序的作用是:把选出结点所关联的边去掉,即原来V1有到V3的边a1=30和到V2的边a2=10,当V1结点选出以后,a1,a2也要随之消失。这时V3和V2的入度要更新,也就是把V3和V2的入度分别减1。所以第(3)空应填indegree[p->adjvex]--。第(4)空看起来比较棘手,因为前面没有说明ve是用于存放什么数据的,所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度,但到目前为止,都没有程序段完成此项功能。所以可以断定
if (4)
ve[p->adjve]=Ve[w]+p->weight;
的功能是计算关键路径长度。ve的初值最开始都是0,而且关键路径是要找从开始点到结束点的最长路径。所以只要保证每到一个点vx,ve[vx]中存的都是最长路径即可。也就是说,首先选出的是V1,从V1~V2只有一条路径,所以ve[v2]=a2=10,从V1~V3只有一条路径,所以ve[v3]=a1=30。然后选出V2结点,V2选出以后,因为V2~V6有a5=50,所以现在到V6的最长路径为ve[v6]=ve[v2]+a5=60。经过若干步后,当程序选中V3结点时,会产生到V6的另外一条路径V1-V3-V6,这条路径的长度为50,这条路径比现存的路径长度ve[v6]短,所以单纯的更新语句“ve[p->adjvex]=ve[w]+p->weight”不能正确保存最长路径,为了保证ve中保存的路径最长,应该有判断(Ve[w]+p->weigh()>Ve[p->adjvex]。所以第(4)空应该填“(ve[w]+p->weight)>ve[p->adjvex]”。
第(5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度,才是整个图的关键路径呢?这一点可以从关键路径的定义着手:“称从开始顶点到结束顶点的最长路径为关键路径”,所以最后一个选出结点的ve存放的便是关键路径。所以第(5)空应填ve[w]。
转载请注明原文地址:https://kaotiyun.com/show/GdDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
由图1-1可见,网络中心与图书馆相距700米,而且两者之间采用千兆连接,那么两个楼之间的通信介质应选择(1),理由是(2)。备选答案:(1)A.单模光纤B.多模光纤C.同轴电缆D.双绞线校园网对校内提供VOD服
与ISDN相关的网络设备主要有TA、NT1、NT2、TE1、TE2等。在图2-9所示的网络拓扑结构中,路由器Router1和ISDN之间是否需要加入终端适配器(TA)?请用150字以内的文字简要说明理由。在以上路由器Router2的配置命令列表中,di
与ISDN相关的网络设备主要有TA、NT1、NT2、TE1、TE2等。在图2-9所示的网络拓扑结构中,路由器Router1和ISDN之间是否需要加入终端适配器(TA)?请用150字以内的文字简要说明理由。在路由器Router2上运行showrunni
阅读以下关于校园网组建的技术说明,根据要求回答问题1至问题4。【说明】某学校新建一栋21层教学综合大楼,楼层两端相距100m,距一端50m处有一弱电竖井,弱电竖井贯穿每层的弱电室。每层楼均有100个信息点(所有信息点要求具有100Mb/s的数据传
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]ATM(AsynchronousTransferMode)顾名思义就是异步传输模式,是国际电信联盟ITU-T制定的标准。实际上在20世纪80年代中期,人们就已经
若采用电话线方式上网,并按要求在计算机连入网络的同时能通电话,连网速率高于500Kbps,可以选用哪种技术方案?其最高通信速率为多少?若采用电视铜缆接入计算机主干网络,用户端需增添什么设备?网络通信速率为多少?
阅读以下说明、Java源程序和运行测试部分1.HTTP协议。●HTTP请求消息示例:GET/index,htmlHTTP/1.1Accept:image/gif,image/jpeg,*/Acc
简述本题中POP3服务的实现过程。要求:(1)仅屏蔽来自200.117.112.0网络的FTP数据信息;(2)仅屏蔽来自192.168.11.12主机对Internet的FTP数据信息请求。请填写完整相关信息,将(1)~(4)处
认真阅读以下关于架构Apache安全服务器的技术说明,根据要求回答问题1至问题5。【说明】某些商务公司要求其网站的部分信息资源只对经过身份认证后的用户开放。因此在Linux+Apache架构Web服务器方案中,需利用mod-ss1模块给Apach
随机试题
Whatjobdidthemangetfirst?Hegotthefirstjobas_________________.
形成视网膜裂孔危险性最小的周边视网膜变性是
患者,男性,65岁。诊断为胆道泥沙样结石,拟行胆总管空肠RouxenY吻合术。WBC11.5×109/L,中性粒细胞0.75。血清总胆红素162μmol/L,谷丙转氨酶215U/L,凝血酶原时间(PT)18s。患者口服灌肠液的时间为
超额存款准备金主要用于()。
管理信息的特征包括()。
哥白尼的“日心说”与当时的宗教思想、占统治地位的亚里士多德的物理学以及人们的“常识”均相抵触,一开始遭到许多人的反对,直到牛顿发现万有引力定律之后才逐步被天文学家们承认。随着现代科技的发展,“日心说”也已经被否定,太阳只是银河系中一颗普通的恒星。由此说明(
Intheolddays,childrenwerefamiliarwithbirthanddeathaspartoflife.ThisisperhapsthefirstgenerationofAmericany
【B1】【B8】
A、Itcanavoidthenecessityofcarryinglargeamountofcash.B、Youneedn’tpurchaselargeamountsoftraveler’schecks.C、You
Lookattheboxfilesonthisshelf.Theyareintheofficeofthewomanwhoproducesthemonthlycompanynewsletter.Forquesti
最新回复
(
0
)