首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和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
26
问题
阅读下列函数说明和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://jikaoti.com/ti/Xca7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
DQDB同时支持(26)两种服务。DQDB子网的双总线结构由(27)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(28)访问控制方式,其中能够提供非等时服务是(29),它用于(30)业务。
在局域网中,常用的介质访问控制方法CSMA/CD、令牌总线和令牌环,IEEE802.4标准采用(16)媒体访问控制方法,IEEE802.5标准采用(17)媒体访问控制方法。其中(18)介质访问控制方法对最短帧长度有要求。假设这种网络的传输速率为10Mbi
RS-232C是(46)之间的接口标准,它规定的电平的表示方式为(47)。当使用RS-232C连接相关设备时,电缆的长度不应超过(48)m。当用RS-232C直接连接两台计算机时,采用零调制解调器方式,其连接方式为(49)。当计算机需要通过相连的M
在X.25网络中,通常用户计算机与网络的(41)相连接。X.25网络的数据链路层使用的标准是(42),它允许在收到应答前连续发送(43)帧数据,为用户提供的最高速率为(44)Kbps。两个X.25网络之间互联时使用(45)协议。
某工程计划如图4-3所示,由于任务A延迟了一天,为保证该工程按时完成,应将任务(55)缩短一天。
TCP通过建立连接为用户提供可靠传输,与数据链路层的连接建立不同,TCP要经过(58)才能确定一个连接,这是因为(59)。TCP采用的差错控制也是超时重发技术,超时时间的设置采用—(60)策略,以便适应互联网的特性。超时时间设置根据的是(61)。TCP的拥
在分布式数据库的类型中,网络中有一个中心站,在这个站点上存放着所有的数据,这种类型是(56)。
Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov
BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01.BGPisbasedonaroutingmethodcalledpathvectorrouting
Routingprotocolsusedifferenttechniquesforassigning(1)toindividualnetwork.Further,eachroutingprotocolformsametricag
随机试题
A.肝内胆管结石B.胆总管结石。胆囊结石C.胰头癌D.胆管癌E.先天性胆管囊肿中年女性,反复发作右上腹痛3年,发作时伴呕吐,数小时后缓解,2天前因进油餐后再次发作上腹痛,伴高热、寒战及黄疸,右上腹及上腹压痛,肝区叩击痛,经手术治疗后症状缓解,黄
下列极限等于1的是()
患者,男,28岁。高热烦躁,神昏谵语,口干舌燥,痰涎壅盛,舌绛,脉数。治宜选用()。
86下列有关粉碎目的的论述中,错误的是
患者,男性,56岁,肝硬化病史7年,此次因腹水入院治疗,某日大量利尿放腹水后出现肝性脑病,导致该患者肝性脑病最主要的诱因是()。
代表业主与业主大会选聘的物业服务企业签订物业服务合同的是()。
苏格拉底教学法包括()。
基于排版的需要,标题文字可能需要对齐。在HTML文件中,如果把标题文字向右对齐,下面写法正确的是()。
对于干部引咎辞职,请问你怎么看?
注意事项1.申论考试是对应考者阅读理解能力、综合分析能力、提出和解决问题能力、文字表达能力和贯彻执行能力的测试。2.作答参考时限:阅读材料30分钟,作答90分钟。3.仔细阅读给定资料,按照后面提出的“作答要求”依次作答。4.考生可以在
最新回复
(
0
)