首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和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
74
问题
阅读下列函数说明和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
软件设计师上午基础知识考试
软考中级
相关试题推荐
EIARS-232C定义了DTE和DCE之间的接口,其机械特性规定RS-232C的D型连接器有(11)个插脚,其电气特性与CCITT的(12)兼容。DTE和DCE之间的接口信号线按功能一般可分为(13)4类,使用EIARS-232C接口进行数据通信时,至少
网络协议是计算机网络和分布系统中互相通信的对等层实体间交换信息时必须遵守的规则的集合。100BaseTx中的“100”用于说明网络协议关键成分中的(17)。
TCP是一个面向连接的协议,它提供连接的功能是(31)的,采用(32)来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(33)的分组,这种分组的数量最多可以(34),TCP协议采用滑动窗口协议解决了(35)。
IEEE802.5令牌环(TokenRing)网中,时延是由(1)决定。要保证环网的正常运行,环的时延必须有一个最低限度,即(2)。如果达不到这个要求,可以采用的一种办法是通过增加电缆长度,人为地增加时延来解决。设有某一个令牌环网长度为400m
网络操作系统是使网络上各计算机能方便而有效地共享网络资源,为用户提供所需的各种服务的软件和有关规程的集合。以下是对各种NOS产品的描述。(53)由外层(Shell)和操作系统核心所构成,早期的产品的主要是用作网络文件服务器,并且采用了与TCP/I
两个码子之间的海明距为(22)。码是由码子组成的集合,一个码的海明距离指的是(23)。若一个码要求检测3位错,则该码的海明距离应为,(24)。
Atypicalapplicationofthis(71)isADSL.Itisemergingasthetechnologyforhome-andsmall-officeInternetconnectivity.Itp
在因特网的路由选择协议中,属于外部网络协议的是(27),按固定时间间隔和相邻路由器交换路由表信息的协议是(28)。该协议最大特点是(29),它使用(30)传输信息。此协议报文最大长度、最多可包括的路由数和最大距离分别是(31)。
以太网交换机转发数据包的根据是(44)。访问交换机的方式有多种,配置一台新的交换机时可以(45)进行访问。在键入交换机命令时可使用缩写形式,在Switch#模式下,如果键入“con”,则表示(46)。
随机试题
____________就是典型的合法性监督。
以下哪项脉象的脉体较短()
根据《中华人民共和国防治海岸工程建设项目污染损害海洋环境管理条例》,下列环境保护措施中,属于岸边油库应当采取的有()。
如下为某小企业发生的业务,该小企业12月1日有关资料如下:Ⅰ.总分类账户的期初余额如下:Ⅱ.有关明细分类账户的期初余额如下:应收账款—旺达实业:58500元;原材料—甲材料:2000个,单价10,计:20000元;
采用被动管理的管理者认为()。
在典型的职业生涯通道类型中,描述员工在同一管理层级或技术、技能等级上不同工种之间变动路径的是()。(2008年真题)
优惠利率属于()货币政策工具。
下列有关审计风险的说法中,错误的是()。
当颁发向河道内排放化学物质的许可证时,它们是以每天可向河道中排放多少磅每种化学物质的形式来颁发的。通过对每种化学物质单独计算来颁发许可证,这些许可证所需的数据是基于对流过河道的水量对排放到河道内的化学物质的稀释效果的估计。因此河道在许可证的保护之下,可以免
在报表设计中,用来绑定控件显示字段数据的最常用的计算控件是
最新回复
(
0
)