首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
60
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
如下图所示,从输出的信息中可以确定的信息是___________。
在机器指令的地址字段中,直接指出操作数本身的寻址方式称为___________。
针对以下C语言程序段,假设sta[10]=-1,对于x的取值,需要______个测试用例能够满足分支覆盖的要求。intMathMine(intx){intm=0;inti;for(i=x-1;i<=x+1;
在软件工程中,不属于软件定义阶段的任务是______。A.制定验收测试计划B.制定集成测试计划C.需求分析D.制定软件项目计划
对象是面向对象系统的最基本的元素,一个运行期系统就是对象之间的协作。一个对象通过()改变另一个对象的状态。
在进行软件编码规范评测过程中需要围绕几个方面的内容展开,以下描述中不属于编码规范评测内容的有(37)。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则完成该项目的最少时间为_____________(34)天。活动BD最多可以晚开始______________(35)天而不会影响整个项目的进度。(35)
软件测试使用各种术语描述软件出现的问题,以下叙述正确的是______。A.软件错误(error)是指在软件生命周期内的不希望或不可接受的人为错误,其结果是导致软件故障的产生B.软件缺陷(defect)是存在于软件(文档、数据、程序)之中的那些不希望或不
阅读以下说明和交换机的配置信息,回答问题1至问题3,将解答填入答题纸的对应栏内。[说明]某公司设3个部门,为了便于管理,每个部门组成1个VLAN,公司网络结构如图9-4所示。[交换机Switch1的部分配置信息]Switch
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。1.将(1)处空缺设备的名称填写在答题纸的相应位置。2.(1)所在局域网内的PC机或笔记本的IP地址有
随机试题
在TCP/IP中,提供端到端数据传输的是_______。
下列哪些表现或指标有助于贫血严重程度的判断()。
A.5~15分钟B.1小时C.1~2小时D.6~8小时E.11~12小时初产妇第一产程约需
指出下面正确的
(2015年)案情:甲欲出卖自家的房屋,但其房屋现已出租给张某,租赁期还剩余1年。甲将此事告知张某,张某明确表示,以目前的房价自己无力购买。甲的同事乙听说后,提出购买。甲表示愿意但需再考虑细节。乙担心甲将房屋卖与他人,提出草签书面合同,
根据《环境影响评价技术导则一大气环境》,某项目大气污染源距离厂界最近距离为500m,采用估算模式计算各污染物的最大影响程度为20%,最远影响距离为800m,该项目大气环境评价应为()。
政策性金融债券的发行需经过下列哪个机构的批准()
某商品成本为200元,售价为292元,公司根据市场情况调整了销售方案,将售价调整为268元,预计日销量将上涨15%。现欲通过改进生产线降低成本,以保持降价前的单日利润,则单件产品的生产成本至少需要降低
设有关系模式R(职工号,职工姓名,项目号,项目名,工资)如果规定,每个职工可参加多个项目,各领一份工资;每个项目可又多名职工完成。关系模式R的主码是______。A)职工号B)项目号C)(职工号,项目号)D)(职工号,项目
下列关于磁道的说话中,正确的是
最新回复
(
0
)