首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
admin
2013-01-05
82
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
已知关系模式:图书(图书编号,图书类型,图书名称,作者,出版社,出版日期,ISBN),图书编号唯一识别一本图书。建立“计算机”类图书的视图Compute-BOOK,并要求进行修改、插入操作时保证该视图只有计算机类的图书。CREATE(1)
通用的风险分析表应包括()。(54)①风险问题②发生的呵能性③影响的严重性④风险预测值⑤风险优先级
关系数据库是表的集合。对视图进行查询,本质上就是查询从_______中获得的数据。
数据库是按照一定的数据模型组织、存储和应用的______的集合。
若系统中有4个互斥资源R,当系统中有2个进程竞争R,且每个进程都需要i个R(i≤3)时,该系统可能会发生死锁的最小i值是________。
某计算机系统页面大小为4K,进程P的页面变换表如下表所示。若P中某数据的逻辑地址为十六进制2C18H,则该地址的页号和页内地址分别为2和C18H;经过地址变换后,其物理地址应为十六进制______。
在由L2TP构建的VPN中,主要由①和②两种类型的服务器构成。1.将图5-1中①和②处空缺名称填写在答题纸的相应位置。2.简要说明两种服务器的主要作用。某路由器(在图5-1中没有标出)的部分配置信息如下所示,请解释其中标有下划线部分的含
阅读以下说明,回答问题1~4。[说明]FTTx+LAN是实现宽带接入的常用方法,基本结构如下图所示。
根据图3-1所给出的网络连接方式及相关的网络参数,区域(A)与区域(B)中计算机的网络参数配置(如图3-2所示)为:区域(A)计算机“IP地址”(范围):(1):区域(A)计算机“子网掩码”;(2);区域(A)计算机“默认网关”:(
根据图3-1所给出的网络连接方式及相关的网络参数,区域(A)与区域(B)中计算机的网络参数配置(如图3-2所示)为:区域(A)计算机“IP地址”(范围):(1):区域(A)计算机“子网掩码”;(2);区域(A)计算机“默认网关”:(
随机试题
以组成建筑结构的主要建筑材料来分,一般可将建筑结构分为()。
对于沉积岩相对地质年代的确定方法有下列()项。
平安工地建设考核评价中的安全生产条件核查包括()。
某棉纺企业为增值税一般纳税人,适用增值税税率为17%,2012年3月1日,“应付职工薪酬”科目贷方余额为516000元(全部为工资),该企业2012年3月份发生的有关职工薪酬业务如下:(1)1日,企业租人房屋4套供管理人员免费使用,月租金共计1200
根据下列资料,回答下列问题。金融:2010年年末北京市金融机构(含外资)本外币存款余额37700.3亿元,比年初增加3893.6亿元,增加额比上年减少911亿元,贷款余额19861.5亿元,比年初增加2408.1亿元,按可比口径计算,增加额比
下列关于当代中国价值观念说法错误的是()。
中国自古就有浓烈的宗法传统,_______宗族血亲之内的彼此关照,互相提携,并一致对外,上自帝王下至百姓,_______。填入划横线部分最恰当的一项是()。
[*]
Whatdoesthemanimply?
ToliveintheUnitedStatestodayistogainanappreciationforDahrendorf’sassertionthatsocialchangeexistseverywhere.T
最新回复
(
0
)