首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和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
76
问题
阅读下列函数说明和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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在OSI网络管理标准中定义了网络管理的5大功能。对历史数据进行分析、统计和整理,为未来的网络规划提供参考的功能属于(41);提供一系列实时数据采集、分析和可视化工具对流程、负载、丢包、温度、内存、延迟等网络设备和线路进行实时检测的功能属于(42);接收报警
DQDB同时支持(26)两种服务。DQDB子网的双总线结构由(27)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(28)访问控制方式,其中能够提供非等时服务是(29),它用于(30)业务。
在FDM中,主要通过(1)技术,使各路信号的带宽(2)。使用FDM的所有用户(3)。从性质上说,FDM比较适合于传输(4),FDM的典型应用是(5)。
RSA算法的一个比较知名的应用是(41),其协商层利用RSA公钥进行身份认证,记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。
每个盘块512字节的目录文件存放在某一磁盘上,其中文件控制块占64B(文件名占用8B)。若采用“文件控制块分解法”将文件控制块分解成两部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其他描述信息)。那么对于一个共
RS-232C是(46)之间的接口标准,它规定的电平的表示方式为(47)。当使用RS-232C连接相关设备时,电缆的长度不应超过(48)m。当用RS-232C直接连接两台计算机时,采用零调制解调器方式,其连接方式为(49)。当计算机需要通过相连的M
TCP是互联网中的(6)协议,使用(7)次握手协议建立连接。当主动方发出SYN连接请求后,等待对方回答(8)。这种建立连接的方法可以防止(9)。TCP使用的流量控制协议是(10)。
依据著作权法,计算机软件著作权保护的对象是指(19)。
Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols,orstaticrouting,
随机试题
患者,男,40岁。误服敌敌畏约200ml,出现呼吸困难,面肌细颤,其原因是
根据一定标准和原则制定的同类法律规范的总和,被称为()
证券公司短期融资券是指证券公司以短期融资为目的,在()发行的、约定在一定期限内还本付息的金融债券。
某商品流通企业拟选择经营甲、乙、丙、丁四类商品中的一类。由于未来市场需求无法做到比较精确的预测,只能大致估计为需求量较高、需求量一般和需求量较低三种情况,并且不知道这三种情况的发生概率,只知道三种情况下不同类商品的估算损益额(万元),如下表所示。该企业的总
(2009年真题)最基本的出版物商品竞争方式是()。
关于互联网,习近平总书记近年来多有论述。在网络安全和信息化工作座谈会上,习近平总书记不少精辟巧妙的比喻直陈核心技术发展“隐患”,直指难点、痛点。下列有关比喻说法错误的是()。
设向量组α1,α2,…,αm线性无关,β1可由α1,α2,…,αm线性表示,但β2不可由α1,α2,…,αm线性表示,则().
设x∈(0,1),证明下面不等式:(1)(1+x)ln2(1+x)<x2;(2).
对建立良好的程序设计风格,下列描述正确的是()。
LastyearafterIhadleftasmallvillageinthesouthofFrance.Idroveomofilenexttown.Onthewayayoungmansloppedme
最新回复
(
0
)