首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
admin
2013-01-05
57
问题
阅读下列函数说明和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);
}
(4)
选项
答案
h==n-1
解析
由注释可见空(4)是最后一条边条件,变量h表示的是“选入端点关系表中的边数”,而n个节点回路应该包含n条边,这点也可从后面h==n输出解看出,故空(4)填h==n-1。
转载请注明原文地址:https://kaotiyun.com/show/rYDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
目前比较热门的软件开发工具,如VB、PB、Delphi等都是可视化的。这些工具是一种(24)程序语言。
在引入自动化测试工具以前,手工测试遇到的问题包括()。①工作量和时间耗费过于庞大②衡量软件测试工作进展困难③长时间运行的可靠性测试问题④对并发用户进行模拟的问题⑤确定系统的性能瓶颈问题⑥软件测试过程的管
在输入输出控制方法中,采用______可以使得设备与主存间的数据块传送无需CPU干预。A.程序控制输入输出B.中断C.DMAD.总线控制
黑盒测试法是根据产品的______来设计测试用例的。A.功能B.输入数据C.应用范围D.内部逻辑
结构化分析(StructuredAnalysis,SA)是面向数据流的需求分析方法,______不属于SA工具。A.分层的数据流图B.数据词典C.问题分析图D.描述加工逻辑的结构化语言、判定表或判定树
表示“以字符a开头且仅由字符a、b构成的所有字符串”的正规式为______。
在网络应用测试中,网络延迟是一个重要指标。以下关于网络延迟的理解,正确的是(64)
随机试题
简述领导者树立人本观念的基本要求。
牙隐裂患牙不适用的治疗方法是()
某一通风排气系统在t=20℃、p=1atm①下运行,排出空气中NO2浓度为1000mg/m3,把该浓度用比摩尔分数表示应为()。A.4.87×10-1B.9.74×10-1C.9.74×10-3D.4.87×10-4
甲在乙处加工门窗两套,在取回门窗时因钱不够,未能付清加工费,乙只允许甲取走其中一套,另外一套等甲的钱交清之后再取。甲无奈,只得取走其中一套,则乙对另一套门窗的占有属于()。
域名WWW.xau.edu.cn卢一级域名是()。
甲公司于2011年111月收到法院通知,被告知乙公司状告甲公司侵犯专利权,要求甲公司赔偿100万元。甲公司经过反复测试认为其核心技术是委托丙公司研究开发的,丙公司应承担连带责任对甲公司进行赔偿。甲公司在年末编制会计报表时,根据法律诉讼的进展情况以及专业人士
标准参照评价是指评价时以学生所在团体的平均成绩为参照标准,根据其在团体中的相对位置(或名次)来报告评价结果。()
忆刘半农君这是小峰出给我的一个题目。这题目并不出得过分。半农去世,我是应该哀悼的,因为他也是我的老朋友。但是,这是十来年前的话了,现在呢,可难说得很。我已经忘记了怎么和他初次会面,以及他怎么来到了北京。他到北京,恐怕是在《新青
BSP的数据类按信息生命周期分成存档、事务、计划、统计四类,下面属于计划类数据的是
UnitedNationsDayThe24thofOctoberiscelebratedasUnitedNationsDay./Itisadaythatbelongstoeveryone,/andi
最新回复
(
0
)