首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
admin
2010-12-17
66
问题
阅读下列函数说明和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;
}
}
}
}
(3)
选项
答案
mst[i].StopVex
解析
转载请注明原文地址:https://kaotiyun.com/show/fvDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
某企业职工关系EMP(E_no,E_name,DEPT,E_addr,E_tel)中的属性分别表示职工号、姓名、部门、地址和电话;经费关系FUNDS(E_no,E_limit,E_used)中的属性分别表示职工号、总经费金额和已花费金额。若要查询部门为“开
高度为n的完全二叉树最少的结点数为______。
有两个N*N的矩阵A和B,想要在微机(PC机)上按矩阵乘法基本算法编程实现计算A*B。假设N较大,本机内存也足够大,可以存下A、B和结果矩阵。那么,为了加快计算速度,A和B在内存中的存储方式应选择______。
函数main()、f()的定义如下所示。调用函数f()时,第一个参数采用传值(callbyvalue)方式,第二个参数采用传引用(callbyreference)方式,main()执行后输出的值为______。
某软件公司项目组的程序员在程序编写完成后均按公司规定撰写文档,并上交公司存档。此情形下,该软件文档著作权应由______享有。
某系统中有一个中央数据存储,模块A负责接收新来的数据并修改中央数据存储中的数据,模块B负责访问中央数据存储中的数据,则这两个模块之间的耦合类型为________________。若将这两个模块及中央数据合并成一个模块,则该模块的内聚类型为_________
设数组a[1..10,1..8]中的元素按行存放,每个元素占用4个存储单元,已知第一个数组元素a[1,1]的地址为1004,那么a[5,6]的地址为________________。
某计算机系统采用页式存储管理方案,假设其地址长度为32位,其中页号占20位,页内地址占12位。系统中页面总数与页面大小分别为________________。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
随机试题
患者,女性,24岁。因肠梗阻入院。BP90/60mmHg,血钠124mmol/L,血钾3.2mmol/L,CO2CP13.5mmolfL,尿25ml/h,尿比重1.020。首先应采取的治疗是
关于聚众斗殴罪下列哪些说法是正确的?
关于建筑业企业资质证书使用与延续的说法,正确的是()。
可以采用胸外心脏按压来抢救电击伤、窒息和溺水的人。()
下列活动属于人所独具的意识活动的是:
两个不透明的布袋A和B里面各放着6个球,其中,布袋A中的球有3个标为数字1,2个标为数字2,1个标为数字3;而布袋B中的球分别标为1、2、3、4、5、6。若某人分别从布袋A和B里取一个球,这两个球的数字之和不大于3的概率是多少?
甘蔗:红糖
在指令中,操作数地址在某寄存器中的寻址方式称为__________寻址。
ThismonthSingaporepassedabillthatwouldgivelegalteethtothemoralobligationtosupportone’sparents.Calledthemain
ThetwomostcelebratingholidaysintheNorthandSouthAmerica,AustraliaandEurope,andinmostofChristianworldareChris
最新回复
(
0
)