首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空; (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
admin
2011-01-29
60
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
(65)________________不属于数据库性能测试的测试指标。
假设关系R1和R2如下图所示:若进行R1R2运算,则结果集分别为(1)元关系,共有(2)个元组。(1)
对于初始为空的栈S,入栈序列为a、b、c、d,且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d,则合法的出栈序列为______。
一个程序的控制流图中有8个节点、12条边。在测试用例数最少的情况下,确保程序中每个可执行语句至少执行一次所需测试用例数的上限是________________。
软件内部/外部质量模型中,以下(66)不是功能性包括的子特性。
程序员甲与同事乙在乙家探讨甲近期编写的程序,甲表示对该程序极不满意,说要弃之重写,并将程序手稿扔到乙家垃圾筒。后来乙将甲这一程序稍加修改,并署乙名发表。以下说法正确的是(11)。
以下关于测试方法的叙述中,不正确的是_______。
若计算机存储数据采用的是双符号位(00表示正号、11表示负号),两个符号相同的数相加时,如果运算结果的两个符号位经()运算得1,则可断定这两个数相加的结果产生了溢出。
计算机采用分级存储体系的主要目的是为了解决()的问题。
阅读以下家庭HFC宽带接入Internet网的技术说明,结合网络连接拓扑图,根据要求回答问题1至问题5。【说明】混合光纤一同轴电缆网(即HFC网)将光纤敷设到小区,再通过光电转换节点,利用CATV的总线式同轴电缆网连接到用户,从而为用户提供Int
随机试题
A.收敛固涩B.发散行气C.补虚缓急D.坚阴和通泄E.软坚散结、泻下通便辛味所示作用是()。
用于判定高压灭菌效果,包裹中心可放置:
新的财政年度的收支计划指标以上年度指标执行数为基础,并考虑本年度的实际情况之后调整确定,称为()。
水利工程建设中发生的自然灾害、公共卫生事件、社会安全等事件,依照()相应应急预案执行。
A点高程为36.05m,现取A点为后视点,B点为前视点,水准测量,前视点读数为1.12m,后视点读数为1.22m,则B点的高程为()。
对于我国证券回购的报价,说法不正确的有()
下列预算编制方法中,不受现行预算的束缚,有助于保证各项预算开支合理性的是()。
有黑、白、蓝三种颜色袜子各7双,装在一个纸盒里,现从纸盒中任意取出袜子,为了确保至少有2双不同颜色的袜子,至少要取出()只袜子。
资本主义社会的幕本矛盾主要表现在( )
设f(x)在区间[a,b]上二阶连续可导,证明:存在ξ∈(a,b),使得
最新回复
(
0
)