首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
34
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
下面的协议中属于应用层协议的是(26),该协议的报文封装在(27)中传送。(27)
软件测试的对象不包括________。
某高校人事管理系统中,规定讲师每课时的教学酬金不能超过100元,副教授每课时的教学酬金不能超过130元,教授每课时的教学酬金不能超过160元。这种情况下所设置的数据完整性约束条件称之为______。
页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4K,地址变换过程如下图所示,图中逻辑地址用十进制表示。图中有效地址经过变换后,十进制物理地址a应为(18)。
编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段,其中,(22)并不是每种编译器都必需的。
安全防护策略是软件系统对抗攻击的主要手段,安全防护策略不包括______。
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(25)
设有学生实体Students(学号,姓名,性别,年龄,家庭住址,家庭成员,关系,联系电话),其中“家庭住址”记录了邮编、省、市、街道信息;“家庭成员,关系,联系电话”分别记录了学生亲属的姓名、与学生的关系以及联系电话。学生实体Students中的“
在分层体系结构中,(41)实现与实体对象相关的业务逻辑。在基于Java,EE技术开发的软件系统中,常用(42)技术来实现该层。(42)
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
随机试题
二次能源不包括()
急性接触性唇炎
治疗热闭神昏,常与麝香配伍相须使用的药物是()
喷射混凝土回弹物不得重新用作喷射混凝土材料。()
某企业为提高产品附加值,拟建设一套深加工装置,项目计算期为6年,其中建设期为1年,运营期为5年。新建装置的固定资产费用为28000万元(含可抵扣增值税进项税额3000万元),无形资产费用为4000万元,其他资产费用为1000万元,基本预备费为20
为提高工作效率,方便建设单位,规划设计条件在()环节提出为佳。
按照现行增值税制度规定,下列行为应“视同销售”征收增值税的有()。
设单链表的表头指针为h,链表中结点构造为(data,next),其中data域为字符型,链表长度为n。编写算法判断该链表的n个字符是否中心对称。(例如xyx,xyyx都是中心对称。)
对长度为n的线性表排序,存最坏情况下,比较次数不是n(n一1)/2的排序方法是
A、Itisamutuallybeneficialpractice.B、Itbecomesaninternationalbusiness.C、Itbecomesthebestwayofeducation.D、Itbec
最新回复
(
0
)