阅读下列函数说明和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)

阅读下列函数说明和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)


相关考题:

●试题二阅读下列程序或函数说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。【函数2.1说明】函数strcmp()是比较两个字符串s和t的大小。若s<t函数返回负数;若s=t函数返回0;若s>t,函数返回正数。【函数2.1】int strcmp(char *s,char *t){ while(*s *t (1) ){s++;t++;}return (2) ;}【程序2.2说明】在n行n列的矩阵中,每行都有最大的数,本程序求这n个最大数中的最小一个。【程序2.2】#includestdio.h#define N 100int a[N][N];void main(){ int row ,col,max,min,n;/*输入合法n(<100),和输入n×n个整数到数组a的代码略*/for (row=0;row<n;row++){for(max=a[row][0],col=1;col<n;col++)if( (3) )max=a[row][col];if( (4) )min=max;else if( (5) )min=max;}printf ("The min of max numbers is %d\n",min);}

一个有N个用户网络中,采用RSA算法在网络中进行加密通信,则满足所有用户通信需要的密钥个数是()。()A.N*(N-1) B.N C.2N D.N*N

图的生成树是不唯一的,一个连通图的生成树是一个最小连通子图,n个顶点的生成树有n-1条边,最小代价生成树是唯一的。( ) 此题为判断题(对,错)。

阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】 应用Prim算法求解连通网络的最小生成树问题。请阅读程序后填空。const int MaxInt=INT MAX; //INT MAX的值在<limits.h>中const int n=6; //图的顶点数,应由用户定义typedef int AdjMatrix[n][n]; //用二维数组作为邻接矩阵表示typedef struct{ //生成树的边结点int fromVex,to Vex; //边的起点与终点int weight; //边上的权值}TreeEdSenode;typedef TreeEdgeNode MST[n-1]; //最小生成树定义void PrimMST (AdjMatrix G,MST T,int rt){//从顶点rt出发构造图G的最小生成树T,rt成为树的根结点TreeEdgeNode e; int i,k=0,min,minpos,v;for(i=0;i<n;i++) //初始化最小生成树Tif(i!=rt){T[k].fromVex=rt;(1);T[k++].weight=G[rt][i];}for(k=0;k<n-1;k++){ //依次求MST的候选边(2);for(i=k;i<n-1;i++) 八遍历当前候选边集合if(T[i].weight<min) //选具有最小权值的候选边{min=T[i].weight;(3);}if(min==MaxInt) //图不连通,出错处理{cerr<<“Graph is disconnected!”<<endl; exit(1);}e=T[minpos];T[minpos]=T[k];(4);v=T[k].to Vex;for(i=k+1;i<n-1;i++) //修改候选边集合if(G[v][T[i].to Vex]<T[i].weight){T[i].weight=G[v][T[i].toVex];(5);}}}

试题三(共 20 分)阅读下列说明,回答问题 1 至问题 3,将解答填入答题纸的对应栏内。【说明】随着个人电脑和因特网的普及,越来越多的语音和数据通信以数字形式进行,使用网络多媒体技术可以在 IP 网络上实现多媒体通信、媒体点播等服务。因特网电话技术不仅限于语音 Vo IP(Voice over IP) ,它还集成了语音、视频和数据服务。【问题 1】 (9 分)请解释以下完成一个因特网电话服务所涉及的网络协议和应用标准。H.323,TCP,RTP,RTCP,UDP,RSVP,RTSP,IP,IP Multicast【问题 2】 (9 分)下图是一个因特网电话服务系统的网络协议及应用结构图,请将问题 1中列出的协议和应用标准填入图中正确的位置。【问题 3】 (2 分)如果要在H.323因特网电话终端和公共电话交换网络的H.324多媒体通信终端之间进行通信,需要如何实现?

试题三(共 15 分)阅读以下说明和 C 程序,将应填入 (n) 处的字句写在答题纸的对应栏内。

某省6个城市(A~F)之间的网络通信线路(每条通信线路旁标注了其长度公里数)如图2-13所示。如果要将部分千兆通信线路改造成万兆通信线路,以提升各个城市网络之间的通信容量,则至少要改造总计(66)公里的通信线路,这种总公里数最少的改造方案共有(67)个。A.1000B.1300C.1600D.2000

阅读下列说明和C++-代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 某发票(lnvoice)由抬头(Head)部分、正文部分和脚注(Foot)部分构成。现采用装饰(Decorator)模式实现打印发票的功能,得到如图5-1所示的类图。【C++代码】 #include using namespace std; class invoice{ public: (1){ cout

阅读下列说明和?C++代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】阅读下列说明和?Java代码,将应填入?(n)?处的字句写在答题纸的对应栏内。【说明】某快餐厅主要制作并出售儿童套餐,一般包括主餐(各类比萨)、饮料和玩具,其餐品种类可能不同,但其制作过程相同。前台服务员?(Waiter)?调度厨师制作套餐。现采用生成器?(Builder)?模式实现制作过程,得到如图?6-1?所示的类图。