试举例说明，即便带权网络中不含权重相等的边，其最短路径树依然可能不唯一。

哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根结点也较远。( )

此题为判断题(对，错)。

________是指在带权图的源点出发，找出一条通往汇点的路径，其组成边的权值之和最小。

A 最短路径问题

B 关键路径问题

C 最小生成树问题

哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( )【北京邮电大学1999二、5(2分)】【中国海洋大学2005二、13(1分)2007二、8(1分)】

此题为判断题(对，错)。

下列关于广度优先算法的说法正确的是（ ）。I当各边的权值相等时，广度优先算法可以解决单源最短路径问题II当各边的权值不等时，广度优先算法可用来解决单源最短路径问题III广度优先遍历算法类似于树中的后序遍历算法Ⅳ实现图的广度优先算法时，使用的数据结构是队列

A．I、Ⅳ

B．II、III、Ⅳ

C．II、Ⅳ

D．I、III、Iv

阅读下列算法说明和算法，将应填入(n)的字句写在对应的栏内。

[说明]

下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1条互不构成回路的权值最小边为止。

[算法]

/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/

typedef struct{

VertexType vex1;

VertexType vex2;

VRType weight;

} EdgeType;

typedef ElemType EdgeType;

typedef struct { //有向网的定义

VertexType vexs [MAX_VERTEX_N U M ]; //顶点信息

EdgeType edge[ MAX_EDGE_NUM]; //边的信息

int vexnum, arcnum; //图中顶点的数目和边的数目

I 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返回边的顶点所在树的树的根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。 */

ri = fix_mfset(F, LocateVex(e. vex1) );

r2=(2); //返回两个顶点所在树的树根

if(r1 (3) r2) { //选定生成树上第k条边

if(Listlnsert(MSTree,k,e){(4); //插入生成树

mix_mfset( E, r1,r2); //将两棵树归并为一棵树

}

(5); //继续考察下一条权值最小边

}

DestroySet (F); }

}

A．错误

B．正确

下列关于哈夫曼树的叙述错误的是

A．一棵哈夫曼树是带权路径长度最短的二叉树

B．一棵哈夫曼树中叶节点的个数比非叶节点的个数大1

C．一棵哈夫曼树节点的度要么是0，要么是2

D．哈夫曼树的根节点的权值等于各个叶节点的权值之和

下列关于哈夫曼树的叙述错误的是

A．一棵哈夫曼树是带权路径长度最短的二叉树

B．一棵哈夫曼树中叶节点的个数比非叶节点的个数大1

C．一棵哈夫曼树节点的度要么是0，要么是2

D．哈夫曼树的根节点的权值等于各个叶节点的权值之和