首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
30
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在ISO/IEC软件质量模型中,功能性是与一组功能及其指定的性质的存在有关的一组属性,其子特性不包括__________。
两名以上的申请人分别就同样的发明创造申请专利时,专利权授权给(35)。
现要开发一个通过卫星通信连接计算机的新软件产品,假设之前没有开发卫星通信软件的经验,则最不适合采用______模型。
为保证测试活动的可控性,必须在软件测试过程中进行软件测试配置管理,一般来说,软件测试配置管理中最基本的活动包括(65)
安全防护策略是软件系统对抗攻击的主要手段,安全防护策略不包括______。
以下属于测试停止依据的是______。①测试用例全部执行结束②测试覆盖率达到要求③测试超出了预定时间④查出了预定数目的故障⑤执行了预定的测试方案⑥测试时间不足
下图所示的二叉树进行顺序存储(根结点编号为1,对于编号为i的结点,其左孩子结点为2i,右孩子结点为2i+1)并用一维数组BT来表示,已知结点X、E和D在数组BT中的下标为分别为1、2、3,可推出结点G、K和H在数组BT中的下标分别为____________
MVC模式(模型.视图一控制器)是软件工程中的一种软件架构模式,把软件系统分为模型、视图和控制器三个部分。________________不属于MVC模式的优点。
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。1.将(1)处空缺设备的名称填写在答题纸的相应位置。2.(1)所在局域网内的PC机或笔记本的IP地址有
网络开发设计的整个过程分为哪几个阶段?每个阶段各有什么任务?请用流程图的方式说明。
随机试题
行政合理性原则的内涵是()。
简述测验的编制和实施。
以下无上皮衬里的囊肿是
引起上消化道出血最常见的原因是()
为开拓市场需要,个人独资企业主曾水决定在某市设立一个分支机构,委托朋友霍火为分支机构负责人。关于霍火的权利和义务,下列哪一表述是正确的?
影响混凝土和易性的主要因素有()。
下列各项中,属于利润表提供的信息有()。
课外活动和课堂教学的共同之处在于它们都是在学校里进行的有目的、有组织、有计划的活动。()
Inasmuchasitispopular,organizedsportsactivitiesarediscouragedasindividualsmaylosefocusattheteambuildingaspe
A、Writetheirlabreport.B、FindoutProfessorSmith’sschedule.C、Interviewsomehighschoolstudents.D、Finishtheirchemistry
最新回复
(
0
)