首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
admin
2011-01-29
40
问题
阅读下列说明和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://jikaoti.com/ti/74i7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
通过设置基准(枢轴)元素将待排序的序列划分为两个子序列,使得其一个子序列的元素均不大于基准元素,另一个子序列的元素均不小于基准元素,然后再分别对两个子序列继续递归地进行相同思路的排序处理,这种排序方法称为________________。
下图所示的二叉树进行顺序存储(根结点编号为1,对于编号为i的结点,其左孩子结点为2i,右孩子结点为2i+1)并用一维数组BT来表示,已知结点X、E和D在数组BT中的下标为分别为1、2、3,可推出结点G、K和H在数组BT中的下标分别为____________
虚拟存储体系由___________两级存储器构成。
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则________________是一个小顶堆结构。堆结构用二叉树表示,则适宜的二叉树类型为________________。对于10个结点的小顶堆,其
在软件设计和编码过程中,采取“(7)”的做法将使软件更加容易理解和维护。
统一过程(UP)是一种用例驱动的迭代式增量开发过程,每次迭代过程中主要的工作流包括捕获需求、分析、设计、实现和测试等。这种软件过程的用例图(Use Case Diagram)是通过(19)得到的。
函数t()、f()的定义如下所示。若调用函数t()时传递给x的值为3,并且调用函数f()时,第一个参数采用传值(call by value)方式,第二个参数采用传引用(call by reference)方式,则函数t0的返回值为(33).
软件可靠性是指在指定的条件下使用时,软件产品维持规定的性能级别的能力,其子特性(51)是指在软件发生故障或者违反指定接口的情况下,软件产品维持规定的性能级别的能力。
阅读以下说明,回答以下问题,将解答填入答题纸对应的解答栏内。【说明】某学校有三个校区,校区之间最远距离达到61km,学校现在需要建设校园网,具体要求如下:校园网通过多运营商接入互联网,主干网采用千兆以太网将使每个校区的中心节点连起来,每
随机试题
上颌骨骨折X线检查首选
燃油加热到某一温度时,表面蒸发的油气增多,当油气和空气的混合物与明火接触时,发生短暂的闪光,此时的温度即为()
已知Ksp[Mg(OH)2]=5×10-12,现将等体积的0.1mol/L。Mg2+溶液和0.1mol/LNaOH溶液混合,则()。
关于当事人在施工合同中约定的仲裁条款,下列说法正确的是()
背景材料:一个施工项目,材料费往往是占了施工成本的绝大部分,如果加上预算材料费以外材料消耗,则材料费占工程成本的比重更大。因此,对材料费的控制就成为公路施工成本控制的重点。在工程的整个实施期间,必须有严格的材料计划和管理制度,确保料费成本得到有效控制。某
()年,联合国第二十六届大会恢复了中华人民共和国在联合国的合法席位。
近年来城市喜欢搞一些亮化工程,提高城市形象,但是在实施过程中也出现了一些问题,比如带来光污染、能源浪费等问题。某市准备开展城市亮化工程。由市建委具体负责。2011年5月,某大四学生小杨向市建委了解亮化工程的情况,提出要看该工程的建设规划报告,并提议进行亮化
2015年,我国快递业务量完成206.7亿件,实现业务收入2770亿元。全年同城快递业务量完成54亿件,同比增长52.3%;实现业务收入400.8亿元,同比增长50.7%。全国异地快递业务量完成148.4亿件,同比增长47.1%;实现业务收入1512.9亿
A.I度拥挤B.Ⅲ度深覆C.Ⅱ度深覆盖D.Ⅲ度开E.手腕部X线片为判断安氏Ⅲ类骨型反患者能否使用口外上颌前方牵引矫治器,常要看()。
Whatdoesthemanplantowritehispaperon?
最新回复
(
0
)