2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(10)

　　問(wèn)題：--------------------------------------------------------------------------------------

　　1) 為何兩個(gè)for循環(huán)都是從下標(biāo)2開(kāi)始的?尤其是第二個(gè)想不通。

　　答：因?yàn)镻rim算法可以任選起點(diǎn)，通常選定點(diǎn)1為起點(diǎn)，也就是說(shuō)點(diǎn)1一開(kāi)始就在U里面了，自然不必出現(xiàn)在第二個(gè)循環(huán)(在V-U中尋找點(diǎn))中。

　　2) lowcost數(shù)組顧名思義知道是存放最小代價(jià)信息的數(shù)組，但是具體的說(shuō)lowcost放著是什么的最小代價(jià)，比如“l(fā)owcost[i]=c[1][i];”表示的是什么意思(我要帶i的語(yǔ)言描述)?

　　答：存放的是當(dāng)前從點(diǎn)集U到點(diǎn)集V-U的最短邊長(zhǎng)，lowcost[i] = c[1][i]是初始化，開(kāi)始時(shí)點(diǎn)集U中只有點(diǎn)1，因此當(dāng)前點(diǎn)集U到點(diǎn)集V-U的各最短邊長(zhǎng)lowcost[i]就等于點(diǎn)1到點(diǎn)i的邊權(quán)。

　　3) closest[i]=1 又是什么含意呢?

　　答：closest[i]記錄對(duì)應(yīng)lowcost[i]的邊的起點(diǎn)，因?yàn)閘owcost[i]是當(dāng)前終點(diǎn)為i的各條邊中的最小值，再加上一個(gè)closest[i]記錄起點(diǎn)，就能確定最小生成樹(shù)的邊了。closest[i] = 1是初始化，自然每一個(gè)邊都是從點(diǎn)1出發(fā)的。

　　4) 求教第二個(gè)for循環(huán)的整層循環(huán)是寫(xiě)什么，我要每一行的注釋。到底是在作什么??

　　答：

　　for (i=2;i<=n;i++) /*從U之外求離U中某一頂點(diǎn)最近的頂點(diǎn)*/

　　{

　　min=MAXCOST; // 這一段是在U之外找最小值，closest[j] != 0表示是U之外

　　j=1;

　　k=i;

　　while (j<=n)

　　{

　　if(lowcost[j]

　　{

　　min=lowcost[j];

　　k=j;

　　}

　　j++;

　　}

　　printf("(%d,%d)",closest[k],k); /*打印邊，這里就看出closest[k]的用途了嘛*/

　　closest[k]=0; /*將點(diǎn)k加入集合U */

　　for(j=2;j<=n;j++) //更新最短邊和相應(yīng)起點(diǎn)

　　{

　　if (closest[j]!=0&& c[k][j]

　　{

　　lowcost[j]=c[k][j]; //更新最小權(quán)值

　　closest[j]=k; //記錄新邊的起點(diǎn)

　　}

　　}

　　}

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)