02331数据结构
相似问题和答案
第1题：
连通图的各边权值均不相同，则该图的最小生成树是唯一的。()
第2题：
A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.n+2
第3题：
如下所示是一个带权连通无向图，其最小生成树各边权的总和为
A． 24
B．25
C．26
D．27
第4题：
如下所示是一个带权连通无向图，其最小生成树各边权的总和为
A．24
B．25
C．26
D．27
第5题：
若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有( )。棵树。
A．k
B．n
C．n-k
D．n+k
解析：假设有x棵树，任一棵树的结点数ni与边数ki都满足ni=ki+1，所以对x棵树有 n=k+x，则x=n-k。
第6题：
此题为判断题(对，错)。
第7题：
下列叙述中正确的是（ ）。A．连通分量是无向图中的极小连通子图 B．生成树是连通图的一个极大连通子图 C．若一个含有n个顶点的有向图是强连通图，则该图中至少有n条弧 D．若一个含有n个顶点的无向图是连通图，则该图中至少有n条边
有向图是一个二元组
第8题：
此题为判断题(对，错)。
第9题：
●试题四
阅读下列算法说明和算法，将应填入(n)的字句写在答题纸的对应栏内。
【说明】
下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。
图5算法流程图
【算法】
/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个"有序表"。以顺序表MSTree返回生成树上各条边。*/
typedef struct{
VertexType vex1；
VertexType vex2；
VRType weight；
}EdgeType；
typedef ElemType EdgeType；
typedef struct{//有向网的定义
VertexType vexs[MAX_VERTEX_NUM]；//顶点信息
EdgeType edge[MAX_EDGE_NUM]；//边的信息
int vexnum，arcnum；//图中顶点的数目和边的数目
}ELGraph；
void MiniSpanTree_Kruskal(ELGraph G，SqList& MSTree){
//G.edge 中依权值从小到大存放有向网中各边
//生成树的边存放在顺序表MSTree中
MFSetF；
InitSet(F，G.vexnum)；//将森林F初始化为n棵树的集合
InitList(MSTree，G.vexnum)；//初始化生成树为空树
i=0；k=1；
while(k< (1) ){
e=G.edge[i]；//取第i条权值最小的边
/*函数fix_mfset返回边的顶点所在树的树根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。*/
rl=fix_mfset(F，LocateVex(e.vex1))；
r2= (2) //返回两个顶点所在树的树根
if(r1 (3) r2){//选定生成树上第k条边
if(ListInsert(MSTree，k，e){ (4) ；//插入生成树
mix_mfset(E，rl，r2)；//将两棵树归并为一棵树
}
(5) ；//继续考察下一条权值最小边
}
DestroySet(F)；
}
●试题四【答案】(1)G.vexnum(2)fix_mfset(F，LocateVex(e.vex2))(3)!=(4)k++(5)i++【解析】本题考查的是克鲁斯卡尔(Kruskal)算法。理解该算法的关键在于：由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。例如，如图2所示的连通网G5，在依次选中了(e，f)，(b，c)，(e，d)和(f，g)的4条边之后，权值最小边为(g，d)，由于g和d已经连通，若加上(g，d)这条边将使生成树上产生回路，显然这条边不可取。同理，边(f，d)也不可取，之后则依次取(a，g)和(a，b)两条边加入到生成树。那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。
第10题：
任何一个带权的无向连通图的最小生成树( )
A．只有一棵
B．有一棵或多棵
C．一定有多棵
D．可能不存在