软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2024/3/30）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/3/30

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2024/3/30）

阅读下列说明和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）方法（深度优先或广度优先）。
信管网试题答案与解析：www.cnitpm.com/st/395684405.html

信管网考友试题答案分享：

信管网cnitpm613520395848：
1.visited[0] ＝ 1 2.visited[x[k]] == 0 3. 4. 5. 自顶向下 深度优先

信管网cnitpm615344458501：
问题1： （1）：visited[x[0]] ＝ 1； （2）： （3）： （4）： （5）：

信管网weiing：
1、visited[x[0]] ＝ 1 2、visited[x[k]] ＝ 0 3、 4、 5、k=k-1 6、动态规划 7、深度优先

信管网cnitpm509362975264：
问题1： 1： visited[0] ＝ 1 2： c[x[k]][x[k]]==0 3： 4： 5： 问题2： 回溯法 深度优先

信管网suhx：
【问题1】： （1）：c[x[0][1]] ＝ 0，（2）：visited[x[k]] == 0，（3）：，（4）：visited[x[k]] == 1，（5）：k=k-1， 【问题2】： 算法采用的设计策略是回溯，遍历图的顶点时，采用的是深度优先方法

信管网试题答案与解析：www.cnitpm.com/st/395684405.html