首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和c代码,将应填入(n)处的字句写在对应栏内。 【说明】 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题。程
阅读下列函数说明和c代码,将应填入(n)处的字句写在对应栏内。 【说明】 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题。程
admin
2009-02-15
28
问题
阅读下列函数说明和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://jikaoti.com/ti/0wi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
使用质量是从用户的角度来看待的产品质量,其属性不包括()。
集成测试关注的问题不包括()。
某教学管理数据库中,学生、课程关系模式和主键分别为:S(学号,姓名,性别,家庭住址,电话),关系S的主键为学号;C(课程号,课程名,学分),关系C的主键为课程号。假设一个学生可以选择多门课程,一门课程可以由多个学生选择。一旦学生选择某门课程必定有该课程的成
若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是_______。
在软件工程中,不属于软件定义阶段的任务是______。A.制定验收测试计划B.制定集成测试计划C.需求分析D.制定软件项目计划
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
某企业的生产流水线上有2名工人P1和P2,1名检验员P3。P1将初步加工的半成品放入半成品箱B1;P2从半成品箱B1取出继续加工,加工好的产品放入成品箱B2;P3从成品箱B2取出产品检验。假设B1可存放n件半成品,B2可存放m件产品,并设置6个信号量S1、
Youaredevelopingaserver-sideenterpriseapplication.Itmustsupportavarietyofdifferentclientsincludingdesktopbrowse
Youaredevelopingaserver-sideenterpriseapplication.Itmustsupportavarietyofdifferentclientsincludingdesktopbrowse
随机试题
小李是某幼儿园小班的教师,刚工作不久就满怀热情地投入到教育实践中,、可令她苦恼的是,在组织班级活动时,她发现小朋友们很难集中注意力,教室里一有响动,他们就会分心。无论是听故事、画画还是看图书,小朋友们的注意力都只能集中几分钟,这样一来,小李老师事先设计好的
简析“问君能有几多愁?恰似一江春水向东流”能称为千古佳句的原因。
关于食管下段括约肌(LES)的结构与功能,下面哪些说法不恰当
冯女士,第一孕,妊娠40周,初产妇。临产6小时,宫口开大3cm;临产11小时,宫口开全,先露头,先露“0”,胎心正常。宫口开全已2小时,产妇仍在屏气用力,此时,产程属于
股静脉注射,下述哪项是错误的:
基坑(槽)回填土施工过程中,应查验()等项目。
以下关于文档的说法错误的一项是()。
商检机构依据《商检法》的有关规定,对非法定检验的进出口商品可以实施定期检验。( )
给定资料1.2009年,一群来自深圳的普通工人成为美国《时代》周刊的年度人物。周刊一出版,中国工人的灿烂笑容,瞬间给经济低迷的世界带来希望。他们坚毅的目光、质朴的外表、倔强的神态,真实地反映了中国工人的性格,这种性格,为“中国制造”贴上光亮的标签
【F1】OnemeaningoftheGreekword"dran"istoaccomplish,andinthismeaningliesafurtherkeytothestructureofdrama.Ap
最新回复
(
0
)