2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 所谓货郎担问题，是指给定一个无向图，并己知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题，程序先计算由各点构

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 所谓货郎担问题，是指给定一个无向图，并己知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题，程序先计算由各点构

admin2014-10-11  15
问题 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。
【说明】
所谓货郎担问题，是指给定一个无向图，并己知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下：
#defineM100
typedefstruct{／*x为两端点p1、p2之问的距离，p1、p2所组成边的长度*／
floatX；
intp1，p2；
}tdr；
typedefstruct(／*pl、p2为和端点相联系的两个端点，n为端点的度*／
intn，p1，p2；
}tr；
typedefstruct{／*给出两点坐标*／
floatX，Y；
}tpd;
typedefintt1[M]；
intn=10；
【函数】
floatdistance(tpda，tpdb)；／*计算端点a、b之间的距离*／
voidsortArr(tdra[M]，intm)；
／*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*／
intisCircuit(trr[M]，inti，intj)；
／*判断边(i，j)选入端点关系表r[M]后，是否形成回路，若形成同路返回0*／
voidselected(trr[M]，inti，intJ)；／*边(i，j)选入端点关系表r*／
voidc。urse(trr[M]，t1l[M])；／*从端点关系表r中得出回路轨迹表*／
voidexchange(tdra[M]，intm，intb)；
／*调整表排序表，b表示是否可调，即是否有长度相同的边存在*／
voidtravling(tpdpd[M]，intII，floatdist，t1locus[M])
／*dist％ff录总路程*／
{
tdrdr[M]；／*距离关系表*／
trr[M]；／*端点关系表*／
inti，j，k，h，m；／*h表示选入端点关系表中的边数*／
intb；／*标识足否有长度相等的边*／
k=0；
／*计算距离关系表中各边的长度*／
for(i=1；ifor(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；
}elseif((4)){
／*最后一边选入r成回路，则该边必须加入且得到解*／
selected(r，i，j)；
h++：
dist+=dr[k]．x；
}
}
)while((k!=n)＆＆(h!=n));
if(h==n)(／*最后一边选入构成回路，完成输出结果*／
course(r，locus)；
}else(／t找不到解，调整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)填selectde(r,i,j)。由注释可见空(4)是最后一条边条件，变量h表示的是“选入端点关系表中的边数”，而n个节点回路
应该包含n条边，这点也可从后面h==n输出解看出，故空(4)填h==n-1。空(5)是进行调整，调mexchangeiN数，正确调用形式为exchange(dr,m,b)。
转载请注明原文地址:https://kaotiyun.com/show/9aDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)