首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和c代码,将应填入(n)处的字句写在对应栏内。 【说明】 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题。程
阅读下列函数说明和c代码,将应填入(n)处的字句写在对应栏内。 【说明】 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题。程
admin
2009-02-15
19
问题
阅读下列函数说明和c代码,将应填入(n)处的字句写在对应栏内。
【说明】
所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。
应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值),按长度大小对各边进行排序后,按贪婪准则从排序后的各边中选择边组成回路的边,贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下:
#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[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 1[M]);/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M], int m, int b);
/*调整表排序表,b表示是否可调,即是否有边长度相同的边存在*/
void travling(tpd pd[M], int n, float dist, t1 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].p1=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
.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]) (2) !isCircuit(r,i,j) (3) selected(r,i,j) (4) h==n-1 (5) exchange(dr,m,b)
解析
本题主要是函数调用的问题。
空(1)是计算各边的长度,根据函数的声明及说明,应填distance(pd
,pd[j])。
由注释可见空(2)是判断边(i,j)加入r后是否形成回路,若形成了回路,不加入。由语句“dist+=dr[k].x;”可知此处是将边加入,故此处应该是不形成回路条件。参照isCircuit函数声明及说明可知,若形成回路返回0,故空(2)填“!isCircuit(r,i,j)”。
空(3)是将边(i,j)加入到r中,参照selected函数声明及说明,可得空(3)填selected(r, i,j)。
由注释可见空(4)是最后一条边条件,变量h表示的是“选入端点关系表中的边数”,而 n各节点回路应该包含n条边,这点也可从后面h==n输出解看出,故空(4)填h==n-1。
空(5)是进行调整,调用exchange函数,正确调用形式为exchange(dr,m,b)。
转载请注明原文地址:https://kaotiyun.com/show/puDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在数据库系统中,数据的()是指保护数据库,以防止不合法的使用所造成的数据泄漏、更改或破坏。
甲公司接受乙公司委托开发了一项应用软件,双方没有订立任何书面合同。在此情形下,()享有该软件的著作权。
如下图所示,从输出的信息中可以确定的信息是___________。
针对以下C语言程序段,假设sta[10]=-1,对于x的取值,需要______个测试用例能够满足分支覆盖的要求。intMathMine(intx){intm=0;inti;for(i=x-1;i<=x+1;
在程序执行过程中,Cache与主存的地址映像由()。
编写汇编语言程序时,下列寄存器中程序员可访问的是______。A.程序计数器(PC)B.指令寄存器(IR)C.存储器数据寄存器(MDR)D.存储器地址寄存器(MAR)
在面向对象系统中,对象的属性是()。
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数已经排好序,将第i个整数依次和第i-1,i-2,…个整数进行比较,找到应该插入的位置。现采用插入排序算法对6个整数{5,2,4,6,1,3}进行从小到大排序,则需要进行(31)
定义某一密码Password::=[APPLICATION27]OCTETSTRING,使用隐含标签,其第一字节BER编码为(35)。
随机试题
男,30岁,建筑工人,从高处坠下,腰痛。血压85/50mmHg,脉细速,神志淡漠,面色苍白,HR110次/分,全腹压痛、轻度肌紧张、反跳痛,肠鸣音减弱,移动性浊音(+)。应立即施行
硝酸甘油、维拉帕米、川芎嗪、普萘洛尔治疗心绞痛的共同作用机制是
既能用于支气管哮喘,又能用于心源性哮喘的药物是()
如果纳米新型材料公司与商某委托开发完成了发明创造,则在双方没有约定的情况下申请专利的权利应属于()。如果商某要转让对材料M的专利申请权,则()。
排水管渠系统中,雨水口按进水箅在街道上的设置位置可分为()。
现值指数法与净现值法相比较,其优点是()。
下列关于见面礼节说法正确的是()。
国际货币基金组织(IMF)在()年把人民币纳入特别提款权(SDR)。
民国时期出版的著名大型工具书包括()等。
设,而n≥2为正整数,则An-2An-1=_________.
最新回复
(
0
)