2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 若要在N个城市之间建立通信网络，只需要N—1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5—1所示，

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 若要在N个城市之间建立通信网络，只需要N—1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5—1所示，

admin2014-10-11  29
问题 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。
【说明】
若要在N个城市之间建立通信网络，只需要N—1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5—1所示，边表示城市间通信线路，边上标示的是建立该线路的代价。
【图5一1】
无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵足对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。现用Prim算法生成网络的最小生成树。由网络G=(V，E)构造最小生成树T=(U,TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V—U里的边中，找出权值最小的边(u，v)，将边加入TE，并将顶点v加入集合U，重复上述操作直到U=V为止。函数中使用的预定义符号如下：
    }}define MAX 32768／*无穷大权，表示顶点问不连通*／
    #define MAXVEx 3 0／*图中顶点数目的最大值*／
    typedef  struct{
    int startVex，stopVex；    ／*边的起点和终点*／
    float weight；    ／*边的权*／
    }Edge；
    typedef  struct{
    char vexs[．MAXVEx]j    ／*顶点信息*／
    float arcs[MAXVEx*(MAXVEx一1)／2]；    ／*邻接矩阵信息，压缩存储*／
    int n；    ／*图的顶点个数*／
    )Graph；
    【函数】
    void primMST(Graph*pGraph，  Edge mst[])
    {
    int i，j,k,min,vx,vy：
    float weight，minWeight；
    Edge edge；
    for(i=0；in一1；  i++){
    mst．StartVex=0；
    mst．StopVex=i+1；
    mst．weight=pGraph一>arcs；
    }
    for(i=0 ; i<  (1)；i++)(／*共n一1条边*／
    minWeight=(float)MAX；
    min=i；
    ／*从所有边(vx，vy)中选出最短的边*／
    for(j=i；jn一1；j++)(
    if(mst[j]．weight    minWeight=  (2)；
    min=j；
    }
    }
    ／*mst[min]是最短的边(vx，vy)，将mst[min]加入最小生成树*／
    edge：mst[min]；
    mst[min]=mst；
    mst=edge；
    vx= (3);／*VX为刚加入最小生成树的顶点下标*／
    ／*调整mst[i+1]到mst[n一1]*／
    for(j=i+1；jn一1;J++){
    vy=mst[j]．StopVex；
    if(4){／*计算(vx，vy)对应的边在压缩矩阵中的下标*／
    k=pGraph一>n*vy—vy*(vy+1)／2+VX—vy一1；
    )e1Se{
    k=pGraph一>n*vx—vx*(VX+1)／2+vy—vx一1；
    }
    weight=  (5)；
    if(weight    mst[J]．weight=weight；
    mst[j]．StartVex=VX；
    }
    }
    }
选项
答案(1)pGraph一>11—1 (2)mst[j]．weight (3)rest[i]．StopVex (4)vyarcs[k]
解析 由注释“n一1条边”可得，  (1)处应为pGraph一>n—1。空(2)有关程序段是选出权值最小的边，minWeight表示的是最小权值，因此空(2)应填mst[j]．weight。 “vx为刚加入最小生成树的顶点下标”，因此空(3)应填mst．StopVex。邻接矩阵是压缩存储的，只存储上三角阵，因此下标需要进行转换。比较if及else块，可发现两算式区别在于vx、vy互换，由邻接矩阵的对称性可得空(4)处应填vyarcs[k]。
转载请注明原文地址:https://kaotiyun.com/show/VaDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)