首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在
admin
2018-09-03
53
问题
阅读下列说明和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代码中的空(1)~(5)。
选项
答案
1.visited[0]=1 2.visited[x[k]]==0 3.3k==n-1&&c[x[k][x[0]==1 4.visited[x[k]]=1 5.k=k-1
解析
转载请注明原文地址:https://kaotiyun.com/show/NzxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
该企业网络的核心层采用了千兆以太网技术,简述千兆以太网的主要技术特点及优点。图1中防火墙(Firewall)的主要作用是什么?
请用蒙特卡罗错误随机植入模型估算出被测程序模块中将会遗留下多少个未被发现的隐藏错误。请简要列出计算式子及计算过程。在进行上述分析后,谢工程师感到有些困惑,于是与本研发部门郭工程师进行了讨论。郭工程师告诉他可以借用硬件的MTBF(平均无故障时间)或者MT
Samba的工作原理是:让(1)和NetBIOS这两种协议运行于TCP/IP通信协议之上,且通过Windows的(2)协议让用户的Linux计算机可以在Windows的网络邻居上被看到。Samba服务器配置工具是用来管理Samba共享、用户及基本服
Samba的工作原理是:让(1)和NetBIOS这两种协议运行于TCP/IP通信协议之上,且通过Windows的(2)协议让用户的Linux计算机可以在Windows的网络邻居上被看到。Samba服务器配置工具是用来管理Samba共享、用户及基本服
当路由器Router1启用OSPF协议后,将每10秒钟向它的各个接口发送Hello分组,接收到Hello分组的路由器就知道了邻居的存在。如果在40秒内没有从特定的邻居接收到这种分组,路由器就认为那个邻居不存在了。OSPF邻接建立过程主要经过关闭(D
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
认真阅读下列有关Linux操作系统环境下配置Apache服务器的技术说明,根据要求回答问题1至问题5。【说明】随着电子商务日益普及,A公司建构了一台装有RedhatLinux9.0操作系统的虚拟服务器,为各类客户提供网上架构商务站点的Web服
可供使用的合法IP还有多少哪些?请写出。使用内部IP进行地址转换,若用一台主机连接内外两个网络,请说出两种不同的网络接法并进行比较?
阅读以下说明,回答问题1~5,将答案填入对应的解答栏内。某公司在国际网互联中心申请了210.45.12.0/24一个C的IP地址,域名为abc.com.cn。该公司有一台该WEB服务器(IP地址为210.45.12.11,主机名为S1)、一台FT
随机试题
螺杆式压缩机齿高系数一般取()。
《论语·颜渊篇》:“政者,正也。子帅以正,孰敢不正?”说明在古人心目中,政治家的特点是
不属于肠杆菌科的菌属是
在编制概算定额时,对于定额项目划分应坚持的原则是()。
长期借款利息费用在资产负债表日按照实际利率法计算确定,如果实际利率和合同利率差异小,也可以采用合同利率计算确定。( )
1908年,美国人______出版了《一颗自我发现的心》,引来了全世界心理卫生运动。
(2014山东)某单位举办围棋联赛,所有选手的排名都没有出现并列名次。小周发现除自己以外,其他所有人排名数字之和正好是70。问小周排名第几?
依照合同法规定,下列债权不得转让的是()。
电视制作中有哪些画面特技。举出5种并说明。
以下选项中能表示合法常量的是
最新回复
(
0
)