首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
函数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
114
问题
函数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
软件设计师下午应用技术考试
软考中级
相关试题推荐
如果以前已经配置过这台服务器为VPN服务器,现在需要重新配置,该怎么操作?Windows2000服务器配置完毕后,系统默认任何用户均都可以拨入连接到服务器上吗?
阅读以下说明,回答问题1、问题2和问题3,将解答填入对应栏内。[说明]ADSL是运行在原有电话线上的一种高速宽带上网方式,具有节省投资、上网速度快与安装简单等优点。目前很多局域网、家庭上网,尤其是网吧都使用这种方式。接入方式如图6-1所示
阅读以下说明,回答问题1~3。【说明】Windows组网是指把Windows终端和服务器连接起来。如图5-6所示给出了在Windows操作系统中的典型LAN配置。
SSL是一个协议独立的加密方案,在网络信息分组的应用层和传输层之间提供了安全的通道。SSL主要包括SSL修改密文协议、SSL握手协议、SSL告警协议、SSL记录协议等,其协议栈见图7-16。请根据SSL协议栈结构,将(1)~(4)处空缺的协议名称填写完整。
L2TP协议是一种基于(1)协议的二层隧道协议,它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上,为了保证传输的可靠性,L2TP协议对控制报文采取了(3)机制,并要求tunne1对端设备在隧道(tunne
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。项目管理就是以项目为对象的系统管理方法,通过一个临时性的专门的柔性组织,对项目进行高效率的计划、组织、指导和控制,以实现项目全过程的动态管理和项目目标的综合协调与优化。除了本题涉及到
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。在最理想和保守的估计中加速开发进度要着重抓的共同环节是哪些?请用50字以内的文字加以说明。
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。请指出图7-15可能存在的关键路径是什么?(请用英文字母序号列出)
阅读以下说明然后完成问题1、问题2、问题3、问题4,把答案填入相应的对应栏内。[说明]如图10-1是Cisco1900交换机划分为两个vain拓扑图,把E0/10划分为vlan2,把E0/20划分为vlan3。[*]
随机试题
Ifyouweretobeginanewjobtomorrow,youwouldbringwithyousomebasicstrengthsandweaknesses.Successor【61】inyourwor
1岁患儿,母乳喂养未添加辅食。查体:虚胖,毛发稀黄,面色苍黄,肝肋下3cm,脾肋下1.5cm,表情呆滞,智力发育落后,肢体震颤,踝阵挛阳性。此患儿最不可能出现的指标是
以下所列机场中,属于干线机场的有()。
根据《水利水电建设工程验收规程》SL223--2008,工程竣工验收分两阶段进行,即在国家主管部门组织竣工验收前,项目法人应组织进行工程竣工验收的()。
某工业企业(增值税一般纳税人),2010年1月购销业务情况如下:(1)购进生产原料一批,已验收入库,取得的防伪税控系统开具的增值税专用发票上注明的价、税款分别为23万元、3.91万元;(2)购进钢材20吨,未入库,取得的防伪税控系统开具
请你结合科学发展观谈一谈如何建设一支高素质的公安干警人才队伍。
2014年一季度,上海市六个重点发展的工业行业共完成工业总产值5168.47亿元,增长3.6%,增幅低于全市规模以上工业平均水平0.4个百分点。其中,汽车制造业产销两旺,共完成工业总产值1372.12亿元,增长15%。一季度生产汽车67.33万辆,增长15
设总体X的概率分布为X~,其中参数θ未知且。从总体X中抽取一个容量为8的简单随机样本,其8个样本值分别是1,0,1,-1,1,1,2,1。试求:(Ⅰ)θ的矩估计值;(Ⅱ)θ的最大似然估计值;(Ⅲ)经验分布函数F8(x)。
如有声明语句Dima(2,-3To2,4),则数组a包含元素的个数是()。
38.MyclassmateaskedMe______.
最新回复
(
0
)