首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】用克鲁斯卡尔算法求解给定图的最小生成树。 #include <stdio. h> #include <stdlib. h> #define MAXN 30
阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】用克鲁斯卡尔算法求解给定图的最小生成树。 #include <stdio. h> #include <stdlib. h> #define MAXN 30
admin
2009-02-15
44
问题
阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】用克鲁斯卡尔算法求解给定图的最小生成树。
#include <stdio. h>
#include <stdlib. h>
#define MAXN 30
typedef struct
{ int v1,v2; /*一条边依附的两个顶点*/
int weight; /*边上的权值*/
}EDGE;
typedef struct
{ int Vnum; /*图中的顶点数目*/
EDGE e[MAXN*(MAXN-1)/2]; /*图中的边*/
}Graph;
typedef struct node{ /*用链表存储同一个连通分量的顶点*/
int v;
struct node *next;
}Alist;
void heapadjust(EDGE data[], int s, int m)
{ /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/
int j;
EDGE t;
t=data[s]; /*备份元素data[s], 为其找到适当位置后再插入*/
for(j=2*s+1; j<=m; j=j*2+1){/*沿值较小的子结点向下筛选*/
if(j<m &&(1)) ++j;
if(!(t. weight>data[j]. weight)) break;
data[s]=data[j];s=j; /*用s记录待插入元素的位置(下标)*/
}/*for*/
data[s]=t; /*将备份元素插入由s所指出的插入位置*/
}/*heapadjust*/
int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/
{ int k=0; /*记录图中边的数目*/
int n;
int v1,v2;
int w;
printf("vertex number of the graph:");
scanf("%d", &n); /*输入图中的顶点数目*/
if(n<1) return 0;
p->Vnum=n;
do{ printf("edge(vertex1,vertex2,weight):");
scanf("%d %d %d", &V1, &v2, &w);
if(v1>=0 && v1<n && v2>=0 && v2<n){
p->e[k]. v1=v1; p->e[k]. v2=v2; p->e[k]. weight=w;
k++;
}/*if*/
}while(!( (2) ));
return k; /*返回图中边的数目*/
}/*creat_graph*/
int kruskal(Graph G, int enumber, int tree[][3])
{ /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, */
/*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/
int i, k, m, c=0;
int v1, v2;
Alist *p, *q, *a[MAXN];
for(i=0; i<G.Vnum; ++i){ /*将每个连通分量中的顶点存放在一个单链表中*/
a
=(Alist*)malloc(sizeof(Alist));
if(!a
) {
printf("\n mernory allocation error!");
exit(0);
}/*if*/
a
->v=i; a
->next=NULL;
}/*for*/
for(i=enumber-1; i>=0; --i)/*按照边上的权值建立小顶堆*/
heapadjust( (3) );
k=G. Vnum; /*k用于计算图中的连通分量数目*/
m=enumber-1;
i=0;
do{
v1=G. e[0]. v1; v2=G. e[0]. v2;
p=a[v1];
while(p && p->v!=v2){ /*判断当前选择的边的顶点是否在一个连通分量中*/
q=p; p=p->next;
}
if(!p){ /*当前边的顶点不在一个连通分量中*/
p=q;
p->next=a[G. e[0]. v2];
p=a[G. e[0]. v1); /*加入边(v1,v2), 将两个连通分量合并为一个*/
while(p){a[p->v]=(4); p=p->next; }
k--; /*连通分量数目减少一个*/
tree
[0]=v1; /*记录加入最小生成树的边*/
tree
[1]=v2;
tree
[2]=G. e[0]. weight;
c+=G. e[0]. weight;
++i;
}/*if*/
G. e[0]=G. e[m];
m--;
heapadjust ((5));
} while(k>1); /*当所有顶点不在同一个连通时, 继续*/
return c; /*返回最小生成树的代价*/
} /*kruskal*/
void main(void)
{ int i, enumber;
int tree[MAXN][3];
int cost=0;
Graph G;
enumber=creat_graph(&G);
cost=-kruskal(G,enumber,tree);
printf("Minimum-Cost spanning tree(kruskal):\n");
printf("edge\t weight\t\n");
for(i=0; i<G. Vnum-1; ++i)
printf("v %d –v %d \t %d\n", tree
[0], tree
[1], tree
[2]);
printf("Cost:%d\n", cost);
}
选项
答案
(1) data[j].weight>data[j+1].weight (2) v1==-1 && v2==-1 (3) G.e,i,enumber-1 (4) a[G.e[0].v1] (5) G.e,0,m
解析
(1) data[j].weight>data[j+1].weight
沿值较小的子结点向下筛选,建堆,堆顶元素最小;
(2) v1==-1 && v2==-1
当v1!=-1||v2!=-1时,循环读入,直到v1==-1 && v2==-1为真。
(3) G.e,i,enumber-1
按照边上的权值建立小顶堆。
(4) a[G.e[0].v1]
加入边(v1,v2),将两个连通分量合并为一个。
(5) G.e,0,m
找出下一条权值最小的边。
转载请注明原文地址:https://kaotiyun.com/show/FgDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
两名以上的申请人分别就同样的发明创造申请专利时,专利权授权给(35)。
GB/T18905-2002《软件工程产品评价》中确定的通用评价过程包括四个方面,即:确立评价需求,规定评价,设计评价和执行评价,其中有关“规定评价”部分包含的内容有(52)。
在计算机系统中,系统的______可以用MTTF/(1+MTTF)来度量,其中MTTF为平均无故障时间。
设有关系模式R(A1,A2,A3,A4,A5,A6),其中:函数依赖集F={A1→A2,A1A3→A4,A5A6→A1,A2A5→A6,A3A5→A6),则___________(21)是关系模式R的一个主键,R规范化程度最高达到____________(
软件工程的基本目标是()。
以下关于数据流图的叙述中,不正确的是()。
计算机各功能部件之间的合作关系如下图所示。假设图中虚线表示控制流,实线表示数据流,那么a、b和c分别表示(5)。
阅读以下说明和交换机的配置信息,回答问题1至问题3,将解答填入答题纸的对应栏内。[说明]某公司设3个部门,为了便于管理,每个部门组成1个VLAN,公司网络结构如图9-4所示。[交换机Switch1的部分配置信息]Switch
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。【说明】一个印刷电路板的布线区域可分成n×m个方格,如图3-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
随机试题
超急期心肌梗死的心电图为()
胸部X线检查心电图心影呈梨形提示()
在事件风险量的区域图中,若某事件经过风险评估,处于风险区A,则应采取措施降低其概率,可使它移位至()。
某珠宝首饰生产企业(一般纳税人)2019年6月向消费者个人销售自产的钻石戒指取得含税收入0.6万元,销售金银镶嵌项链取得含税收入0.3万元;向某经营金银首饰的商业企业销售镀金镶嵌手镯取得不含税收入0.2万元;取得铂金项链修理、清洗收入780元;当月采取翻新
邹妍向银行贷款60万元,贷款利率为4%,期限20年,按月计息,按月还款,则下列说去正确的是()。(1)如果采用等额本息还款法,则邹妍每月需还款3636元。(2)如果采用等额本金还款法,则第5期还款中所还的利息额,会比采用等额本息还
证券公司为所承销的证券创造一个流动性较强的二级市场,并维持市场价格的稳定的职能被称为()。
根据民事诉讼法及相关规定,对哪些裁定可以提起上诉?
国外最早专门论述教育的著作是()。
请使用VC6或使用【答题】菜单打开考生文件夹proj3下的工程proj3,其中声明的DataList类,是一个用于表示数据表的类。DataList的重载运算符函数operator+,其功能是求当前数据表与另一个相同长度的数据表之和;即它返回一个数据表,其每
Haveyoueverthoughtaboutinventingsomething?Didyouworrythatyourideawastoostrangeorunrealistic?Well,maybeyoush
最新回复
(
0
)