首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和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
40
问题
阅读下列函数说明和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://jikaoti.com/ti/Qli7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某飞行器供油阀控制软件通过控制左右两边的油箱BL、BR向左右发动机EL、ER供油,既要保证飞行器的安全飞行,又要保证飞行器的平衡,该软件主要完成的功能如下:(1)无故障情况下
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某公司欲开发一套基于Web的房屋中介系统,以有效管理房源和客户,提升成交效率。该系统的主要功能是:(1)房源管理。员工或客户对客户拟出售/出租的意向房进行登记和管理。(2)客户管理。员工对
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某连锁酒店集团实行积分奖励计划,会员每次入住集团旗下酒店均可以获得一定积分,积分由欢迎积分加消费积分构成。其中欢迎积分跟酒店等级有关,具体标准如表2-1所示;消费积分跟每次入住消费金额
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。某汽车维修公司的工时计算模块每天定时根据系统登记的维修信息统计维修工的工时工资。维修工分为学徒、普通维修工和高级维修工三种,三种维修工有不同的时薪标准。图4一1是该模块的类图,图中属性和操作前的“+”
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某公司欲开发一款二手车物流系统,以有效提升物流成交效率。该系统的主要功能是:(1)订单管理:帮买顾问看到有买车线索后,会打电话询问买家是不是需要物流,若需要,帮买顾问就将这个线索发起为订单,
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某航空公司进行促销活动,会员在指定日期范围内搭乘航班将获得一定奖励,奖励分为4个档次,由乘机次数和点数共同决定,如表2-1所示。其中点数跟票面价格和购票渠道有关,规则如表2-2所示。航空公
某数据库中有供应商关系S和零件关系P,其中,供应商关系模式S(Sno,Sname,SZip,City)中的属性分别表示;供应商代码、供应商名、邮编、供应商所在城市;零件关系模式P(Pno,Pname,Color,Weight,City)中的属性分别表示:
在UML提供的图中,(36)用于描述系统与外部系统及用户之间的交互;(37)用于按时间顺序描述对象间的交互。
数据存储在磁盘上的排列方式会影响I/O服务的总时间。假设每磁道划分成10个物理块,每块存放1个逻辑记录。逻辑记录R1,R2,…,R10存放在同一个磁道上,记录的安排顺序如下表所示:假定磁盘的旋转速度为20ms/周,磁头当前处在R1的开始处。若系统顺序处
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
随机试题
Is______48hours______theman-madesatellite______ismadeinourcountrytoorbittheplanetaround?
淋巴细胞和中性粒细胞有两次比例基本相等的时间,分别是
为防止四环素牙的发生,除妊娠和哺乳期的妇女外,几岁以下的小儿也不宜使用四环素
脓肿切开后建立引流时不需考虑的因素有
下列关于地漏及其设置的叙述中,错误的是()。
背景某燃气公司进行一燃气管道铺设工程,该燃气管为DN500mm的钢管,设计压力为0.4MPa,管线位于慢车道上,该管位附近有一条DNl000mm的给水管道,管道材质为钢管。该燃气公司将工程中的土方工程分包给了劳务公司,由于没有在施工前进行安全技术交底,导
下列情况中,不需要对可转换债券的转换价格进行修正的是()。
行政处罚是指行政机关依法对违法反行政管理秩序的公民、法人或其他组织给予制裁的行政行为。据此,下列属于“行政处罚”的是
下列现象中,属于无意识现象的是()
一项全球范围的调查显示,近10年来:吸烟者的总数基本保持不变;每年只有10%的吸烟者改变自己的品牌,放弃原有的品牌而改吸其他品牌;烟草制造商用在广告上的支出占其毛收入的10%。在z烟草公司的年终董事会上,董事A认为,上述统计表明,烟草业在广告上的收益正好等
最新回复
(
0
)