首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
43
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
模块A的功能为:从数据库中读出产品信息,修改后存回数据库,然后将修改记录写到维护文件中。该模块内聚类型为(38)内聚。以下关于该类内聚的叙述中,正确的是(39)。(39)
页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4K,地址变换过程如下图所示,图中逻辑地址用十进制表示。图中有效地址经过变换后,十进制物理地址a应为(18)。
以下关于不同类型的软件测试的叙述,正确的是______。A.单元测试不是模块测试B.多个模块不能平行地独立进行测试,应该顺序执行C.系统测试是检验程序单元或部件之间的接口关系D.确认测试是通过检验和/或核查所提供的客观证据,证实软件是否满足特定预期
以下属于测试停止依据的是______。①测试用例全部执行结束②测试覆盖率达到要求③测试超出了预定时间④查出了预定数目的故障⑤执行了预定的测试方案⑥测试时间不足
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则完成该项目的最少时间为_____________(34)天。活动BD最多可以晚开始______________(35)天而不会影响整个项目的进度。(35)
某企业的生产流水线上有2名工人P1和P2,1名检验员P3。P1将初步加工的半成品放入半成品箱B1;P2从半成品箱B1取出继续加工,加工好的产品放入成品箱B2;P3从成品箱B2取出产品检验。假设B1可存放n件半成品,B2可存放m件产品,并设置6个信号量S1、
以下关于数据流图的叙述中,不正确的是()。
面向对象分析需要找出软件需求中客观存在的所有实体对象(概念),然后归纳、抽象出实体类。(26)是寻找实体对象的有效方法之一。
系统交付后,修改原来打印时总是遗漏最后一行记录的问题,该行为属于______维护。
MVC模式(模型.视图一控制器)是软件工程中的一种软件架构模式,把软件系统分为模型、视图和控制器三个部分。________________不属于MVC模式的优点。
随机试题
简述使用画图程序制作一幅图画的完整过程。
A.儿童接种卡介苗B.指导孕妇服用叶酸C.对传染病患者进行隔离D.宫颈癌的筛查E.糖尿病患者的自我管理属于第三极预防措施的是
甲诉乙民间借贷纠纷,二审法院终审判决乙返还甲借款本金、利息共计50万元。判决生效后,乙拒不履行义务,甲向一审法院申请强制执行。由于乙在银行的存款余额不足,执行人员对乙占有的一辆奥迪汽车采取了执行措施。在拍卖该汽车之前,公民丙向人民法院提出;该汽车的所有人是
拟建某工业项目,建设期2年,生产期10年,基础数据如下:1.第一年、第二年固定资产投资分别为2100万元、1200万元。2.第三年、第四年流动资金注入分别为550万元、350万元。3.预计正常生产年份的年销售收入为3500万元,经营
在项目组织的形式中,如果每个成员都接受项目经理和职能部门的双重领导,这种组织形式称为( )。
提前还款是指借款人具有一定偿还能力时,主动向贷款银行提出部分或全部提前偿还贷款的行为。()
某建设单位建设一热电厂,该单位委托甲工程监理公司对工程进行监理,委托乙施工单位作为项目的施工总承包单位,并决定向美国丙重型设备制造商订购发电设备。甲监理公司的总监理工程师在主持编制监理规划时,安排了一位专业监理工程师负责风险分析和相应监理规划内容
在真实财富概念基础上,建设社会将会是充满挑战的:它需要勇气、正义和智慧这样的高尚品德,也需要我们之间、后代之间、长辈之间、邻里之间以及政治家之间的严肃对话来决定何种前进道路能实现我们的福祉。对人类来说,重新界定金钱的性质,纠正金钱对我们生活的奴役,重塑金钱
如何减缓组织变革的阻力?
我同《刑法》对醉酒的人犯罪承担刑事责任的规定是()。
最新回复
(
0
)