首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在
admin
2018-09-03
37
问题
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。
【说明】
一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在一个从顶点V0出发的哈密尔顿回路V1—V2—V3—…—Vn-1—V0。算法从顶点V0出发,访问该顶点的一个未被访问的邻接顶点V1,接着从顶点V1出发,访问V1一个未被访问的邻接顶点V2,…;对顶点Vi,重复进行以下操作:访问Vi的一个未被访问的邻接接点Vi+1;若Vi的所有邻接顶点均已被访问,则返回到顶点Vi-1,考虑Vi-1的下一个未被访问的邻接顶点,仍记为Vi;直到找到一条哈密尔顿回路或者找不到哈密尔顿回路,算法结束。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
n:图G中的顶点数
c[][]:图G的邻接矩阵
k:统计变量,当前已经访问的顶点数为k+1
x[k]:第k个访问的顶点编号,从0开始
Visited[x[k]]:第k个顶点的访问标志,0表示未访问,1表示已访问
(2)C程序
#include<stido.h>
#include<stidb.h>
#define MAX100
void Hamilton(int n,int x[MAX,int c[MAX][MAX]){
int;
int visited[MAX];
int k;
/*初始化x数组和visited数组*/
for(i=0:i<n;i++)(
x
=0;
visited
=0,
}
/*访问起始顶点*/
k=0
( );
X[0]=0
K=k+1
/*访问其他顶点*/
while(k>=0){
X[k]=x[k]+1;
while(x[k]<n){
if( )&&c[x[k-1]][x[k]=1){/*邻接顶点x[k]未被访问过*/
break:
}else{
x[k]=x[k]+1
}
}
if(x[k]<n&&()(/*找到一条哈密尔顿回路*/
for(k=0,k<n;k++){
prinf("%d--",x[k];/*输出哈密尔顿回路*/
}
prinf("%d--",x[0],
return;
}else if x[k]<n&&k<n-1)(/*设置当前顶点的访问标志,继续下一个顶点*/
( );
k=k+1;
}else(/*没有未被访问过的邻接顶点,回退到上一个顶点*/
x[k]=0;
visited x[k]=0;
( );
}
}
}
根据题干说明和C代码,算法采用的设计策略为( ),该方法在遍历图的顶点时,采用的是( )方法(深度优先或广度优先)。
选项
答案
回溯法、深度优先。
解析
转载请注明原文地址:https://kaotiyun.com/show/VzxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请用蒙特卡罗错误随机植入模型估算出被测程序模块中将会遗留下多少个未被发现的隐藏错误。请简要列出计算式子及计算过程。假设该宽带路由器应用于某小型局域网,NanOs程序去年全年处理业务约250万个单位数据,其中5%的业务处理中每个业务需对宽带路由器嵌入式微
光接入网(OAN)由ONU、ODN和OLT等三大部分组成。请将以下所提供的网络设备的序号填写到如图3-6所示的网络结构图中(1)~(5)空缺处对应的位置。【供选择的设备】①ONU②OLT③光分路器④光收发器⑤
双绞线可以制作成直连线和交叉线两种形式,在图3-12所示的拓扑结构中,交换机与路由器(Router)相连的双绞线应制作成什么形式?仔细阅读以下与路由器(Router)的快速以太网接口实现不同VLAN间路由的相关配置信息,结合图3-12所示的拓扑结构图
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?为了保证FTP服务器的数据安全,每个在读取文件时,只能读取和执行相关文件,请问在
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如想将某用户在设咸FTP服务器管理员,其用户名称不变,请问在“Privileg
请阅读以下说明和Socfon程序,将应填(n)处的字句写在对应栏内。【说明】网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。以下是一个简单的客户机程序(服务器程序略),其工
请分别说出(1)与(2)的设备名称。假设有一个50M的文件从终端用户上传至服务器,需要的最短时间是多少?
设计布线时,需要考虑哪些主要因素?在工作区内,信息插座的安装一般在什么位置?
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。某公司设置VPN服务器允许外地的公司员工通过Internet连接到公司内部网络,如图4-1所示。在由L2TP构建的VPN中,主要由(6)和(7)两种类型的服务器构成。
学校根据网络需求选择了四种类型的交换机,其基本参数如表1-2所示。根据网络需求、拓扑图和交换机参数类型,在图1-1中,Switch1应采用(5)类型交换机,Switch2应采用(6)类型交换机,Switch3应采用(7)类
随机试题
神经细胞静息电位的数值接近于()
梅与松、竹并称为“岁寒三友”,以其高洁、坚强、谦虚的品格,给人以立志奋发的激励,常被古人用来咏物言志。以下诗词哪一句描写的不是梅花?
ManyfamiliesintheUnitedStateshavealargerincomenowthaneverbefore,butpeoplearefindingitdifficulttomakeendsm
患儿,出生22天,口腔黏膜出现散在白色斑点,状如凝乳,不易剥离,若强行撕脱,则暴露出血创面,烦躁拒食,啼哭不安,体温36.9℃。该患儿可能是
某在建机场的飞行区指标Ⅱ为E,跑道长度3200m,宽60m。某施工单位承揽了1800m土基填方施工工程。在土基施工过程中,一层土基处理完成后,施工单位检验了16个点位的平整度,检验结果为3~4cm的2个,2~3cm的3个,1~2cm的8个,1cm以下的3个
资料1南京万和电子有限公司(海关注册编号3201331111)在投资总额内进口设备一批。货物进口前,该公司已向主管海关取得编号为Z22004A×××××的征免税证明,该证明海关签注为“鼓励项目”。货物委托上海申华进出口公司(海关注册编号310491
涨价:滞销
秘书处理人际关系的准则除了礼貌礼仪、宽容体谅、赞美他人外,还有()。
根据我国相关法律法规的规定,城市规划管理权必须集中,也就是由城市规划主管部门集中管理。下列权限中,()属于城市规划管理权。
OrganicAgricultureTheideathatshoppingisthenewpoliticsiscertainlyenticing.Nevermindtheballotbox:votewithy
最新回复
(
0
)