首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 若要在N个城市之间建立通信网络,只需要N—1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5—1所示,
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 若要在N个城市之间建立通信网络,只需要N—1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5—1所示,
admin
2014-10-11
49
问题
阅读下列函数说明和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;i
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
n一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;j
n一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)vy
arcs[k]
解析
由注释“n一1条边”可得, (1)处应为pGraph一>n—1。空(2)有关程序段是选出权值最小的边,minWeight表示的是最小权值,因此空(2)应填mst[j].weight。 “vx为刚加入最小生成树的顶点下标”,因此空(3)应填mst
.StopVex。邻接矩阵是压缩存储的,只存储上三角阵,因此下标需要进行转换。比较if及else块,可发现两算式区别在于vx、vy互换,由邻接矩阵的对称性可得空(4)处应填vy
arcs[k]。
转载请注明原文地址:https://kaotiyun.com/show/VaDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
下图是责任链设计模式的类图,该设计模式的目的是________。该图中,Handler和Handler之间是关联关系,Handler和ConcreteHandler之间是继承关系。
某个不确定有限自动机(s0为初态,s3为终态)如下图所示,_______是该自动机可识别的字符串(即从初态到终态的路径中,所有边上标记的字符构成的序列)。
常用作网络边界防范的是________。
阅读以下说明,回答问题1至问题3,将解答填入答题纸对应的解答栏内。说明网络解决方案如图4-1所示。该网络原先使用的是国外品牌的交换机,随着网络规模的扩大,增添了部分国产品牌的交换机,交换机1至交换机5均是国产10M/100M自适应交换机,交换机6
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?如何暂时禁用某个用户账号?
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持root用户执行psaux|grepinit命令,得到init的PID是______。A.0
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。将答
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。为上
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
具有综合业务传输能力的HFC网络由视频前端(FE)、主数字终端(HDT)、光纤节点(FN)、网络接口单元(NIU)、综合业务单元(ISU)及传输线路等构成。根据HFC网接入Internet的典型配置,将图8-11所示的拓扑图中(1)~(5)空缺处名称填写
随机试题
培训
Doyoufinditverydifficultandpainfultogetupinthemorning?Thismightbecalledlaziness,butDr.Kleitmanhasanewex
下列不是防治人感染高致病性禽流感关键要做到“四早”的是()
安史之乱
A、 B、 C、 D、 D本题属于两组同规律类图形推理。观察图形可知,第一组图形三个图形均位于两道平行线之间,且有相连的两块黑色图形。同样,第二组图形均位于封闭图形内部且有相连的两块黑色图形,故选D。
某商场开业酬宾,公布了打折信息:开业期间,①如果购物不超过300元,则没有优惠;②如果超过300元但不超过800元,按标价给予8折优惠;③如果超过800元,其中800元按8折优惠,超过800部分给予7折优惠。小王在开业期间两次购物,分别付款190
【B1】【B6】
资本主义积累过程往往伴随着资本有机构成的提高,资本有机构成是指______。
WhatkindofoverviewdoesthebookintendtogiveaboutAmericansociety?
Itoccurredtome______ifIhadcontinuedtomaintaineyecontact,Iwouldhavebeenrudeandaggressive.
最新回复
(
0
)