单选题用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从（）组中选取。A {（1，4），（3，4），（3，5），（2，5）}B {（5，4），（5，3），（5，6）}C {（1，2），（2，3），（3，5）}D {（3，4），（3，5），（4，5），（1，4）}

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

下面哪些使用的不是贪心算法()

A.单源最短路径中的Dijkstra算法

B.最小生成树的Prim算法

C.最小生成树的Kruskal算法

D.计算每对顶点最短路径的Floyd-Warshall算法

A、非连通图

B、连通图

C、稀疏图

D、稠密图

阅读下列函数说明和C代码，将应填入(n)处的字句写上。

[说明]

若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5-1所示，边表示城市间通信线路，边上标示的是建立该线路的代价。

[图5-1]

无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。

现用Prim算法生成网络的最小生成树。由网络G=(V，E)构造最小生成树T=(U，TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V-U里的边中，找出权值最小的边(u，v)，将边加入TE，并将顶点v加入集合U，重复上述操作直到U=V为止。

函数中使用的预定义符号如下：

define MAX 32768 /*无穷大权，表示顶点间不连通*/

define MAXVEX 30 /*图中顶点数目的最大值*/

typedef struct{

int startVex，stopVex; /*边的起点和终点*/

float weight; /*边的权*/

}Edge;

typedef struct{

char vexs[MAXVEX]; /*顶点信息*/

float arcs[MAXVEX*(MAXVEX-1)/2]; /*邻接矩阵信息，压缩存储*/

int n; /*图的顶点个数*/

}Graph;

[函数]

void PrimMST(Graph*pGraph, Edge mst[])

{

int i,j,k,min,vx,vy;

float weight，minWeight;

Edge edge;

for(i=0; i＜pGraph-＞n-1；i++){

mst[i].StartVex=0;

mst[i].StopVex=i+1;

mst[i].weight=pGraph-＞arcs[i];

}

for(i=0；i＜(1)；i++){/*共n-1条边*/

minWeight=(float)MAX;

min=i;

/*从所有边(vx，vy)中选出最短的边*/

for(j=i; j＜pGraph-＞n-1; j++){

if(mst[j].weight＜minWeight){

minWeight=(2);

min=j；

}

}

/*mst[minl是最短的边(vx，vy)，将mst[min]加入最小生成树*/

edge=mst[min]；

mst[min]=mst[i];

mst[i]=edge;

vx=(3);/*vx为刚加入最小生成树的顶点下标*/

/*调整mst[i+1]到mst[n-1]*/

for(j=i+1；j＜pGraph-＞n-1；j++){

vy=mst[j].StopVex;

if( (4) ){/*计算(vx，vy)对应的边在压缩矩阵中的下标*/

k=pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1；

}else{

k=pGraph-＞n*vx-vx*(vx+1)/2+vy-vx-1;

}

weight(5)；

if(weight＜mst[j].weight){

mst[j].weight=weight;

mst[j].StartVex=vx;

}

}

}

}

(1)

带权的连通无向图的最小(代价)生成树必是唯一的。()

A.Prim算法

B、Kruskal算法

C.Floyd算法

D、Dijkstra算法

A、非连通图

B、连通图

C、稀疏图

D、稠密图

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

A、深度优先搜索算法

B、广度优先搜索算法

C、求最小生成树的prim算法

D、拓扑排序算法