首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
admin
2011-01-29
51
问题
阅读下列说明和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*/
对于图4-1所示的有向图G,写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈,写出函数TopSort执行后得到的拓扑序列。
选项
答案
队列:vl、v2、v5、v4、v3、v7、v6 栈:v1、v2、v5、v4、v7、v3、v6
解析
首先根据原图,可以得出本题中只有V3和V7是同时入队或入栈的。
[*]
转载请注明原文地址:https://kaotiyun.com/show/ZqDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
Bug记录信息包括________________。①被测软件名称②被测软件版本③测试人④错误等级⑤开发人⑥详细步骤
以下关于软件测试目的的叙述中,不正确的是________________。
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则________________是一个小顶堆结构。堆结构用二叉树表示,则适宜的二叉树类型为________________。对于10个结点的小顶堆,其
某开发小组欲开发一个大型软件系统,需求变化较小,此时最不适宜采用()过程模型。
以下说法不正确的选项包括(48)。①软件测试不仅仅指测试的执行,还包括很多其他的活动②软件测试是一个独立的流程,贯穿产品整个生命周期,与其他流程并发地进行③应用H模型有利于资源调配,有助于跟踪测试投入的流向④H模型指
现有四级指令流水线,分别完成取指、取数、运算、传送结果4步操作。若完成上述操作的时间依次为9ns、10ns、6ns、8ns,则流水线的操作周期应设计为(2)ns。
函数t()、f()的定义如下所示。若调用函数t()时传递给x的值为3,并且调用函数f()时,第一个参数采用传值(call by value)方式,第二个参数采用传引用(call by reference)方式,则函数t0的返回值为(33).
系统响应时间和作业吞吐量是衡量计算机系统性能的重要指标。对于一个持续处理业务的系统而言,其(4)。
在性能测试中,关于数据准备,(65)描述是正确的。①识别数据状态验证测试案例。②初始数据提供了基线用来评估测试执行的结果。③业务数据提供负载压力背景。④脚本中参数数据真实模拟负载。
随机试题
张某为自己的服装厂向甲保险公司投保100万元,并已交付3年保费。张某为偿还服装厂到期的债务,谎称自己的服装厂全部被烧毁,向甲保险公司提出申请给付保险金,下列说法正确的是
简述耐用产品质量特性及其含义。
女,44岁。左乳房外上象限4cm×3cm肿块,距乳头距离5cm,可推动,但是患者双手叉腰时肿块活动度明显受限,左腋窝未扪及肿大淋巴结。该患者最佳的定性诊断方法为
患者,男,20岁,阵发性喘息10年余,每年秋季发作,发作时哮喘并咯大量稀薄白痰,咯痰后症状稍好转,应考虑为()
甲公司本年度委托乙商店代销一批零配件,代销价款800万元(不含增值税),成本为500万元。本年度收到乙商店交来的代销清单,代销清单列明已销售代销零配件的30%,甲公司收到代销清单时向乙商店开具增值税发票。乙商店按不含增值税代销价款的5%收取手续费。则甲公司
下列对()的执行不属于执行刑罚工作。
10,12,18,36,90,( )
罪犯王某,17岁,因犯伤害罪被一审法院判处有期徒刑两年。下列选项中正确的有()。
LAPDChiefCharlieBeck’stenurehashelpedanswerquestionsthatlingeredaftertheRampartconsentdecreeendedandoutsiderC
Humoristhemosteffectivemeansofhandlingthedifficultsituations.Itcanbeusedfor【C1】______updifferences,apologizing
最新回复
(
0
)