閱讀下列說明和C代碼，回答問題1至問題2，將解答寫在答題紙的對應欄內

【說明】

一個無向連通圖G上的哈密爾頓(Hamilton)回路是指從圖G上的某個頂點出發(fā)，經過圖上所有其他頂點一次且僅一次，最后回到該頂點的路徑。一種求解無向圖上的哈密爾頓回路算法的基本思想如下：

假設圖G存在一個從頂點u0出發(fā)的哈密爾頓回路u0—u1—u2—u3—...—u0—un-1—u0。算法從頂點u0出發(fā)，訪問該頂點的一個未被訪問的領接頂點u1 ，接著從頂點u1出發(fā)，訪問u1的一個未被訪問的領接頂點u2，...。對頂點ui，重復進行以下操作：訪問ui的一個為被訪問的領接頂點ui+1;若ui的所有領接頂點均已被訪問，則返回到頂點ui-1，考慮ui-1的下一個未被訪問的領接頂點，仍記為ui;直到找到一個哈密爾頓回路或者找不到哈密爾頓回路，算法結束。

【C代碼】

下面是算法的C語言實現(xiàn)。

(1)常量和變量說明

n：圖G中的頂點數(shù)

c[][]：圖G的領接矩陣

k：統(tǒng)計變量，當前已經訪問的頂點數(shù)為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數(shù)組和visited數(shù)組*/

for(i=o;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]&&k (4) ;

k=k+1;

}

else {/*沒有未被訪問過的領接頂點，回退到上一個頂點*/

x[k]=0;

visited[x[k]]=0;

(5) ;

}

}

}

【問題1】(10分)

根據(jù)題干說明，填充C代碼中的空(1)~(5)。

【問題2】(5分)

根據(jù)題干說明和C代碼，算法采用的設計策略是(6)，該方法在遍歷圖的頂點時，采用的是(7)方法(深度優(yōu)先或廣度優(yōu)先)。

信管網參考答案：

（1）visited[0]=1

（2）visited[x[k]]==0

（3）c[x[k]][0]==1

（4）visited[x[k]]=1

（5）k=k-1 或等價交換

（6）回溯法

（7）深度優(yōu)先

查看解析：www.ichunya.com/st/395684405.html