首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 函数int Toplogcal(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网,图中顶点从1
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 函数int Toplogcal(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网,图中顶点从1
admin
2009-05-15
53
问题
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。
【说明】
函数int Toplogcal(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
typedef struct Gnode{ /*邻接表的表节点类型*/
int adjvex; /*邻接顶点编号*/
int weieht; /*弧上的权值*/
stract Gnode *nextarc; /*指示下一个弧的节点*/
}Gnode;
typedef struct Adjlist{ /*邻接表的头节点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode *Firstadj; /*指向邻接表的第一个表节点*/
}Adjlist;
typedef struct LinkedWDigraph{ /*图的类型*/
int n,e; /*图中顶点个数和边数*/
struct Adjlist *head; /*指向图中第一个顶点的邻接表的头节点*/
}LinkedWDigraph;
例如,某AOE网如图5-4所示,其邻接表存储结构如图5-5所示。
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)*sizeof(int)); /*存储网中各顶点的入度*/
Stack=(int*)malloe((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) ye[w),及其等价形式
解析
本题考查AOE网络及其拓扑排序和关键路径,做题前需要先弄清楚图G的存储结构。
根据注释,空(1)所在for循环用来统计AOE网中各顶点的入度。根据入度的定义及题中AOE网的存储结构,当p不为NULL时,应将p->adjvex对应的顶点的入度加1。又数组 indegree正是用来存储各顶点入度的,从紧接着的用来求入度为0的顶点的for循环可看出, indegree数组有效下标是从1到G.n,而顶点的编号正好也是从1开始,故空(1)应填 indegree[p->adjvex]++。
各顶点入度统计结束后,收集入度为0的顶点并将其编号保存在栈Stack(数组模拟)中,栈顶指针为数组下表top。
接下来根据各顶点入度进行拓扑排序输出。
空(2)是给变量w赋值,紧接着将w对应的信息输出,根据拓扑排序算法,此处是选择一个入度为0的顶点输出。Stack栈存储的正是入度为0的顶点编号,故空(2)应填Stack[top--]。注意top指向的栈顶,因此不能写成Stack[--top];另外,这里是出栈操作,不能写成Stack[top]。
根据拓扑排序算法,接下来需要将变量w对应的顶点的所有出边删除,即将对应的顶点的入度减1。类似空(1),空(3)应填indegree[p->adjvex]--。接着判断相应顶点的入度是否为0,为0时将其入栈。
空(4)比较难确定,因程序中并未说明ve数组的用途,注意到函数需要返回关键路径的长度,而至此尚无任何相关语句。因此可以断言ve数组正是为了计算关键路径长度而设置的。关键路径是指从开始到结束点的最长路径,所以只要保证每到一个顶点vx,ve[vx]中存储的都是从开始顶点到vx的最长路径(即顶点vx的最早发生时间)即可。故空(4)应填“ve[w]+p->weight>ve[p->adjvex]”。这样,空(5)很容易得出应填“ve[w]”。
转载请注明原文地址:https://kaotiyun.com/show/B5xZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
RAID级别是指磁盘阵列中硬盘的组合方式,不同级别的RAID为用户提供的磁盘阵列在性能上和安全性的表现上也有不同。图7-2是(45)磁盘阵列的工作原理示意图。
每个盘块512字节的目录文件存放在某一磁盘上,其中文件控制块占64B(文件名占用8B)。若采用“文件控制块分解法”将文件控制块分解成两部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其他描述信息)。那么对于一个共
利用ADSLG.lite的最高速率标准,下载一个150MB文件需要的最短时间约为(31)秒。
国际标准化组织制定的OSI网络管理协议是(36),另外,ISO还定义了5个管理功能域,(37)属于性能管理域。IAB制定的网络管理协议是SNMP,在SNMP管理框架中使用的管理信息库为(38)。管理站(Manager)通过GetRequest命令查询代理(
RS-232是DTE和DCE之间的接口标准,当作为DCE的Modem和作为DTE的计算机相连时,按此标准需要连接的最少线数是(11)。Modem收到呼叫信号后向计算机发送的信号是(12)。当数据发送完毕,计算机向Modem发送的信号是清除(13)、Mode
某工程计划如图4-3所示,由于任务A延迟了一天,为保证该工程按时完成,应将任务(55)缩短一天。
两个码子之间的海明距为(22)。码是由码子组成的集合,一个码的海明距离指的是(23)。若一个码要求检测3位错,则该码的海明距离应为,(24)。
PriortotheavailabilityofenterpriseEDM,locatingadocumentoveraLANcouldbedifficult,andoveraWAN(66)nearlyimpossi
下列复用方式中,(112)是光纤通信中使用的复用方式,EI载波把32个信道按(113)方式复用在一条2.048Mb/s的高速信道上,每条话音信道的数据速率是(114)。
UML提供了一系列的图支持面向对象的分析与设计,其中(13)给出系统的静态设计视图;(14)对系统的行为进行组织和建模是非常重要的;(15)和(16)都是描述系统动态视图的交互图,其中(15)描述了以时间顺序组织的对象之间的交互活动,(16)强调收发消息的
随机试题
20世纪90年代以来,我国的平均关税
儿童身心发展有两个高速发展期:新生儿与青春期,这是身心发展()规律的反映。
不属于钙通道阻滞药的是
海金沙的性状特征
对初始网络图优化的关键工作是()。
废品损失采用按废品所耗定额费用计算不可修复废品成本时,废品的生产成本是按废品数量和各项费用定额计算的,废品的定额费用和实际发生的生产费用之间的差额,计入当期损益。()
“任何人不得强迫自证其罪”是联合国《公民权利和政治权利国际公约》的重要内容,沉默权制度是该原则在警察讯问中的直接体现。沉默权人法,虽可能妨碍到惩治犯罪,但不应过分夸大沉默权的弊端或因噎废食。从欧美诸国的经验来看,通过制度引导,完全可使被追诉人打破沉默,开口
李某以出卖为目的偷盗一名男童,得手后因未找到买主,就产生了自己抚养的想法。在抚养过程中,因男童日夜啼哭,李某便将男童送回家中。关于李某的行为,下列哪个选项是正确的?()
ListentoSarahandMatthewtalkingaboutthepeopletheymetataparty.Whatdotheysayabouteachperson?Forquestions6-10
A、HethinksthechoiceofBaringsFactoryisbetter.B、Hethinksthechoiceofthehospitalisbetter.C、Hethinksthereisnon
最新回复
(
0
)