首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 若要在N个城市之间建立通信网络,只需要N—1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5—1所示,
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 若要在N个城市之间建立通信网络,只需要N—1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5—1所示,
admin
2014-10-11
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 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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在C程序中,对于如下的两个for语句,其运行后a和b的值分别为________。for(inta=0;a=0,a++);for(intb=0;b=0;++b);
_______是构成我国保护计算机软件著作权的两个基本法律文件。
目前,通过移动电话接人互联网采用的主要技术是什么?目前,国内采用的第三代移动通信技术标准有哪些?
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?IMail安装完成后,系统自动建立了一个名为root的用户,在默认情况下root用户是个失效的账号,如何设置使其生效?
将图2-1中(1)和(2)空缺名称填写在应的位置。在本质上,ADSL采用的什么多路复用方式?
阅读以下说明,回答问题1~7。[说明]下图是在网络中划分VLAN的连接示意图。VLAN可以不考虑用户的物理位置,而根据功能、应用等因素将用户从逻辑上划分为一个个功能相对独立的工作组,每个用户主机都连接在支持VLAN的交换机端口上,并属于某个VLA
SSL协议使用(1)密钥体制进行密钥协商。在IIS5.0中,Web服务器管理员必须首先安装Web站点数字证书,然后Web服务器才能支持SSL会话,数字证书的格式遵循ITU-T(2)标准。通常情况下,数字证书需要由(3)颁发。如果Web服务器管理员希望W
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
具有综合业务传输能力的HFC网络由视频前端(FE)、主数字终端(HDT)、光纤节点(FN)、网络接口单元(NIU)、综合业务单元(ISU)及传输线路等构成。根据HFC网接入Internet的典型配置,将图8-11所示的拓扑图中(1)~(5)空缺处名称填写
随机试题
具体行政行为认定事实不清的,证据不足的,行政复议机关可以调查补正后作出维持决定。()
房地产法律的调整对象中,()是指房地产行政主管部门依据法律规定对房地产市场实施管理、监督、检查时发生的法律关系。
过点(1,2,4)且与两平面x+2z+1=0,y一3z+3=0平行的直线方程为()。
海关在查验时认为必要,可以径行开验、复验或者提取货样,货物保管人员应当到场作为见证人。()
产业资本从不同的角度可以做出不同的划分,若将其分为货币资本、生产资本、商品资本,则这种划分的依据是资本各个部分()。
下列关于我国爱国统一战线的表述,不正确的是()(2013年一综一第18题)
执行者与用例之间的关系是()。
SSL主要用于WWW客户与服务器之间传送数据进行(1),它位于(2)层之上,发送方接收(3)的数据进行加密,然后将加密数据送往(4)。(5)是专为在因特网上进行安全信用卡交易的协议。
利用计算机进行指纹识别、图像和声音处理属于下列哪一种应用领域?()。
A、$800.B、$850.C、$1000.D、$1050.D
最新回复
(
0
)