首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和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
105
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某公司欲开发一套基于Web的房屋中介系统,以有效管理房源和客户,提升成交效率。该系统的主要功能是:(1)房源管理。员工或客户对客户拟出售/出租的意向房进行登记和管理。(2)客户管理。员工对
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某连锁酒店集团实行积分奖励计划,会员每次入住集团旗下酒店均可以获得一定积分,积分由欢迎积分加消费积分构成。其中欢迎积分跟酒店等级有关,具体标准如表2-1所示;消费积分跟每次入住消费金额
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。某汽车维修公司的工时计算模块每天定时根据系统登记的维修信息统计维修工的工时工资。维修工分为学徒、普通维修工和高级维修工三种,三种维修工有不同的时薪标准。图4一1是该模块的类图,图中属性和操作前的“+”
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。某汽车维修公司的工时计算模块每天定时根据系统登记的维修信息统计维修工的工时工资。维修工分为学徒、普通维修工和高级维修工三种,三种维修工有不同的时薪标准。图4一1是该模块的类图,图中属性和操作前的“+”
阅读下列C程序,回答问题,将解答填入答题纸的对应栏内。【C程序】intisbinary(constvoid*buf,constsizetbuf—fen){sizetsuspiciousbytes=0;sizettotal—by
某评测机构A承接了公司B开发的ERP软件的测试工作,负责该项目的软件评测师甲,为了提高自己在ERP方面的知识,向A机构的负责人提出要到开发ERP软件的公司D做兼职开发工作的请求。当测试工作正在进行时,B公司为了申报某科技奖项,希望A机构能先出具一个证明其软
操作数所处的位置,可以决定指令的寻址方式。操作数包含在指令中,寻址方式为(4);操作数在寄存器中,寻址方式为(5);操作数的地址在寄存器中,寻址方式为(6)。
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
黑盒测试是通过软件的外部表现来发现软件缺陷和错误的测试方法,具体地说,黑盒测试用例设计技术包括(42)等。现有一个处理单价为1元的盒装饮料的自动售货机软件,若投入1元币,按下“可乐”、“雪碧”或“红茶”按钮,相应的饮料就送出来,若投入的是2元币,在送出饮料
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
随机试题
期货合约标的选择,一般需要考虑的条件包括()。
自燃点是指在规定条件下,不用任何辅助引燃能源而达到燃烧的最低温度。对于柴油、煤油、汽油、蜡油来说,其自燃点由低到高的排序是()。
Whilecautiousinterpretationisneeded,thefindingsaddtoagrowingbodyofevidenceindicatingthatlimitingsugarydrinkco
用量过大时,可以引起谷草转氨酶或谷丙转氨酶活性增高的药物为
小肠的主要生理功能是
等直杆受力如下图所示,其横截面积A=100mm2,则截面,m-m上的正应力为()。
下列符合人机分配原则的措施是()
炉火臧克家金风换成了北风,秋去冬来了。冬天刚刚冒了个头,落了一场初雪,我满庭斗艳争娇的芳菲,顿然失色,鲜红的老来娇,还有各色的傲霜菊花,一夜全白了头。两棵丁香,叶子簌簌辞柯
说明:根据下列要求写一封商业信函。1)在2014年2月的《儿童玩具》杂志上看到贵公司的洋娃娃产品广告,很感兴趣;2)想了解详细信息,期望能寄一份洋娃娃的目录和最新价格表;3)如质量满意,价格合理,可以长期大量订购。Wordsforref
【B1】【B4】
最新回复
(
0
)