试题内容

阅读下列说明和C代码，回答问题1至问题2，将解答写在答题纸的对应栏内
【说明】
一个无向连通图G上的哈密尔顿（Hamilton）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。一种求解无向图上的哈密尔顿回路算法的基本思想如下：
假设图G存在一个从顶点u0出发的哈密尔顿回路u0—u1—u2—u3—...—u0—un-1—u0。算法从顶点u0出发，访问该顶点的一个未被访问的领接顶点u1 ，接着从顶点u1出发，访问u1的一个未被访问的领接顶点u2，...。对顶点ui，重复进行以下操作：访问ui的一个为被访问的领接顶点ui+1；若ui的所有领接顶点均已被访问，则返回到顶点ui-1，考虑ui-1的下一个未被访问的领接顶点，仍记为ui；直到找到一个哈密尔顿回路或者找不到哈密尔顿回路，算法结束。
【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 4Void Hamilton(int n,int x[MAX],int c[MAX][MAX]){
int i;
int visited[MAX];
int k;
/*初始化x数组和visited数组*/
for(i=o;ix[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;kprintf(“%d--”,x[k]);/*输出哈密尔顿回路*/
}
printf(“%d\n”,x[0]);
return;
}
else if(x[k]&&k (4)   ;
k=k+1;
}
else {/*没有未被访问过的领接顶点，回退到上一个顶点*/
x[k]=0;
visited[x[k]]=0;
(5)  ;
}
}
}
【问题1】（10分）
根据题干说明，填充C代码中的空（1）~（5）。
【问题2】（5分）
根据题干说明和C代码，算法采用的设计策略是（6），该方法在遍历图的顶点时，采用的是（7）方法（深度优先或广度优先）。
查看答案