首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网
admin
2010-01-15
24
问题
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
typedef struct Gnode{ /*邻接表的表结点类型*/
int adivex; /*邻接顶点编号*/
int weight; /*弧上的权值*/
bstmct Gonde*nextare; /*指示下一个弧的结点*/
}Gnode;
typedef struct Adjlist{ /*邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode*Firstadj; /*指向邻接表的第1个表结点*/
}Adjlist;
typedef struct LinkedWDigraph{ /*图的类型*/
int n, e; /*图中顶点个数和边数*/
struct Adjlist head; /*指向图中第1个顶点的邻接表的头结点*/
}LinkedWDigraph;
【函数】
int Toplogical(LinkedWDigraph G)
{ Gnode *p;
int j,w,top=0;
int *Stack,*ve,*indegree;
ve=(int *)mallloc(G.n+1)* sizeof(int)};
indegree=(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(i=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*/
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]及其等价形式
解析
(1)indegree[p->adjvex]++及其等价形式
此填空在for(j=1;j<=G.n;j++)中,求网中各顶点的入度。遍历邻接表G.head[j].Firstadj,将每个结点p->adjvex的入度indegree[p->adjvex]加1。邻接表是j的出度结点表。
(2)Stack[top-]及其等价形式
栈Stack中存放的是入度为0的结点号,此while循环中,w取栈顶值开始搜索打印这些结点。
(3)indegree[p->adjvex]--及其等价形式
由于p=G.head[w].Firstadj;因此while循环是遍历这个邻接链表,将每个结点的入度减1。将入度为0的结点号入栈Stack中。
(4)ve[w]+p->weight>ve[p->adjvex]及其等价形式
若ve[w]+p->weight大于ve[p->adjvex],则ve[w]+p->weight是最长路径,用ve[w]+p->weight取代ve[p->adjvex]。
(5)ve[w]及其等价形式
最终返回的是w结点的ve[w]值作为整个AOE—网的最长路径值。
转载请注明原文地址:https://kaotiyun.com/show/c0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
设有关系模式R(A1,A2,A3,A4,A5,A6),其中:函数依赖集F={A1→A2,A1A3→A4,A5A6→A1,A2A5→A6,A3A5→A6),则___________(21)是关系模式R的一个主键,R规范化程度最高达到____________(
下列关于软件开发的叙述中,与提高软件可移植性相关的是(19)。
某财务系统在使用过程中,因个人所得税政策变化,需修改计算工资的程序。这种修改属于______维护。
下图中,类Product和ConcreteProduct的关系是(45),类ConcreteCreator和ConcreteProduct的关系是(46)。(46)
CPU中的数据总线宽度会影响(4)。
A类网络是很大的网络,每个A类网络中可以有(26)个网络地址。实际使用中必须把A类网络划分为子网,如果指定的子网掩码为255.255.192.0,则该网络被划分为(27)个子网。(26)
假设系统中有三类互斥资源R1、R2和R3,可用资源数分别为10、5和3。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,此时系统剩余的可用资源数分别为(22)。如果进程按(23)序列执行,那么系统
某企业生产流水线M共有两位生产者,生产者甲不断地将其工序上加工的半成品放入半成品箱,生产者乙从半成品箱取出继续加工。假设半成品箱可存放n件半成品,采用PV操作实现生产者甲和生产者乙的同步可以设置三个信号量S、S1和S2,其同步模型如下图所示。 信号量
对某商店业务处理系统采用数据流图(DFD)进行功能建模,其中“检查订货单”是其中的一个①。由于在进行订货单检查时,需要根据客户的欠款情况、订单金额等多个条件判断是否采取发出催款单、准备货物、发出发货单等行为,此时适合采用②进行描述。②处
产品的功能性测试的内容不包括______。A.适合性B.易用性C.正确性D.互操作性
随机试题
心肌梗死的发热很少超过()
下列行为人以他人的名义而进行的“代理”活动,是无权代理的有( )。
在以下的合同中,( )属于效力待定的合同。
某石油化工企业在进行总平面设计时,明火加热炉宜集中布置在装置的边缘,且位于可燃气体、液化烃、甲B类液体设备的()。
下列关于民事诉讼管辖的说法中,正确的是()。
下列不属于广告监理管理的行政许可的是()。
某人购得一条电热毯,在使用时因该电热毯漏电而受伤害,如果他向法院起诉,法律保护其请求权的诉讼时效期间为()。
Thecentralgovernmenthopestocurtailmilitaryspendinginthenextyear.
Facialtattooingisastandard______amongcertainpeoples.
Work-lifeBalance:FlexAppealGeorginaBlizzardandNickyImriedecidedtheyneededtofindamoreflexibleworkingpattern
最新回复
(
0
)