首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
函数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
110
问题
函数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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1、问题2和问题3。现以一台远程访问服务器(RemoteAccessServer,RAS)Cisco2509、RJ45为例来说明。第1步,准备安装与调试所需的设备,主要包
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?限制MailUser邮件主机里最多允许有2000个邮件用户,如何配置?
如果以前已经配置过这台服务器为VPN服务器,现在需要重新配置,该怎么操作?Windows2000服务器配置完毕后,系统默认任何用户均都可以拨入连接到服务器上吗?
阅读以下说明,回答问题1、问题2和问题3,将解答填入对应栏内。[说明]ADSL是运行在原有电话线上的一种高速宽带上网方式,具有节省投资、上网速度快与安装简单等优点。目前很多局域网、家庭上网,尤其是网吧都使用这种方式。接入方式如图6-1所示
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。简述WLAN用户通过RADIUS服务器登录的过程。
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
SSL是一个协议独立的加密方案,在网络信息分组的应用层和传输层之间提供了安全的通道。SSL主要包括SSL修改密文协议、SSL握手协议、SSL告警协议、SSL记录协议等,其协议栈见图7-16。请根据SSL协议栈结构,将(1)~(4)处空缺的协议名称填写完整。
如果在网络设计过程中划分了很多VLAN,则可采用VTP来简化其管理。交换机管理IP地址只能创建在(1)中,而VTP信息只能在(2)端口上传播。共享相同VLAN数据库的交换机构成一个(3)。不同交换机平台、不同的IOS版本支持的VLAN数量不同,从图6-18
阅读以下交换机Switch01的部分配置信息,结合图2-8所示的网络拓扑图将(1)~(8)空缺处的内容(命令或解释)填写完整。Switch>enable(进入特权模式)S
随机试题
喂婴幼儿吃药()。
________是经济体制的基础,________是经济制度的具体实现形式。
虚寒痢的治法是
女婴,4月,1周来口腔粘膜出现白色凝乳状的斑点及斑块,可擦掉;患儿啼哭,哺乳困难。应怀疑为
患儿,男,7岁,因腹痛、发热(37.5℃)、食欲不振3天来诊。查体:37.4℃,精神萎靡,呼吸、脉搏无异常。双侧下肢及臀部可见出血点,尤以下肢伸侧为重,称分布,微高出皮面,压之不退色,新旧出血点并存。腹部平坦,脐周及下腹部均有压痛,但无肌肉紧张及反跳痛。粪
甲公司和乙公司签订了设备购买合同,合同约定甲公司分期付款购买乙公司的设备,设备总价款100万元,甲公司分5次付款,每次付款20万元。以下说法正确的是:
强制传唤属于()的权利形式。
2005年打捞公司在南川岛海域调查沉船时意外发现一艘载有中国瓷器的古代沉船,该沉船位于海底的沉积层上。据调查,南川岛海底沉积层在公元1000年形成,因此,水下考古人员认为,此沉船不可能是公元850年开往南川岛的“征服号”沉船。以下哪项如果为真,最严重地弱化
抗日战争是中国人民在中国共产党的领导下,为抗击日本帝国主义侵略而进行的伟大的民族革命战争。下列有关抗日战争的说法,不正确的有:
《中华民国临时约法》规定“中华民国之主权属于国民全体”,下列选项中体现这一观点的是
最新回复
(
0
)