首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
函数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
113
问题
函数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
软件设计师下午应用技术考试
软考中级
相关试题推荐
请阅读以下说明和Socket程序,将应填入(n)处的字句写在对应栏内。【说明】网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。一般发起通信请求的应用程序称为客户软件,该应
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在第4步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释(1)~(4)处的标有下划线部分配置命令的含义(“◇”后为配置内容
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1、问题2和问题3。现以一台远程访问服务器(RemoteAccessServer,RAS)Cisco2509、RJ45为例来说明。第1步,准备安装与调试所需的设备,主要包
如果以前已经配置过这台服务器为VPN服务器,现在需要重新配置,该怎么操作?Windows2000服务器配置完毕后,系统默认任何用户均都可以拨入连接到服务器上吗?
如果以前已经配置过这台服务器为VPN服务器,现在需要重新配置,该怎么操作?VPN按技术可分为哪三类?
阅读以下基于VPN网络互连的网络规划设计的技术说明,根据要求回答问题1至问题3。【说明】某软件开发公司总部和子公司A、子公司B分别位于3个不同的省城,公司总部通过一台带VPN功能的防火墙与Internet连接。该防火墙支持PPTP、L2TP、IP
根据该单位防火墙与外部网络相关的网络连接参数,请将以下命令行中(1)~(4)空缺处的内容填写完整,以完成对防火墙相应的网络接口进行地址初始化的配置。FireWall(config)#ipaddressinside(1)(2)
阅读以下说明,回答问题1和问题2。【说明】某学校拟组建一个小型校园网,具体设计如下:1.设计要求。(1)终端用户包括:48个校园网普通用户;一个有24个多媒体用户的电子阅览室;一个有48个用户的多媒体教室(性能要求高于电子阅
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?如果ISDN收费是按每分钟计算,假如0.5元/分钟,采用ISDN基本速率接口下载1024k的文件需要付费多少?
阅读以下关于网络应用系统可靠性分析方面的技术说明,根据要求回答问题1至问题4。【说明】可靠性是一个网络应用系统能正常工作的能力,一般用平均故障间隔时间(MTBF)来度量。某网络应用软件研发公司正在开发一个嵌入式实时应用软件——宽带路由器的NanO
随机试题
在asp.net中,下面()是用类保存类型代码的文件夹
企业营销环境的中心是()
A.氨茶碱B.沙丁胺醇C.哌仑西平D.色甘酸钠E.二丙酸倍氯米松抢救哮喘持续状态宜选用的药物是
A.痈B.瘰疬C.流痰D.有头疽E.红丝疔易发生内陷的疾病是
下列项目中,符合房产税规定的有()。
旅游团中某位旅游者希望带其在华亲友的孩子随团活动,导游员应该()
某公司新上任的人力资源部王经理,在一次研讨会上获得了一些他自认为不错的其他企业的培训经验,回来后就向公司主管领导提交了一份全员培训计划书,要求对公司全体人员进行为期一周的脱产计算机培训,以提升全员的计算机操作水平。不久,该计划书就获批准,公司还专门下拨十几
保教结合就是教师要与保育员沟通、相互帮助。()
对地球和人类而言,月亮不仅仅__________着地月系统的固有状态和稳定运行,还以其优雅、静谧、澄澈,以及阴晴圆缺和生生不息__________着人们无尽的审美意象。填入画横线部分最恰当的一项是:
【S1】【S8】
最新回复
(
0
)