首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和c代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 函数int Toplogical(Linded WDipaph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网
阅读下列函数说明和c代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 函数int Toplogical(Linded WDipaph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网
admin
2005-03-20
113
问题
阅读下列函数说明和c代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数int Toplogical(Linded WDipaph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
typedefstruct Gnode{ /* 邻接表的表结点类型*/
iht adjvex; /* 邻接顶点编号*/
iht weight; /* 弧上的权值*/
street Gnode *nextarc; /* 指示下一个弧的结点*/
}Gnode;
typedef struct Adjlist{ /* 邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode *Firstadj; /* 指向邻接表的第一个表结点*/
}Adjlist;
typedef street LinkedWDigraph{ /* 图的类型*/
int n, e; /* 图中顶点个数和边数*/
struct Adjlist *head; /*指向图中第一个顶点的邻接表的头结点 */
} LinkedWDigraph;
例如,某AOE-网如图5-1所示,其邻接表存储结构如图5-2所示。
【函数】
iht Toplogical(LinkedWDigraph G)
{ Gnode *p;
intj, w, top = 0;
iht *Stack, *ye, *indegree;
ye = (int *)malloe((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("%e ", G.head[w].vdata);
p = G.head[w].Firstadj;
while (p) {
(3);
if ( !indegree [p→adjvex])
Staek[++top] = p→adjvex;
if( (4))
ve[p→adjvex] = ve[w] + p→weight;
p = p→nextarc;
}/* while */
}/* while */ return (5); }/*Toplogieal*/
选项
答案
(1)indegree【p→adjvex】++,及其等价形式 (2)Stack【top--】,及其等价形式 (3)indegree【p→adjvex】--,及其等价形式 (4)ve【w】+p→weight>ve【p→adjvex】,及其等价形式 (5)ve【w】,及其等价形式
解析
本题考查的是数据结构中拓扑排序和求关键路径问题的算法。
在AOE网中,入度为0的顶点为源点,出度为0的顶点为汇点。从源点到汇点的路径中,长度最长的路径称为关键路径。表示事件的顶点存在最早、最晚发生时间。若以顶点v1表示源点、顶点vn表示汇点,则汇点的最早发生时间和最晚发生时间是一致的,并且等于关键路径的长度。
设顶点vj的最早发生时间用ve(j)表示,则ve(j)是指从源点v1到vj的最长路径长度(时间)。这个时间决定了所有从vj发出的弧所表示的活动能够开工的最早时间。
ve(j)计算方法为
其中,T是所有到达顶点j的弧的集合;dut(<i,j>)是弧<i,j>上的权值;n是网中的顶点数(即汇点的序号),如下图所示。
显然,上式是一个从源点开始的递推公式。ve(j)的计算必须在 vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对 AOE网进行拓扑排序,然后按拓扑有序序列逐个求出各项点事件的最早发生时间。
拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程,并且该序列满足:若在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点vi必然在顶点vj之前。
题目中给出的是AOE(Activity On Edge network)网,是一种赋权的有向无环图。
对AOE网进行拓扑排序的方法如下:
①在AOE网中选择一个入度为0(没有前驱)的顶点且输出它。
②从网中删除该顶点及其与该顶点有关的所有边。
③重复上述两步,直至网中不存在入度为0的顶点为止。
在拓扑排序过程中,有可能同时存在多个入度为0的顶点,函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。
进行拓扑排序之前,应先求出网中每个顶点的入度并存入数组indegree[]中,从而,将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减一”,一旦发现某个顶点的入度变为0,就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。
题目中顶点从1开始编号,顶点vi的编号为i,以下代码用于求网中各个顶点的入度。
for(j=1;j<G.n;j++){ /*求网中各顶点的入度*/
p=G.head【j】.Firstadj;
while(p){
(1) ; p=p→nextarc;
}/*while*/
}/*for*/
在有向图中,若以v2为尾的弧有<v2,v4>且权值为30、<v2,v6.>且权值为50,则其的邻接表表示形式如下图所示。
因此,扫描顶点v2的邻接表可以将邻接于v2的所有顶点的入度加10所以,空(1)处应填入“indegree【p→mdjvex】++”或其等价形式。
以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。
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*/
由于入度为0的顶点由栈中弹出,而且根据w在后续代码中所起的作用,可知空(2)处应填入“Stack【top--】”。然后将邻接到顶点w的各个顶点(p→adjvex)的入度减一,所以,空(3)应填入“indegree【p→adjvex】--”或其等价形式。同时,对于顶点p→adjvex而言,当删除其所有引入边之后,从源点出发到达它的最长路径长度也就计算出来了,所以每删除一条到达顶点p→adjvex的引入边,都要查看一下最长路径长度是否需要更新。因此,空(4)填入“ve【w】+p→weight>ve【p→adjvex】”或其等价形式。
最后,汇点的最早发生时间即为该AOE网的关键路径长度。由于AOE网中汇点未必是编号最大的顶点,因此,当它必然是从栈中弹出的最后一个顶点,因此空(5)处填入“ve【w】”。
转载请注明原文地址:https://kaotiyun.com/show/cyDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某航空公司进行促销活动,会员在指定日期范围内搭乘航班将获得一定奖励,奖励分为4个档次,由乘机次数和点数共同决定,如表2-1所示。其中点数跟票面价格和购票渠道有关,规则如表2-2所示。航空公
操作数所处的位置,可以决定指令的寻址方式。操作数包含在指令中,寻址方式为(4);操作数在寄存器中,寻址方式为(5);操作数的地址在寄存器中,寻址方式为(6)。
操作数所处的位置,可以决定指令的寻址方式。操作数包含在指令中,寻址方式为(4);操作数在寄存器中,寻址方式为(5);操作数的地址在寄存器中,寻址方式为(6)。
在UML提供的图中,(36)用于描述系统与外部系统及用户之间的交互;(37)用于按时间顺序描述对象间的交互。
在GB/T 17544中,软件包质量要求包括三部分,即产品描述要求、(53)、程序和数据要求。
对于业务流清晰的系统可以利用(57)贯穿整个测试用例设计过程,在用例中综合使用各种测试方法,对于参数配置类的软件,要用(58)选择较少的组合方式达到最佳效果,如果程序的功能说明中含有输入条件的组合情况,则一开始就可以选用(59)和判定表驱动法。
下列测试工具中,使用(68)执行自动化负载压力测试,使用(69)执行代码静态结构分析,使用(70)执行网络测试。
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(30)设计模式能够有效达到该目的:该系统中的某子模块需要为其他模块捉供访问不同数据库系统(如 Oracle、SQL Server和DB2 UDB等)的功能,这些数
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(30)设计模式能够有效达到该目的:该系统中的某子模块需要为其他模块捉供访问不同数据库系统(如 Oracle、SQL Server和DB2 UDB等)的功能,这些数
随机试题
枣庄“小吃三宝”指的是()。
简述咨询公司拟订方案工作的具体步骤。
战略环境研究的内容包括( )
老年男性,65岁,既往有胆囊结石病史,因上腹痛4小时由家属送诊。查体:意识淡漠,血压90/50mmHg,右上腹部肌紧张。可能的诊断为
背景资料:A公司中标某市城区高架路工程第二标段。本工程包括高架桥梁、地面辅道及其他附属工程:工程采用工程量清单计价,并在清单中列出了措施项目;双方签订了建设工程施工合同,其中约定工程款支付方式为按月计量支付:并约定发生争议时向工程所在地仲裁委员会申请仲裁
股票投资的收益等于()。
21101,9633,8624,7523,954,()。
先秦的春秋战国时期是我国学术和思想蓬勃发展的“百家争鸣”时期,有“九流十家”之说。一般认为,苏秦、张仪是()的代表人物。
在表单中为表格控件指定数据源的属性是
Extract1LastyearIstartedworkwithanewcompany.Unfortunately,inmynewroleIwasrequiredtospeakinpublic,atc
最新回复
(
0
)