首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网
admin
2010-01-15
48
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
零件关系P(零件名,条形码,供应商,产地,价格)中的(12)属性可以作为该关系的主键。查询产于西安且名称为“P2”的零件,结果以零件名、供应商及零件价格分列表示,对应的SQL语句为:SELECT零件名,供应商,价格FROMPWHE
有关评估系统效率质量特性,以下论述正确的是______。A.响应时间越长,系统执行效率越高B.响应时间和交易执行吞吐量都是用来衡量系统执行快慢的C.响应时间越短,交易执行吞吐量越大D.系统的访问量越大,交易执行吞吐量越大
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(49)
以下关于功能测试用例的意义的叙述,正确的是(38)。①避免盲目测试并提高测试效率②令软件测试的实施重点突出、目的明确③在回归测试中无需修正测试用例便可继续开展测试工作④测试用例的通用化和复用化使软件测试易于开展
关于汇编语言,以下叙述中正确的是(20)。
某文件管理系统采用位示图(bitmap)记录磁盘的使用情况。如果系统的字长为32位,磁盘物理块的大小为4MB,物理块依次编号为:0、1、2、…,位示图字依次编号为:0、1、2、…,那么16385号物理块的使用情况在位示图中的第(24)个字中描述;如果磁盘的
在数据库逻辑结构设计阶段,需要(20)阶段形成的(21)作为设计依据。(21)
软件缺陷通常是指存在于软件之中的那些不希望或不可接受的偏差,以下关于软件缺陷的理解不正确的是()。
软件工程概念的提出是由于______。A.计算技术的发展B.软件危机的出现C.程序设计方法学的影响D.其他工程科学的影响
产品的功能性测试的内容不包括______。A.适合性B.易用性C.正确性D.互操作性
随机试题
某产妇,产后母乳喂养不顺利,改为人工喂养。产后一周左右产妇出现焦虑情绪,易激惹,有时暗自伤心落泪,伴有失眠、便秘等躯体症状。产后两周时,产妇的情绪越来越低落,回避他人,对自己缺乏信心,并因自己不会照顾小孩而有负罪感,有自杀念头。社区护士应提供的护理措施
A、HethinksBakeristoostrictinclass.B、HethinksBakerisnotstraightforward.C、Hethinkssheisunfair.D、Shedoesnotex
外科急腹症的特点,正确的是
当前城市规划管理工作的重要任务是()。
防水混凝土可通过调整配合比,或掺加外加剂、掺合料等措施配制而成,其抗渗等级不得小于(),其试配混凝土的抗渗等级应比设计要求提高()MPa。
导游的素质要求包括()。
幼儿园选择教育内容的依据是()。
《2016年政府工作报告》指出,改革是引领发展的第一动力,必须摆在国家发展全局的核心位置,深入实施创新驱动发展战略。()
Anewreportclaimsthatthemakersofsugar-laden(含糖)drinkssuchassodas,sportsdrinks,energydrinksandfruitdrinkstaked
A、TheterribleeffectsofdroughtonCalifornia.B、Newtechnologiesusedtopreventwaterwaste.C、Amandatoryorderonwatercu
最新回复
(
0
)