首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
函数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
69
问题
函数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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在Windows2003中,(1)不能实现NAT功能。A.终端服务管理器B.Internet连接共享C.路由和远程访问在服务器2的eth1上启用基本防火墙,如果希望将202.117.12.38固定分配给IP地址为192.1
IPSec工作在TCP/IP协议栈的(1),为TCP/IP通信提供访问控制、(2)、数据源验证、抗重放、(3)等多种安全服务。IPSec的两种工作模式分别是(4)和(5)。(1)~(5)备选答案:A.应用层B.网络层C.数据链
与ISDN相关的网络设备主要有TA、NT1、NT2、TE1、TE2等。在图2-9所示的网络拓扑结构中,路由器Router1和ISDN之间是否需要加入终端适配器(TA)?请用150字以内的文字简要说明理由。以下是在路由器Router1上的部分配置信息,结
解释图10-2中的PVC和SVC。以下是LANE工作过程,其顺序已乱,请排序。①LEC接着便向其他LEC广播这个响应。②在地址表中含有被称为MAC地址的LEC向LEC作出响应。③LES发送多点组播至网络上的其他LEC。④
阅读以下说明,将(n)的含义填入对应栏内。[说明]电子邮件是Internet中应用最广泛的服务,因此安装和配置一个高效与满足实际需求的电子邮件系统是每一个系统管理员的奋斗的目标之一,Linux的出现为构建低成本的、高效的电子邮件服务器提供了
VPN使用的隧道协议可以有那几类,分别有哪些协议?VPN路由器配置如下,请解释画线部分含义。Vpdn-group1(1)Accept-dialinprotocol12tpvirtual-template1terminate
若采用电话线方式上网,并按要求在计算机连入网络的同时能通电话,连网速率高于500Kbps,可以选用哪种技术方案?其最高通信速率为多少?若采用电视铜缆接入计算机主干网络,用户端需增添什么设备?网络通信速率为多少?
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整IEEE802.11标准采取了认证和加密措施,其中(9)具有控制图4-8所示的拓扑结构中无线接待室WLAN接入的能力。IEEE802.11标准提供WEP
阅读以下电子商务公司应用无线局域网的技术说明,根据要求回答问题1至问题5。【说明】由于市场的不断扩大,A电子商务公司客户数量日益增多。现有的网络已不能满足信息发展的需求,考虑到既要同时满足网络扩容顺利进行及公司日常工作的正常开展,又要保证目前土建
认真阅读以下关于架构Apache安全服务器的技术说明,根据要求回答问题1至问题5。【说明】某些商务公司要求其网站的部分信息资源只对经过身份认证后的用户开放。因此在Linux+Apache架构Web服务器方案中,需利用mod-ss1模块给Apach
随机试题
讲解“闻水声,如鸣骊环,心乐之”中“乐”的用法,教师使用其他同样包含该用法的语句进行比较。下列适合的是()。
简要回答构成有效接受必须具备的条件。
哮喘发作时,对缓解支气管痉挛作用最快的是
易发生DIC(弥散性血管内凝血)的白血病是()。
郁证总的治法是
下列选项中,属于填写票据和结算凭证的基本要求的有()。
欧洲谚语说:“钉子缺,蹄铁卸;蹄铁卸,战马蹶;战马蹶,骑士绝;骑士绝,战事折;战事折,国家灭”。这说明()。
请在“答题”菜单下选择“演示文稿”命令,然后按照题目要求再打开相应的命令,完成下面的内容,具体要求如下:注意:下面出现的所有文件都必须保存在考生文件夹下。打开考生文件夹下的演示文稿yswg.pptx,按照下列要求完成对此文稿的修饰并保存。
Manypeoplewatchedtheboys______themountainatthattime.
AuniquelaboratoryattheUniversityofChicagoisbusyonlyatnight.Itisadreamlaboratorywhereresearchersareatworks
最新回复
(
0
)