首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
admin
2010-12-17
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 30 /*图中顶点数目的最大值*/
typedef struct{
int startVex,stopVex; /*边的起点和终点*/
float weight; /*边的权*/
}Edge;
typedef struct{
char vexs[MAXVEX]; /*顶点信息*/
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; i<pGraph->n-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; j<pGraph->n-1; j++){
if(mst[j].weight<minWeight){
minWeight=(2);
min=j;
}
}
/*mst[minl是最短的边(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;j<pGraph->n-1;j++){
vy=mst[j].StopVex;
if( (4) ){/*计算(vx,vy)对应的边在压缩矩阵中的下标*/
k=pGraph->n*vy-vy*(vy+1)/2+vx-vy-1;
}else{
k=pGraph->n*vx-vx*(vx+1)/2+vy-vx-1;
}
weight(5);
if(weight<mst[j].weight){
mst[j].weight=weight;
mst[j].StartVex=vx;
}
}
}
}
(2)
选项
答案
mst[j].weight
解析
转载请注明原文地址:https://kaotiyun.com/show/5vDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在结构化分析方法中,用于行为建模的模型是①,其要素包括②。②处应填入?
对于下面的有向图,其邻接矩阵是一个①的矩阵。采用邻接链表存储时,顶点0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为②个。①处应填入?
高度为n的完全二叉树最少的结点数为______。
假设系统有n(n≥5)个并发进程共享资源R,且资源R的可用数为2。若采用PV操作,则相应的信号量S的取值范围应为______。
某算术表达式用二叉树表示如下,该算术表达式的中缀式为________________,其后缀式为________________。
设数组a[1..10,1..8]中的元素按行存放,每个元素占用4个存储单元,已知第一个数组元素a[1,1]的地址为1004,那么a[5,6]的地址为________________。
导致软件缺陷的原因有很多,①~④是可能的原因,其中最主要的原因包括(55)。①软件需求说明书编写的不全面,不完整,不准确,而且经常更改。②软件设计说明书。③软件操作人员的水平。④开发人员不能很好的理解需求说明书和沟通不足。
计算机采用分级存储体系的主要目的是为了解决()的问题。
随机试题
甲地发生旱灾,从外地运到一批救灾物资,该地乙乡政府委托各村发放救灾物资,丙村在发放救灾物资时把张某遗漏,张某不服想提起行政诉讼。 请问:张某应以谁为被告?为什么?
金樱子的主治病证是()
用标准预算审查法审查施工图预算,其特点之一是()。
炮孔孔深超过()m时,禁止用火花起爆.
()是接受受托机构委托,负责保管信托财产账户资金的机构。
下列选项中,属于金融期货主要交易制度的有()。Ⅰ.限仓制度Ⅱ.逐日盯市制度Ⅲ.集中交易制度Ⅳ.有负债的结算制度
2015年1月15日,甲出资5万元设立A个人独资企业(下称“A企业”),主要从事铁皮的加工。甲聘请乙管理企业事务,同时规定,凡乙对外签订标的超过1万元的合同,须经甲同意。2月10日,乙未经甲同意,以A企业名义向善意第三人丙购入价值2万元的货物。3月15日,
材料:语文课上,吴老师正和同学们尽情地“畅游”在《颐和园》这幅清新、美丽的“画卷”中。突然,一只小手高高举起:“老师,课文第四自然段‘游船、画舫在湖面慢慢地滑过,几乎不留一点儿痕迹’中的‘滑’字,应该改成‘划船’的‘划’。”这位同学突然的提问似乎
在下列()市场中,组合管理者会选择消极保守型的态度,只求获得市场平均的收益率水平?
我国1993年《公司法》第5条关于“公司以其全部法人财产,依法自主经营,自负盈亏”的规定,是属于()。
最新回复
(
0
)