首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
函数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
55
问题
函数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://jikaoti.com/ti/3Yi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?IMail安装完成后,系统自动建立了一个名为"root"的用户,在默认情况下“root”用户是个失效的账号,如何设置使其生效?
阅读以下说明,回答问题1~3。【说明】Windows组网是指把Windows终端和服务器连接起来。如图5-6所示给出了在Windows操作系统中的典型LAN配置。
阅读以下有关网络规划的叙述,回答问题1、问题2和问题3。网络工程是一项复杂的系统工程,一般可分为网络规划、网络设计、工程实施、系统测试验收和运行维护等几个阶段。网络规划是在需求分析的基础上,进行系统可行性分析和论证,以确定网络总体方案。网络规划阶段
SSL是一个协议独立的加密方案,在网络信息分组的应用层和传输层之间提供了安全的通道。SSL主要包括SSL修改密文协议、SSL握手协议、SSL告警协议、SSL记录协议等,其协议栈见图7-16。请根据SSL协议栈结构,将(1)~(4)处空缺的协议名称填写完整。
认真阅读以下关于架构Apache安全服务器的技术说明,根据要求回答问题1至问题5。【说明】某些商务公司要求其网站的部分信息资源只对经过身份认证后的用户开放。因此在Linux+Apache架构Web服务器方案中,需利用mod-ss1模块给Apach
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?请说出(1)的含义。
ADSL技术可以充分利用现有铜线网络,只要在用户线路两端加装ADSL设备即可为用户提供服务。请从以下术语选择适当的编号,将图5-9所示的拓扑结构中(1)~(4)空缺处的名称填写完整。【供选择的答案】A.程控交换机B.二层交换机
随机试题
食品污染是指有害物质进入正常食品的过程。()
已知(1)=1,则等于()
《城市规划法》的颁布和实施时间,下列哪一组是正确的?
根据《消防法》,需要进行消防设计的建筑工程,公安消防机构应该对()进行审核。
遗忘的进程是不均衡的,呈现的趋势是()
依次填入下面一段文字横线处的语句,衔接最恰当的一组是:__________。因为,老房子在轰隆隆地与我们告别,缤纷的手工正在不知不觉成批死亡。①这些信息中,只有少量体现在手工制品中,更多的保存在制作的过程中②从文化人类学角度说,每一种手工的背后还有一片
1.2017年12月28日至29日,中央农村工作会议在北京举行。会议深入贯彻党的十九大精神、习近平新时代中国特色社会主义思想,全面分析“三农”工作面临的形势和任务,研究实施乡村振兴战略的重要政策,部署2018年和今后一个时期的农业农村工作。会议指出,农业农
2011年,文化产业各行业增加值占比同比下降的有:
根据现行宪法,以下哪些机关有权制定基本法律()
关于程序模块优化的启发式规则有若干条,以下规则中不符合优化原则的是(1)。如果一个模块调用下层模块时传递一个数据结构,则这种耦合属于(2)。
最新回复
(
0
)