首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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*/
设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。
若有向图采用邻接矩阵表示(例如,图4-1所示有向图的邻接矩阵如图4-3所示),且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作,那么对于有n个顶点、e条弧的有向无环图,实现上述拓扑排序算法的时问复杂度是(7)。
选项
答案
(6)O(n+e) (7)O(n
2
)
解析
邻接表:对有n个顶点和e条弧的有向图而言,在拓扑排序中,若有向图无环,则每个顶点进出队列各一次,共执行e次,搜索算法时间复杂度是由n和e共同决定的,所以总的时间复杂度为O(n+e)。
当用邻接矩阵:对于每个顶点,查找相邻边的时间复杂度是O(n),一共有n个顶点,所以总的时间复杂度是O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/4qDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
风险控制不包括______。
一个程序的控制流图中有8个节点、12条边。在测试用例数最少的情况下,确保程序中每个可执行语句至少执行一次所需测试用例数的上限是________________。
一个Web信息系统所需要进行的测试包括____________。①功能测试②性能测试③可用性测试④客户端兼容性测试⑤安全性测试
为了能按时交付系统,开发小组在实现“确定最优任务分配方案”功能时采用了蛮力的方法。在系统交付后,对可能出现更多任务量的情况,采用更有效的方法来实现该功能,这属于()。
假设系统采用PV操作实现进程同步与互斥。若n个进程共享两台打印机,那么信号量S的取值范围为()。
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。①处应填入?
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
对于逻辑表达式(bufc[i]>223&&bufc[i]<240&&i+2<totalbytes),需要______个测试用例才能完成条件组合覆盖。
通常一个HFC网络由前端(FE)、主数字终端(HDT)、光纤节点(FN)、网络接口单元(NIU)、综合业务单元(ISU)及传输线路等构成。根据HFC网接入Internet网的典型配置,将图6-12所示的拓扑图中(A)~(D)空缺处的名称填写完整(请使用题干
随机试题
下列资源产品中,不征收资源税的是()
下列关于热释光个人剂量仪的描述中,不正确的一项是
Cajal星形细胞染色方法的结果是
下列各项中,哪项表现对诊断尿路感染最有意义
立井基岩施工中,不需要临时支护的作业方式有()。
某公司是一家大型的跨国公司,长期以来,公司高层在纳才、用才方面均采用了科学的管理方法。其人力资源部一贯坚持“考绩定人事”的原则。(他们把员工分为优秀、合格、试用三种,分别享受不同的待遇。公司规定每季度进行一次业绩考评,并根据考评结果使员工晋升到不同的等级。
组织结构是组织为实现共同目标而进行的各种分工和协调的系统,下列属于组织结构的基本构成要素的有()。
()即劳动的计量和工资支付的方式。工资形式的关键,是以何种方式准确地反映和计算劳动者实际提供的劳动数量。
下列生活方式不符合低碳经济要求的是()。
Youarewhatyoueat,orsothesayinggoes.ButRichardWrangham,ofHarvardUniversity,believesthatthisistrueinamorep
最新回复
(
0
)