首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和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
52
问题
阅读下列函数说明和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接口进行数据通信时,至少
一旦介质空闲就发送数据,假如介质是忙的,继续监听,直到介质空闲后立即奉送数据;如果有冲突就退避,然后再尝试的退避算法称为(60)算法。
在Linux操作系统中,为一块设备名为eth1的网卡分配IP地址和子网掩码的命令是(38)。
Windows2003操作系统的网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(34)之间的WLBS.SYS的筛选器驱动。
TCP是一个面向连接的协议,它提供连接的功能是(31)的,采用(32)来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(33)的分组,这种分组的数量最多可以(34),TCP协议采用滑动窗口协议解决了(35)。
设某单位路由器建立了以下的路由表,若收到分组的目的IP地址为128.96.37.151,则转发的端口是(63),若收到分组的目的IP是128.96.35.151,则转发的端口是(64),若该路由器是该单位与Internet连接的路由器,则该单位分得的IP地
基于TCP/IP的互联网服务中,IP协议提供主机之间的(42)分组传输服务。TCP协议提供端口之间的(43)文传输服务;U-DP属于(44)协议,从其下一层接收了数据以后,根据(45)将之分解咸UDP数据报;应用层的(46)协议可以使用UDP或TCP协议传
RS-232-C是目前常见的一种接口标准,它是由(32)提供制定的。该标准在OSI模型中属于(33)层协议标准,通过RS-232-C来连接两个设备最少要连接(34)条线。这个标准的设计数据速率是处理(35)bit/s。(35)bit/s条件下,采用RS-4
IP服务的3个主要特点是(5)。
计算机内存一般分为静态数据区、代码区、栈区和堆区,若某指令的操作数之一采用立即数寻址方式,则该操作数位于(1)。
随机试题
青年女性,护士,近一周以来疲倦乏力,食欲不振,恶心。查体:巩膜黄染,血ALT720U/L,追问二个月前工作中被污染的针头刺破手指
担任药事管理与药物治疗学委员会(组)主任委员的是
以下是制订《工业企业设计卫生标准》的目的和主要内容,不包括
关于医疗机构中的中药制剂委托配制,下列说法错误的是
背景某大型机场航站楼内安全检查系统工程(涵盖旅客人身、随身行李、托运行李等安全检查设施的安装),托运行李采用后置式五级安检。因专业性强、工期紧,对施工单位的施工设备和施工经验较同类要求高。该机场方在对相关单位进行考察以后,于2015年6月2日向具备承担该
按照缴费方式分类,年金保险可分为( )。
()在任期或法定期限内,不得直接或化名、借他人名义持有、买卖股票,也不得接受他人赠与的股票。
电炉丝通电后热得发红,而与电炉丝连接的铜导线却不太热,这是因为()。
f(x)在(一∞,+∞)上连续,且f(x)的最小值f(x0)
Itiseasiertonegotiateinitialsalaryrequirementbecauseonceyouareinside,theorganizationalconstraints(约束)influence
最新回复
(
0
)