首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
阅读下列函数说明和C代码,将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
admin
2010-12-17
37
问题
阅读下列函数说明和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;
}
}
}
}
(5)
选项
答案
pGraph->arcs[k]
解析
由注释“n-1条边”可得,(1)处应为pGraph->n-1。
空(2)有关程序段是选出权值最小的边,minWeight表示的是最小权值,因此空(2)应填mst[j].weight。
“vx为刚加入最小生成树的顶点下标”,因此空(3)应填mst
.StopVex。
邻接矩阵是压缩存储的,只存储上三角阵,因此下标需要进行转换。比较if及else块,可发现两算式区别在于vx、vy互换,由邻接矩阵的对称性可得空(4)处应填vy<vx。
空(5)相关程序段是进行调整,应填pGraph->arcs[k]。
转载请注明原文地址:https://kaotiyun.com/show/8vDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
(42)不是文档测试包括的内容。
在结构化分析方法中,用于行为建模的模型是①,其要素包括②。②处应填入?
按照开发阶段划分,软件测试可以分为______。①单元测试②集成测试③系统测试④确认测试⑤用户测试⑥验收测试⑦第三方测试
采用IE浏览器访问清华大学校园网主页时,正确的地址格式为______。
若一个单处理器的计算机系统中同时存在3个并发进程,则同一时刻允许占用处理器的进程数________________。
虚拟存储体系由___________两级存储器构成。
软件开发中经常利用配置库实现变更控制,主要是控制软件配置项的状态变化,不受配置管理控制的是()。
假设系统采用PV操作实现进程同步与互斥。若n个进程共享两台打印机,那么信号量S的取值范围为()。
当一个双处理器的计算机系统中同时存在3个并发进程时,同一时刻允许占用处理器的进程数______。
随机试题
Oneoftheworld’soldestandmostfamousstatuesmaynot【C1】______muchlongerunlessstepsare【C2】______tosaveit.Thehugef
与肺相合的是
建设用地原则上须依法申请使用国有土地,但有下列哪些情形需要使用土地的,经依法批准可以使用农民集体所有的土地?()
我国商业银行很少直接面临()。
性格是先天形成的,没有好坏之分。
从情绪活动发生的强弱程度和持续时间来看,情绪分为()。
两个月前,王阿姨带5岁的小孙子在小区里散步时,正赶上周阿姨出来遛狗。周阿姨家的小狗活泼好动,趁周阿姨不留神挣脱了绳子,向王阿姨的小孙子扑了过去。小孩子受到惊吓,重重地跌在地上,吓得哇哇大哭。这一来,脾气火暴的王阿姨不愿意了,抱起小孙子就和周阿姨理论,要求对
[*]
HowtoSpeakGoodEnglishManylearnershavedifficultyincommunicatingduetothelackofconfidenceandrightmethods.T
—Idon’tliketocomplain,butIboughtthiscameralastweekandit’sstoppedworking.—Hum—yes,it’sfaulty.Doyouhaveyou
最新回复
(
0
)