2. 计算机
  3. 阅读下列说明和C代码，回答以下问题，将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。哈密尔顿回路算法的基础如下：假设图G存在

阅读下列说明和C代码，回答以下问题，将解答写在答题纸的对应栏内。 【说明】 一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。哈密尔顿回路算法的基础如下：假设图G存在

admin2018-09-03  44
问题 阅读下列说明和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

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)