![](https://static.youtibao.com/asksite/comm/pc/images/content_title_q.png)
使用Floyd算法计算图8-30的各对顶点之间的最短路径。
请帮忙给出正确答案和分析,谢谢!
![](https://static.youtibao.com/asksite/comm/pc/images/content_title_a.png)
请帮忙给出正确答案和分析,谢谢!
第1题
算法设计:对于给定的k个待安排的活动,计算使用最少会场的时间表.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待安排的活动.接下来的k行中,每行有2个正整数,分别表示k个待安排的活动的开始时间和结束时间.时间以0点开始的分钟计.
结果输出:将计算的最少会场数输出到文件output.txt.
第2题
A、Kruskal算法
B、Dijkstra算法
C、Floyd算法
D、Prim算法
第3题
图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.
算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).
结果输出:将计算的不同的着色方案数输出到文件output.txt.
第4题
已知图的邻接表表示的形式说明如下:
define MaxNum 50 //图的最大顶点数
typedef struct node{
int adjvex; //邻接点域
struct node*next; //链指针域
}EdgeNode; //边表结点结构描述
typedef struct{
char vertex; //顶点域
EdgeNode*firstedge;//边表头指针
}VertexNode; //顶点表结点结构描述
typedef struet{
VertexNode adjlist[MaxNum];//邻接表
int n,e; //图中当前的顶点数和边数
}ALGraph; //邻接表结构描述
下列算法输出图G的深度优先生成树(或森林)的边。阅读算法,并在空缺处填入合适的内容,使其成为一个完整的算法。
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[MaxNurn];
void DFSForest(ALGraph*G){
int i;
for(i=0;i<G—>n;i++)visited[i]= (1) ;
for(i=0;i<G—>n;i++)if(!visited[i])DFSTree(G,i);
}
void DFSTree(ALGraph*G,int i){
EdgeNode*p;
visited[i]=TRUE;
p=G—>adjlist[i].firstedge;
while(p!=NULL){
if(!visited[p—>adjvex]){
printf("<%c,%c",G—>adjlist[i].vertex,
G—>adjlist[p—>adjvex].vertex);
(2) ;
}
(3) ;
}
}
第5题
在一个有n个顶点的带权连通图中,有条边,则应该选用()算法来求这个图的最小生成树,从而使计算时间较少,
A、Prim
B、Kruskal
第6题
A.19x19x(25x20)
B.19x19x(20x25)
C.19x19x(5x25)
D.19x19x(5x20)
第7题
A.CSPF不再使用简单的邻居间链路代价作为度量值,而使用隧道的约束条件作为度量值
B.CSPF只计算到达隧道终点的最短路径,而SPF需要计算到达所有节点的最短路经
C.CSPF不存在负载分担,当两条路径有同样的权值时需要仲裁
D.SPF只计算到达隧道终点的最短路径,而CSPF需要计算到达所有节点的最短路经
第9题
A.多层建筑物各楼层的建筑面积不同时
B.基础深度不同的内外墙基础、宽度不同的散水等工程
C.多层建筑物各楼层的砌体砂浆标号不同时
D.当基础断面不同,在计算基础工程量时,就应分段计算
第10题
A.OSPF协议在计算区域问路由和自治系统外路由时使用的是距离矢量算法
B.OSPF能够在计算区域内路由时没有路由自环产生
C.OSPF能够保证在计算区域间路由时没有路由自环产生
D.OSPF能够保证在计算自治系统外部路由时没有路由自环产生