首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
admin
2010-12-17
47
问题
阅读下列函数说明和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;
}
}
}
}
(4)
选项
答案
vy<vx
解析
转载请注明原文地址:https://kaotiyun.com/show/yvDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在结构化分析方法中,用于行为建模的模型是①,其要素包括②。②处应填入?
某软件公司项目组的程序员在程序编写完成后均按公司规定撰写文档,并上交公司存档。此情形下,该软件文档著作权应由______享有。
假设系统有n(n≥6)个并发进程共享资源R,且资源R的可用数为3。若采用PV操作,则相应的信号量S的取值范围应为________________。
某软件公司在招聘软件评测师时,应聘者甲向公司做如下保证:①经过自己测试的软件今后不会再出现问题;②在工作中对所有程序员一视同仁,不会因为在某个程序员编写的程序中发现的问题多,就重点审查该程序,以免不利于团结;③承诺不需要其他人员,自己就可以独立进行测
程序运行过程中常使用参数在函数(过程)间传递信息,引用调用传递的是实参的()。
以下说法不正确的选项包括(48)。①软件测试不仅仅指测试的执行,还包括很多其他的活动②软件测试是一个独立的流程,贯穿产品整个生命周期,与其他流程并发地进行③应用H模型有利于资源调配,有助于跟踪测试投入的流向④H模型指
测试记录包括、(64)。①测试计划或包含测试用例的测试规格说明。②测试期间出现问题的评估与分析。③与测试用例相关的所有结果,包括在测试期间出现的所有失败。④测试中涉及的人员身份。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
随机试题
乙买甲一套房屋,已支付三分之一价款,双方约定余款待过户手续办理完毕后付清。后甲反悔,要求解除合同,乙不同意,起诉要求甲继续履行合同,转移房屋所有权。下列选项正确的是()
A.黄芩B.黄柏C.黄连D.龙胆E.苦参善清热燥湿,泻肝胆火的药物是()。
下列计算公式正确的有()。
下列关于安全许可证的管理的说法,错误的是()。
对于发达国家的国际大型商业银行,利用表外工具规避风险已成为其风险管理的重要组成部分,其利用()等衍生工具来对冲信用风险。
下列有关契税的表述中,正确的是()。
在各种利率并存条件下起决定作用的利率是()。
怎么才能让老板给自已加薪?职场上最纠结的事情莫过于此。可是偏偏就有人_______,幽默地给我们做出了榜样。漫画《老板,求加薪》中给我们列出了加三十六计,从借刀杀人到_______,书中的妙计连连,让人忍俊不禁。虽然都是_______的招式,但或许你的加薪
(Ⅰ)验证函数y(x)=(一∞<x<+∞)满足微分方程y"+y’+y=ex;(Ⅱ)求幂级数y(x)=的和函数。
假设表单上有一选项组:⊙男○女,如果选择第2个按钮“女”,则该选项组Value属性的值为
最新回复
(
0
)