简答题

课程名称:程序员

题目:阅读下列说明和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+1x[k]:第k个访问的顶点编号,从0开始Visited[x[k]]:第k个顶点的访问标志,0表示未访问,1表示已访问(2)C程序#include <stido.h> #include <stidb.h> #define MAX 100 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[i]=0; visited [i]=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; ( ); } } }【问题1】(10分)根据题干说明。填充C代码中的空(1)~(5)。【问题2】(5分)根据题干说明和C代码,算法采用的设计策略为( ),该方法在遍历图的顶点时,采用的是( )方法(深度优先或广度优先)。