首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
admin
2013-01-05
52
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
采用________________表示带符号数据时,算术运算过程中符号位与数值位采用同样的运算规则进行处理。
以下属于静态测试方法的是___________。
Win2003Server中启用配置SNMP服务时,必须以()身份登录才能完成SNMP服务的配置功能。
在性能测试中,关于数据准备,(65)描述是正确的。①识别数据状态验证测试案例。②初始数据提供了基线用来评估测试执行的结果。③业务数据提供负载压力背景。④脚本中参数数据真实模拟负载。
广义的软件测试由“确认”、“验证”、“测试”三个方面组成,其中“确认”是______。A.想证实在一个给定的外部环境中软件的逻辑正确性,检查软件在最终的运行环境上是否达到预期的目标B.检测软件开发的每个阶段、每个步骤的结果是否正确无误,是否与软件开发各
函数main()、f()的定义如下所示。调用函数f()时,第一个参数采用传值(callbyvalue)方式,第二个参数采用传引用(callbyreference)方式,main()执行后输出的值为_______。
_______是构成我国保护计算机软件著作权的两个基本法律文件。
以下关于CPU与I/O设备交换数据所用控制方式的叙述中,正确的是_______。
通常VLAN有静态和动态2种实现方式,这2种方式分别是如何实现的?各有什么特点?Switch1采用的是哪种实现方式?填充VLAN信息表如表9-3所示,将答案填写在答题纸相应位置。
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥以下关于摘要
随机试题
A.雷尼替丁B.奥美拉唑C.阿莫西林D.奥美拉唑、克拉霉素、甲硝唑三联E.多潘立酮28岁男性,上腹烧灼痛2年,为饥饿痛,有午夜痛。胃镜检查为十二指肠球部溃疡,快速尿素酶染色阳性。
具有泻下冷积,逐水退肿作用的药物是()具有泻下逐水,去积杀虫作用的药物是()
设f(x)=∑n=0∞anxn和g(x)=∑n=0∞bnxn,则f(x)g(x)的幂级数展开式中xn项的系数是:
按照《生产安全事故报告和调查处理条例》,发生事故后,事故发生单位必须以最快方式,将事故的简要情况向()报告。
某期权交易所2020年3月20日对ABC公司的期权报价如下:ABC公司是一家上市公司,最近刚发放上年现金股利每股2元,目前每股市价30元。证券分析师预测,甲公司未来股利增长率5%,等风险投资的必要报酬率10%,假设标的股票的到期日市价与
下列分布中,最适合描述光盘表面缺陷数的是()。
用大谱表记谱的乐器不包括()。
作诠释,是对事物或事理的某些性质和特点进行适当解说的一种说明方法,对说明的对象的解说往往侧重于事物某一方面的特征,或者解说它的构造、成因、功用等非本质的因素,说明的内容不能与被说明的对象变换位置。根据上述定义,下列选项中不属于作诠释的是()。
列宁说,意志如果是国家的,就应该表现为政权机关所制定的法律,否则“意志”这两个字只是毫无意义的空气振动而已。孟德斯鸠说:“当立法权和行政权集中在同一个人或同一个机关之手时,自由便不存在了。因为人们将要害怕这个国王或议会制定暴虐的法律,并暴虐地执行这些法律
Time______veryfastandanewyearwillbeginsoon.
最新回复
(
0
)