首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
admin
2013-01-05
77
问题
阅读下列函数说明和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);
}
(1)
选项
答案
distance(pd[i],pd[j])
解析
是计算各边的长度,根据函数的声明及说明,可得应填distance(pd
,pd[j])。
转载请注明原文地址:https://kaotiyun.com/show/0YDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
由于不同加密机制的用途及强度不同,因此一个信息系统中加密机制使用是否合理,强度是否满足当前需要,需要通过测试来检验,通常()是测试的一个重要手段。
(63)不属于网站渗透测试的内容。
(35)测试用例设计方法既可以用于黑盒测试,也可以用于白盒测试。
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。①处应填入?
运行Web浏览器的计算机与网页所在的计算机要建立(66)连接,采用(67)协议传输网页文件。
防火墙对数据包进行过滤时,不能过滤的是(9)________________。
网络杀毒软件厂商已经开始使用数据库技术和LDAP技术进行策略日志存储和用户管理,这里LDAP指的是______。A.轻量目录访问协议B.本地目录访问协议C.轻量数据访问协议D.本地数据访问协议
用面向对象方法设计了一个父类File和两个子类DiskFile和TapeFile,这两个子类继承了其父类的open方法,并给出不同的实现。不同的子类执行open方法时,有不同的行为,这种机制称为_____。
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
阅读以下说明,回答问题1~7。[说明]下图是在网络中划分VLAN的连接示意图。VLAN可以不考虑用户的物理位置,而根据功能、应用等因素将用户从逻辑上划分为一个个功能相对独立的工作组,每个用户主机都连接在支持VLAN的交换机端口上,并属于某个VLA
随机试题
电子邮件作为一种互联网应用,需要有网络协议的支持,用到的网络协议有简单邮件传输协议(SMTP)、邮局协议(POP)及Internet消息访问协议(IMAP)。它们都隶属于————____________簇。
坠落伤损伤发生的部位的特点是常较广泛但
A、最小成本法B、成本-效用分析C、药物利用D、成本-效果分析E、成本-效益分析考察成本在单位时间和空间的社会效果及经济效果的方法为()。
血清壁细胞抗体阳性多见于
下列选项中,不属于各级政府行政机关对招标投标活动进行监督时所采用的监督方式的是()
关于土地登记程序的正确排序是()。
背景材料:某写字楼工程,建筑面积14352m2。箱型基础,现浇钢筋混凝土框架结构。目前进行内部装修阶段,在装修施工前,已对各部位装修材料的燃烧性能进行了技术交底工作。装修工程完工后,建设单位项目负责人组织施工单位项目负责人、监理工程师和设计单
下列费用中,应列入建筑安装工程措施费的有()。
以下项目中,属于科目汇总表账务处理程序缺点的是()。
团队旅游接待的成败关键在于()。
最新回复
(
0
)