首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空: (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧; (3)重复(2),
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空: (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧; (3)重复(2),
admin
2014-11-13
66
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】对有向图进行拓扑排序的方法是:
(1)初始时拓扑序列为空:
(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;
(3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSoa(LinkedDigraphG)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号,顶点序列为v1,v2,…,vn,图G采用邻接表示,其数据类型定义如下:
#def ine NAXVNUM 50 /*最大顶点数*/
typedef structArcNode( /*表节点类型*/
int adjvex; /*邻接顶点编号*/
struct ArcNode*nextarc; /*指示下一个邻接顶点*/
}ArcNode:
typedef struct Adj List( /*头节点类型*/
char vdata; /*顶点的数据信息*/
ArcNode*firstarc; /*指向邻接表的第一个表节点*/
}Adj List;
typedef struct LinkedDigraph( /*图的类型*/
int n; /*图中顶点个数*/
AdjLiSt Vhead[MAXVNUM]; /*所有顶点的头节点数组*/
}LinkedDigraph;
例如,某有向图G如图15.3所示,其邻接表如图15-4所示。
函数T0pSon中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如表15—2所示:
【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)*Si zeof(int)); /*存储拓扑序列中的顶点编号*/
inDegree=(int*)malloc((G.n+1)*sizeof(int)); /*存储图G中各顶点的入度*/
if(!inDegree I I!toporder)return NULL;
(1); /*构造一个空队列*/
for(j=1;J<=G.n;J++)( /*初始化*/
toporder[J]=0; inDegree[j]=0;
}
for(J=1;J<=G.n;J++) /*求图G中各项点的入度*/
for(P=G.Vhead[j].firstarc;P;P=p一>nextarc)
inDegree[p一>adjvex]+=1;
for(j=1;J<=G.n;j++) /*将图G中入度为0的顶点保存在队列中*/
i f(0==inDegree[j])EnQueue(&Q,j);
whi le(!IsEmpty(Q))(
(2) ; /*队头顶点出队列并用W保存该顶点的编号*/
toporder[k++]=W;
/*将顶点W的所有邻接顶点的入度减1(模拟删除顶点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一>adjvex]或其等价形式(5)k
解析
本题考查数据结构和算法中的拓扑排序算法。在拓扑排序过程中,需要将入度为O的顶点临时临时存储起来。函数中用一个队列暂存入度为0且没有进入拓扑序列的顶点。显然,空(1)处应填入InitQueue(&Q)。根据注释,空(2)处应填入DeQueue(&Q,&w),实现队头元素出队列的处理。题中图采用邻接表存储结构,当指针p指向vi邻接表中的节点时,p一>adjvex表示vi的一个邻接顶点,删除Vi至顶点p一>adjvex的弧的操作实现为顶点p一>adjvex的入度减1,因此,空(3)处应填入inDegree[.p一>adIjvex],当顶点p一>adjvex的入度为0时,需要将其加入队列,因此空(4)处也应填入inDegree[p>adjvex]。空(5)处判断是否所有顶点都加入拓扑序列,算法中变量k用于对加入序列的项点计数,因此,空(5)处应填入“k
转载请注明原文地址:https://kaotiyun.com/show/aZDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
根据图3-1所给出的网络连接方式及相关的网络参数,区域(A)与区域(B)中计算机的网络参数配置(如图3-2所示)为:区域(A)计算机“IP地址”(范围):(1):区域(A)计算机“子网掩码”;(2);区域(A)计算机“默认网关”:(
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持在系统控制台,______用Ctrl+Alt+Delete组合键来重新引导服务器。A.允许B
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
请阅读下列SwitchA的配置信息,并在(1)~(5)处解释该语句的作用。Switch>enable(进入特权模式)Switch#configterminal(进入配置模式)Switch(config)#hostnameSwi
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址在DHCP服务器安装完成后,DHCP控制台如图3-4所示。
ARP木马利用M(1)协议设计之初没有任何验证功能这一漏洞而实施破坏。网络正常时,运行如下命令,可以查看主机ARP缓存中的IP地址及其对应的MAC地址:C:\>arp(8)A.-sB.-dC.-allD.-a假设
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
阅读以下说明,回答问题1至问题6。【说明】某公司要在Windows2003Server上搭建内部FTP服务器,服务器分配有一个静态的公网IP地址200.115.12.3。
随机试题
Thetimewasnotfaroffwhenhe______thisdecision.
患者男,17岁。高热5天伴纳差3天就诊,当天查血压105/75mmHg,左趾甲沟部破溃流脓,左侧小腿肿胀,皮肤发红不明显。白细胞计数20×109/L,中性粒细胞为0.85%。经处理3天后病人高热不退,且血压和血小板计数下降,此时病人可能合并有
血液中的胆红素主要由何种物质分解而来
人力资源是指能够推动社会和经济发展的具有智力劳动和体力劳动能力的人们的总和。下列选项中不构成人力资源质量的是( )。
用白光光源进行双缝实验,若用一个纯红色的滤光片遮盖一条缝,用一个纯蓝色的滤光片遮盖另一条缝,则()。
上级机关就某校开学收费事项进行询问,该校答复时应使用()。
2015年8月8~11日台风“苏迪罗”给台湾、福建、浙江、江苏等地造成严重影响,下图为台风“苏迪罗”移动示意图,完成问题。10日14时,江苏盐城的主导风向是()。
教师专业化发展的核心I司题是()。
宣政院(2011年历史学统考真题)
Ididn’tsayanythingtohimaboutyou,____________(我发誓).
最新回复
(
0
)