首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
admin
2011-01-29
34
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
对有向图进行拓扑排序的方法是:
(1)初始时拓扑序列为空;
(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;
(3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。
函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号,顶点序列为vl,v2,…,vn,图G采用邻接表表示,其数据类型定义如下:
#define MAXVNUM 50 /*最大顶点数*/
typedef struct ArcNode| /*表结点类型*/
int adjvex; /*邻接顶点编号*/
struct ArcNode*nextarc; /*指示下一个邻接顶点*/
{ArcNode;
typedef struct AdjList{ /*头结点类型*/
char vdata; /*顶点的数据信息*/
ArcNode*firstarc; /*指向邻接表的第一个表结点*/
}AdjList;
typedef struct LinkedDigraph /*图的类型*/
int n: /*图中顶点个数*/
AdjList Vhead[MAXVNUM]; /*所有顶点的头结点数组*/
}LinkedDigraph;
例如,某有向图G如图4-1所示,其邻接表如图4-2所示。
函数TopSort中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如下表所示:
【C代码】
int*TopSort(LinkedDigraph G){
ArcNode*P; /*临时指针,指示表结点*/
Queue Q; /*临时队列,保存入度为0的顸点编号*/
int k=0; /*临时变量,用作数组元素的下标*/
int j=0,w=0; /*临时变量,用作顶点编号*/
int*topOrder,*inDegree;
topOrder=(int*)malloc((G.n+1)*sizeof(int));/*存储拓扑序列中的顶点编号*/
inDegree=(int*)malloc((G.n+1)*sizeof(int));/*存储图G中各顶点的入度*/
if(!inDegree||!topOrder) return NULL;
(1); /*构造一个空队列*/
for(j=1;j<=Gn;j++){ /*初始化*/
topOrder[j]=0;inDegree[j]=0;
}
for(j=1;j<=Gn;j++) /*求图G中各顶点的入度*/
for(p=G.Vhead[j].firstarc;p;p=p->nextarc)
inDegree[P->adjvex]+=1;
for(j=i;j<=G.n;J++) /*将图G中入度为0的顶点保存在队列中*/
if(0==inDegree[j]) EnQueue(&Q,j);
while(! IsEmpty(Q)){
(2); /*队头顶点出队列并用w保存该顶点的编号*/
topOrder[k++]=w; /*将顶点W的所有邻接顶点的入度减l(模拟删除顶点w及该顶点出发的弧的操作)*/
for(p=G.Vhead[w].firstarc;p;p=p->nextarc){
(3)-=1;
if(0== (4) ) EnQueue(&Q,P->adjvex);
}/*for*/
}/ * while*/
free(inDegree);
if( (5) )
return NULL;
return topOrder;
}/*TopSort*/
根据以上说明和C代码,填充C代码中的空(1)~(5)。
选项
答案
(1)InitQueue(&Q) (2)DeQueue(&Q,&w) (3)inDegree[p->adjvex] (4)inDegree[p->adjvexj (5)k!=G.N
解析
根据空(1)的后面注释是构造一个空队列,程序的开始已经定义了一个队列Q,那么此处只需初始化这个队列即可,所以空(1)应填InitQueue(&Q)。
根据空(2)后面的解释,如果队列不空,那么就将队列的元素依次出队列,所以空(2)应为DeQueue(&Q,&w)。
空(3)、(4)上下端的功能是将顶点w的所有邻接顶点的入度减l,数组inDegree中存放各个顶点的入度,所以空(3)应为inDegree[p->adjvex],并判断与顶点w相邻的顶点有没有入度为零的顶点,如果有,就把这个顶点入队列,所以空(4)也填inDegree[p->adjvex]。
最后,最外层循环结束,如果拓扑序列中元素的个数k不等于定点数n,那么就说明有向图中存在环,返回NULL上,所以空(5)填k!=G.n。
转载请注明原文地址:https://kaotiyun.com/show/pqDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下关于软件质量属性的叙述中,不正确的是________________。
风险控制不包括______。
面向对象分析与设计是面向对象软件开发过程中的两个重要阶段,下列活动中,(25)不属于面向对象分析阶段。
驻留在多个网络设备上的程序在短时间内同时产生大量的请求消息冲击某Web服务器,导致该服务器不堪重负,无法正常响应其他合法用户的请求,这属于(9)。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
采用________________表示带符号数据时,算术运算过程中符号位与数值位采用同样的运算规则进行处理。
结构化分析(StructuredAnalysis,SA)是面向数据流的需求分析方法,______不属于SA工具。A.分层的数据流图B.数据词典C.问题分析图D.描述加工逻辑的结构化语言、判定表或判定树
通常一个HFC网络由前端(FE)、主数字终端(HDT)、光纤节点(FN)、网络接口单元(NIU)、综合业务单元(ISU)及传输线路等构成。根据HFC网接入Internet网的典型配置,将图6-12所示的拓扑图中(A)~(D)空缺处的名称填写完整(请使用题干
通常一个HFC网络由前端(FE)、主数字终端(HDT)、光纤节点(FN)、网络接口单元(NIU)、综合业务单元(ISU)及传输线路等构成。根据HFC网接入Internet网的典型配置,将图6-12所示的拓扑图中(A)~(D)空缺处的名称填写完整(请使用题干
随机试题
关于医患双方权利与义务的下述口号和做法中,不可取的是
我某公司出口A商品1000箱,该货每箱收购价为100元人民币,国内费用为收购价的15%,增值税额为17元,出口退税率为9%,外销价为每箱19.00美元CFR某港口,每箱应付海运费1.20美元。试计算该商品的换汇成本。
一般要求百年一遇洪水位以上()m的地段,可选作城市用地。
下列关于会计调整的说法中,错误的是()。
中国共产党的成立是马克思列宁主义与()相结合的产物。
“新生代散文”作家大多有写现代诗的背景,诗人所拥有的____________的思维、大胆的想象、敏锐的感觉,将“诗质”____________在散文语言的血液和肌理里。这不同于平铺直叙式的浅浮的诗意.而是自我心灵的体认中____________而成的诗质
小福、小禄、小康、小宁四人是好朋友,又知其中一人是律师,一人是法官,一人是会计,一人是检察官。已知:(1)律师比小禄年龄大。(2)法官比会计年龄大。(3)小康比检察官年龄大。当小王知道了律师、法官、会计、检察官的名字后,就逻辑地推断出四人的唯一排名
物理层传输的数据单位是(3)。
关系代数表达式R×S÷T-U的运算结果是(47)。
A、Heisgoingdriving.B、Heisgoingshopping.C、Heisgoingblowing.D、Heisgoingfishing.D综合理解题。对话中女士看到男士已经准备好了鱼竿和线,男士回答只要再
最新回复
(
0
)