阅读下列说明和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分)
回溯法、深度优先。
在几种不同类型的软件维护中,通常情况下()所占工作量最大。
在()中,项目经理的权力是最小的。
在项目实施的过程中,项目经理通过项目周报中的项目进度分析图表发现机房施工进度有延期风险。项目经理立即组织相关人员进行分析,下达了关于改进措施的书面指令。该指令属于( )
The IT service manager resigns from a project that meets the scheduleand budget. After hiring an alternativenew manager, the team is opposed to the comments from the new manager. The team is at () developmentstages。
()is closet to Deming's definition of Quality。
The IT service manager has learned that a software canimprove the efficiency of current and future project tasks. Because the software is fresh to the Company. Theengineer is not familiar with the software. The lT service manager decides to send the highest level engineero attend the external training course. The proiect manager uses () risk strategies。
The process control charts are used ()。