阅读下列说明和C代码，回答问题1至问题2，将解答写在答题纸的对应栏内。
【说明】
一个无向连通图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
#include
#define MAX 100
void Hamilton（int n,int x［MAX] , int c[MAX][MAX]）｛
int i;
int visited[MAX];
int k;
/*初始化x数组和visited数组*/
for （i=0:i x[i]=0; visited [i]=0; ｝ /*访问起始顶点*/ k=0 （1）； x[0]=0 ; k=k+1 ; /*访问其他顶点*/ while（k>=0）｛ x[k]=x[k]+1; while（x[k] if （（2）&& c [x[k-1]] [x[k]] ==1）｛/*邻接顶点x[k]未被访问过*/ break； ｝else｛ x[k] = x[k] +1 ｝ ｝ if（x[k] for （k=0;k printf（〝%d--〝,x[k] ) ; /*输出哈密尔顿回路*/ ｝ printf（〝%d\n〝,x[0] ) ; return； ｝else if (x[k] （4） k=k+1; ｝else｛/*没有未被访问过的邻接顶点，回退到上一个顶点*/ x[k]=0； visited [x[k]]=0； （5）； ｝ ｝ ｝ 【问题1】（10分） 根据题干说明。填充C代码中的空（1）～（5）。 【问题2】（5分） 根据题干说明和C代码，算法采用的设计策略为（ ），该方法在遍历图的顶点时，采用的 是（ ）方法（深度优先或广度优先）。
正确答案及解析
正确答案
解析
【问题1】（10分）
1. visited[0] = 1
2. visited[x[k]] == 0
3. k==n-1&&c[x[k]][x[0]==1
4. visited[x[k]] = 1
5. k = k - 1
【问题2】（5分）
回溯法、深度优先。
你可能感兴趣的试题
在几种不同类型的软件维护中，通常情况下（）所占工作量最大。
-
- A.更正性维护
- B.适应性维护
- C.完善性维护
- D.预防性维护
- 查看答案
在()中，项目经理的权力是最小的。
-
- A.强矩阵型组织
- B.平衡矩阵组织
- C.弱矩阵型组织
- D.项目型组织
- 查看答案
在项目实施的过程中，项目经理通过项目周报中的项目进度分析图表发现机房施工进度有延期风险。项目经理立即组织相关人员进行分析，下达了关于改进措施的书面指令。该指令属于（ ）
-
- A.检查措施
- B.缺陷补救措施
- C.预防措施
- D.纠正措施
- 查看答案
-
- A.见图A
- B.见图B
- C.见图C
- D.见图D
- 查看答案
-
- A.见图A
- B.见图B
- C.见图C
- D.见图D
- 查看答案