首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
admin
2013-01-05
29
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下关于系统测试的叙述,不正确的是()。
网络系统中,通常把()置于DMZ区。
序言性注释是指在每个程序或模块开头的一段说明,起辅助理解程序的作用,一般包括:程序的表示、名称和版本号;程序功能描述;接口与界面描述;输入输出数据说明:开发历史;与运行环境有关的信息等。下列叙述中不属于序言性注释的是(23)。
数据库测试的对象包括______。①数据库连接测试②数据库的安全测试③定义的存储过程和触发器的测试④数据库接口测试
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
由于操作系统升级而对软件进行修改的行为属于________维护。
在C程序中,设有“inta=3,b=2,c=1;”,则表达式a>b>c的值是_________。
在C程序中,________是合法的用户定义变量名。①123②form-7③short④form7
某个不确定有限自动机(s0为初态,s3为终态)如下图所示,_______是该自动机可识别的字符串(即从初态到终态的路径中,所有边上标记的字符构成的序列)。
阅读以下说明,回答问题1至问题5。[说明]某企业采用Windows2000操作系统部署企业虚拟专用网(VPN),将企业的两个异地网络通过公共Internet安全地互联起来。微软Windows2000操作系统当中对IPSec具备完善的支持,下图
随机试题
人工地增加细胞外液中Na+浓度时,单根神经纤维动作电位的幅度将
(2001年第85题)预防甲状腺肿的碘化食盐,常用剂量为每10~20kg食盐中均匀地加入碘化钾或碘化钠
患者,男性,36岁。油漆厂工人,近半年头晕、乏力,未重视,上周感冒后症状加重,伴发热,体温最高达39℃,急查血常规:血红蛋白75g/L,白细胞2.9×109/L,血小板50×109/L。查体肝、脾未触及。根据临床特点,最可能的诊断是
A.药典品种的通用名B.非药典品种的通用名C.曾用名D.药品的商标E.商品名采用《中国药品通用名称》所规定的名称是()。
质量计划应根据()来编制。
路由器作为网络互连设备,必须具备以下哪些特点()。
小王的表现一直十分优秀,年终考核是第一名,是优秀员工的最佳人选,但是局长觉得小王还太年轻,没有给小王评优秀。小王心里有情绪,消极怠工,并想要以工作压力大为由调岗。如果你是小王的朋友。你会怎么安慰他,请现场模拟。
《雪绒花》是哪部影片的插曲?()
设函数y=y(x)满足△y=△x+o(△x),且y(1)=1,则∫01y(x)dx=—一.
Internet网上一台主机的域名由几部分组成?
最新回复
(
0
)