軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：www.xomuzic.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2025/3/22）在線測試：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2025/3/22

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2025/3/22）

閱讀下列說明和C代碼，回答問題1至問題2，將解答寫在答題紙的對應(yīng)欄內(nèi)
【說明】
一個無向連通圖G上的哈密爾頓（Hamilton）回路是指從圖G上的某個頂點(diǎn)出發(fā)，經(jīng)過圖上所有其他頂點(diǎn)一次且僅一次，最后回到該頂點(diǎn)的路徑。一種求解無向圖上的哈密爾頓回路算法的基本思想如下：
假設(shè)圖G存在一個從頂點(diǎn)u0出發(fā)的哈密爾頓回路u0—u1—u2—u3—...—u0—un-1—u0。算法從頂點(diǎn)u0出發(fā)，訪問該頂點(diǎn)的一個未被訪問的領(lǐng)接頂點(diǎn)u1 ，接著從頂點(diǎn)u1出發(fā)，訪問u1的一個未被訪問的領(lǐng)接頂點(diǎn)u2，...。對頂點(diǎn)ui，重復(fù)進(jìn)行以下操作：訪問ui的一個為被訪問的領(lǐng)接頂點(diǎn)ui+1；若ui的所有領(lǐng)接頂點(diǎn)均已被訪問，則返回到頂點(diǎn)ui-1，考慮ui-1的下一個未被訪問的領(lǐng)接頂點(diǎn)，仍記為ui；直到找到一個哈密爾頓回路或者找不到哈密爾頓回路，算法結(jié)束。
【C代碼】
下面是算法的C語言實(shí)現(xiàn)。
（1）常量和變量說明
n：圖G中的頂點(diǎn)數(shù)
c[][]：圖G的領(lǐng)接矩陣
k：統(tǒng)計(jì)變量，當(dāng)前已經(jīng)訪問的頂點(diǎn)數(shù)為k+1
x[k]：第k個訪問的頂點(diǎn)編號，從0開始
visited[x[k]]:第k個頂點(diǎn)的訪問標(biāo)志，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;ix[i]=0;
Visited[i]=0;
}
/*訪問起初頂點(diǎn)*/
K=0;
(1)  ;
x[0]=0;
k=k+1;
/*訪問其它頂點(diǎn)*/
while(k>0){
x[k]=x[k]+1;
while(x[k]if(   (2)   &&c[x[k-1]][x[k]]==1){/*領(lǐng)接頂點(diǎn)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 {/*沒有未被訪問過的領(lǐng)接頂點(diǎn)，回退到上一個頂點(diǎn)*/
x[k]=0;
visited[x[k]]=0;
(5)  ;
}
}
}
【問題1】（10分）
根據(jù)題干說明，填充C代碼中的空（1）~（5）。
【問題2】（5分）
根據(jù)題干說明和C代碼，算法采用的設(shè)計(jì)策略是（6），該方法在遍歷圖的頂點(diǎn)時，采用的是（7）方法（深度優(yōu)先或廣度優(yōu)先）。
信管網(wǎng)試題答案與解析：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2025/3/22

信管網(wǎng)考友試題答案分享：

信管網(wǎng)cnit**************：
1.visited[0] ＝ 1 2.visited[x[k]] == 0 3. 4. 5. 自頂向下 深度優(yōu)先

信管網(wǎng)cnit**************：
問題1： （1）：visited[x[0]] ＝ 1； （2）： （3）： （4）： （5）：

信管網(wǎng)weii**：
1、visited[x[0]] ＝ 1 2、visited[x[k]] ＝ 0 3、 4、 5、k=k-1 6、動態(tài)規(guī)劃 7、深度優(yōu)先

信管網(wǎng)cnit**************：
問題1： 1： visited[0] ＝ 1 2： c[x[k]][x[k]]==0 3： 4： 5： 問題2： 回溯法 深度優(yōu)先

信管網(wǎng)su**：
【問題1】： （1）：c[x[0][1]] ＝ 0，（2）：visited[x[k]] == 0，（3）：，（4）：visited[x[k]] == 1，（5）：k=k-1， 【問題2】： 算法采用的設(shè)計(jì)策略是回溯，遍歷圖的頂點(diǎn)時，采用的是深度優(yōu)先方法

信管網(wǎng)試題答案與解析：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2025/3/22