首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
函数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
2017-08-31
121
问题
函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
typedef struct Gnode{ /*邻接表的表结点类型*/
int adj vex; /*邻接顶点编号*/
int weight; /*弧上的权值*/
struct Gnode*nextarc; /*指示下一个弧的结点*/
}Gnode;
typedef struct Adj list{ /*邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode*Firstadj; /*指向邻接表的第一个表结点*/
}Adjulist;
typedef struct LinkedWDigraph{/*图的类型*/
int n,e; /*图中顶点个数和边数*/
struct Adj list*head; /*旨向图中第一个顶点的邻接表的头结点*/
}LinkedWDigraph;
例如,某AOE网如图15-2所示,其邻接表存储结构如图15-3所示。
【函数代码】
int Toplogical(LinkedWDigraph G)
{
Gnode*p;
int j r W r top=0;
int*Stack,*ve,*indegree;
ve=(int*)malloc((G.n+1)*sizeof(int));
indeqree=(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]=l:
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->advex]--。 (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的Firsta,dj指向的链表。链表中的记录的,是当前结点可到达的结点,只要统计这些结点在邻接表中所有链表中出现的次数,就可知道其入度。又因为程序前面有:
indegree=(int*)malloc((G.n+1)*sizeof(int) );/*存储网中各顶点的入度*/
所以第(1)空应填indegree[p->adjex]++。
接下来看第(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的边al=30和到V2的边a2=10,当V1结点选出以后,a1,a2也要随之消失。这时V3和V2的入度要更新,也就是把V3和V2的入度分别减1。所以第(3)空应填indegree[p->adjvex]--。第(4)空看起来比较棘手,因为前面没有说明ve是用于存放什么数据的,所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度,但到目前为止,都没有程序段完成此项功能。所以可以断定
if (4)
Ve[p一>adjvex]=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[wpp->weight)>ve[p->adjvex]。所以第(4)空应该填“(ve[w]+p->weight)>ve
[p->adjvex]”。
第(5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度,才是整个图的关键路径呢?这一点可以从关键路径的定义着手:“称从开始顶点到结束顶点的最长路径为关键路径”,所以最后一个选出结点的ve存放的便是关键路径。所以第(5)空应填ve[w]。
转载请注明原文地址:https://kaotiyun.com/show/lODZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?为保证内部网络的安全保密性,在如图1-12所示的网络拓扑图中,(6)空缺处应选用什么设备?如果将该设备放置在路由器Router和设备(2)之间,整个网络的安全级别是否会提高?请用150字以内
先阅读如下说明,然后回答问题。[说明]IPSec(Internet协议安全)是一个工业标准网络安全协议,为IP网络通信提供透明的安全服务,保护TCP/IP通信免遭窃听和篡改,可以有效抵御网络攻击,同时保持易用性。IPSec有两个基本目标:
下面是Web页面处理中3个步骤,请将其进行正确排序。①Web服务器接收到Web页面请求后,寻找所请求的Web页面,并将所请求的Web页面传送给Web浏览器。②Web浏览器接收到所请求的Web页面,并将它显示出来。③Web浏览器向一个
认真阅读以下关于架构Apache安全服务器的技术说明,根据要求回答问题1至问题5。【说明】某些商务公司要求其网站的部分信息资源只对经过身份认证后的用户开放。因此在Linux+Apache架构Web服务器方案中,需利用mod-ss1模块给Apach
L2TP协议是一种基于(1)协议的二层隧道协议,它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上,为了保证传输的可靠性,L2TP协议对控制报文采取了(3)机制,并要求tunne1对端设备在隧道(tunne
阅读以下说明,回答问题1和问题2。【说明】某学校拟组建一个小型校园网,具体设计如下:1.设计要求。(1)终端用户包括:48个校园网普通用户;一个有24个多媒体用户的电子阅览室;一个有48个用户的多媒体教室(性能要求高于电子阅
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?请说出ISDN与传统PSTN的区别。
请说出图9-1的拓扑结构名称与特点。根据IP地址与子网掩码,请判断它们是否属于同一个网段?如果不是,请说出他们分别属于哪个网段。
双绞线可以制作成直连线和交叉线两种形式,在图3-12所示的拓扑结构中,交换机与路由器(Router)相连的双绞线应制作成什么形式?利用IEEE802.1QVLAN中继协议进行不同VLAN之间数据的路由时,需要在原有的以太网帧中加入4字节的IEEE
随机试题
某人的红细胞与B型血的血清发生凝集,此人的血清与B型血的红细胞不发生凝集,分析此人的血型为()
病人消谷善饥,多见于
肺性脑病不能用高浓度吸氧,主要是因为
材料成本管理的控制应包括()。
已知某商业集团2008-2009年各季度销售资料,如表5-1所示。则表5-1中,属于时期数列的有()。
目前我国企业冗员较多,人浮于事,实行()可以解决富余人员较多的问题。
根据以下资料,回答问题。已知中国2010年水电发电量为6867亿兆瓦时,那同年核电发电量约为()亿兆瓦时。
Aperson’shomeisareflectionofhispersonality.Dependingonpersonality,mosthaveinminda(n)"【C1】______home".Butingen
Inthepopularmind,theInternetistherealizationoftheglobalvillage,wheretheflowofinformationandideasisunimpeded
FixingaWorldThatFostersObesityA)WhyareAmericansgettingfatterandfatter?Thesimpleexplanationisthatweeattoomuc
最新回复
(
0
)