首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
admin
2013-01-05
59
问题
阅读下列函数说明和C代码,
[说明]
所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。
应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(作为边的权值),按长度大小对各边进行排序后,按贪婪准则从排序后的各边中选择组成回路的边,贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下:
#define M 100
typedef struct{/*x为两端点p1、p2之间的距离,p1、p2所组成边的长度*/
float x;
int p1,p2;
}tdr;
typedef struct{/*p1、p2为和端点相联系的两个端点,n为端点的度*/
int n,p1,p2;
}tr;
typedef struct{/*给出两点坐标*/
float x,y;
}tpd;
typedef int tl[M];
int n=10;
[函数]
float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/
void sortArr(tdr a[M],int m);
/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表,m为边的条数*/
int isCircuit(tr r[M],int i,int j);
/*判断边(i,j)选入端点关系表r[M]后,是否形成回路,若形成回路返回0*/
void selected(tr r[M],int i,int j);/*边(i,j)选入端点关系表r*/
void course(tr r [M],tl l[M]);/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M],int m,int b);
/*调整表排序表,b表示是否可调,即是否有长度相同的边存在*/
void travling(tpd pd [M],int n,float dist,tl locus[M])
/*dist记录总路程*/
{
tdr dr[M];/*距离关系表*/
tr r[M];/*端点关系表*/
int i,j,k,h,m;/*h表示选入端点关系表中的边数*/
int b;/*标识是否有长度相等的边*/
k=0;
/*计算距离关系表中各边的长度*/
for(i=1;i<n; i++){
for(j=i+1;J<=n;j++){
k++;
dr[k].x=(1);
dr[k].pl=i;
dr[k].p2=j;
}
}
m=k;
sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/
do{
b=1;
dist=0;
k=h=0:
do{
k++;
i=dr[k].p1;
j=dr[k].p2;
if((r(i].n<=1)&&(r[j].n<=1)){/*度数不能大于2*/
if (2) {
/*若边(i,j)加入r后形成回路,则不能加入*/
(3);
h++;
dist+=dr[k].x;
}else if (4) {
/*最后一边选入r成回路,则该边必须加入且得到解*/
selected(r,i,j);
h++:
dist+=dr[k].x;
}
}
}while((k !=n) && (h !=n));
if(h==n){/*最后一边选入构成回路,完成输出结果*/
course(r,locus);
}else(/*找不到解,调整dr,交换表中边长相同的边在表中的顺序,并将b置0*/
(5);
}
}while(!b);
}
(2)
选项
答案
!isCircuit(r,i,j)
解析
由注释可见空(2)是判断边(i,j)加入r后是否形成回路,若形成了回路,不加入,由语句“dist+=dr[k].x;”可知此处是将边加入,故此处应该是不形成回路条件。参照isCircuit函数声明及说明可知,若形成回路返回0,故空(2)填!isCircuit(r,j)。
转载请注明原文地址:https://kaotiyun.com/show/MYDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
(63)不属于网站渗透测试的内容。
某银行系统要求报表功能容易扩展,以便在需要的时候可以处理新的文件格式,.则该需求是()的。
关于白盒测试的测试用例设计方法叙述,正确的是(55)。
软件可靠性管理把软件可靠性活动贯穿于软件开发的全过程,成为软件工程管理的一部分。确定软件的可靠性目标在()阶段。
以下不属于软件测试工具的是()。
以下关于建立良好的程序设计风格的叙述中,正确的是()。
给出关系R(A,B,C)和S(A,B,C),R和S的函数依赖集F={A→B,B→C}。若R和S进行自然连接运算,则结果集有3个属性。关系R和S________。
若系统中有4个互斥资源R,当系统中有2个进程竞争R,且每个进程都需要i个R(i≤3)时,该系统可能会发生死锁的最小i值是________。
目前,通过移动电话接人互联网采用的主要技术是什么?目前,国内采用的第三代移动通信技术标准有哪些?
SSL协议使用(1)密钥体制进行密钥协商。在IIS5.0中,Web服务器管理员必须首先安装Web站点数字证书,然后Web服务器才能支持SSL会话,数字证书的格式遵循ITU-T(2)标准。通常情况下,数字证书需要由(3)颁发。如果Web服务器管理员准备预
随机试题
简述群众路线原则要求各级领导者树立的基本观点。
中国与欧盟各成员国的贸易关系很不平衡,中欧贸易主要集中在()
A.紫雪丹B.至宝丹C.安宫牛黄丸D.行军散E.牛黄清心丸凉开方剂中长于芳香开窍,化浊辟秽者是
[背景资料]某平原区拦河闸工程,设计流量850m3/s,校核流量1020m3/s,闸室结构如图2F320080—2所示。本工程施工采用全段围堰法导流,上、下游围堰为均质土围堰,基坑采用轻型井点降水。闸室地基为含少量砾石的黏土,自然湿密度为1820~190
某房地产开发商招标修建写字楼工程(底层为商场),工程内容包括拆迁和修建,工期为18个月。合同规定,如果承包商不能在18个月内完成工程,应向业主支付误期损害赔偿费。开工后,业主未能在合同规定的时间内向承包商提供足够的施工场地。在开挖基槽时,发现地基土层中有淤
自2020年年初以来,A公司出现不能清偿到期债务,且资产不足清偿全部债务的情况。2020年12月17日,人民法院经审查裁定受理了A公司的破产申请,并指定了管理人。在该破产案件中,存在下述情况: (1)2019年10月8日,B公司向C银行借款1000万元,
教育法规体系分为纵向结构和横向结构。其中,教育法规体系的纵向结构是指由不同层级的教育法律文件组成的等级、效力有序的纵向体系。()
Whatdoesthespeakermainlydiscuss?
A、正确B、错误B词义理解题。根据原文Aleaderdoesnotnecessarilyoccupyaformalleadershipposition可知,领导未必占据正式的领导职位。由此可见,题干认为领导必须拥有领导职位与原文意思不
Ifyouweretobeginanewjobtomorrow,youwouldbringwithyousomebasicstrengthsandweaknesses.Successor【C1】______iny
最新回复
(
0
)