2011年软考程序员考试复习笔试知识点整理(10)

　　问题：--------------------------------------------------------------------------------------

　　1) 为何两个for循环都是从下标2开始的?尤其是第二个想不通。

　　答：因为Prim算法可以任选起点，通常选定点1为起点，也就是说点1一开始就在U里面了，自然不必出现在第二个循环(在V-U中寻找点)中。

　　2) lowcost数组顾名思义知道是存放最小代价信息的数组，但是具体的说lowcost放着是什么的最小代价，比如“lowcost[i]=c[1][i];”表示的是什么意思(我要带i的语言描述)?

　　答：存放的是当前从点集U到点集V-U的最短边长，lowcost[i] = c[1][i]是初始化，开始时点集U中只有点1，因此当前点集U到点集V-U的各最短边长lowcost[i]就等于点1到点i的边权。

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

　　答：closest[i]记录对应lowcost[i]的边的起点，因为lowcost[i]是当前终点为i的各条边中的最小值，再加上一个closest[i]记录起点，就能确定最小生成树的边了。closest[i] = 1是初始化，自然每一个边都是从点1出发的。

　　4) 求教第二个for循环的整层循环是写什么，我要每一行的注释。到底是在作什么??

　　答：

　　for (i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/

　　{

　　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; /*将点k加入集合U */

　　for(j=2;j<=n;j++) //更新最短边和相应起点

　　{

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

　　{

　　lowcost[j]=c[k][j]; //更新最小权值

　　closest[j]=k; //记录新边的起点

　　}

　　}

　　}

　　软考程序员考试历年真题重点题总结及答案

　　2011年上半年软考报名时间及方式汇总

　　软考程序员考试历年真题汇总(2007年-2010年)