首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在
admin
2018-09-03
35
问题
阅读下列说明和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://jikaoti.com/ti/Lea7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1和问题2。【说明】二层隧道协议L2TP(Layer2TunnelingProtocol)是一种基于点对点协议PPP的二层隧道协议。某网络结构如图2-7所示,采用L2TP来实现网络安全。
请用蒙特卡罗错误随机植入模型估算出被测程序模块中将会遗留下多少个未被发现的隐藏错误。请简要列出计算式子及计算过程。在进行上述分析后,谢工程师感到有些困惑,于是与本研发部门郭工程师进行了讨论。郭工程师告诉他可以借用硬件的MTBF(平均无故障时间)或者MT
Samba的工作原理是:让(1)和NetBIOS这两种协议运行于TCP/IP通信协议之上,且通过Windows的(2)协议让用户的Linux计算机可以在Windows的网络邻居上被看到。Samba服务器配置工具是用来管理Samba共享、用户及基本服
Samba的工作原理是:让(1)和NetBIOS这两种协议运行于TCP/IP通信协议之上,且通过Windows的(2)协议让用户的Linux计算机可以在Windows的网络邻居上被看到。Samba服务器配置工具是用来管理Samba共享、用户及基本服
阅读以下说明,回答问题1和问题2。【说明】在一幢11层的大楼内组建一个局域网,该局域网的连接示意图如图5-4所示。
阅读以下有关网络规划的叙述,回答问题1至问题3。网络工程是一项复杂的系统工程,一般可分为网络规划、网络设计、工程实施、系统测试验收和运行维护等几个阶段。网络规划是在需求分析的基础上,进行系统可行性分析和论证,以确定网络总体方案。网络规划阶段任务完成
阅读以下说明,回答问题1~3。【说明】网络解决方案如图2-5所示,该网络原先使用的使国外品牌的交换机,随着网络规模的扩大,增添了部分国产品牌的交换机,交换机1~5均是国产10M/100Mbit/s自适应交换机,交换机6和交换机7是第3层交换
阅读以下说明和交换机的配置信息,回答问题1-3。【说明】某公司下设3个部门,为了便于管理,每个部门组成一个VLAN,公司网络结构如图1-5所示。【交换机Switch1的部分配置信息】Switch1(config)#
设计布线时,需要考虑哪些主要因素?在设备间子系统设计时,从系统的安全设计上要考虑的主要因素有哪些?
阅读以下说明,回答问题1、问题2、问题3。随着通信市场的日益开放,电信业务正向数据化、宽带化、综合化、个性化飞速发展,各运营商之间竞争日益激烈。而竞争的基本点就在于接入资源的竞争,如何快速、有效、灵活、低成本提供客户所需要的各种业务成为运营商首要考虑的问
随机试题
只要得到适当的教育,任何人都可以成为歌唱家、科学家、诗人。
虚拟存储器的最大容量
教育规律
男性,25岁。下前牙牙龈肿痛出血、口腔恶臭2天。口腔检查发现牙龈缘坏死。初步诊断为:急性坏死溃疡性龈炎。比较恰当的应急处理是
()是土地登记机关进行注册登记的主要依据。
下列评价指标中,属于动态指标的是()。
包舱包板存在的问题有()。
根据《税收征收管理法》的规定,下列各项中,属于税收保全措施的是()。
2011年2月14日后第293天的日期是()。
A、Philosophy.B、Economics.C、Agriculture.D、Management.B
最新回复
(
0
)