有一个顶点编号为0~4的带权有向图G,现用Floyd算法求任意两个顶点之间的最短路径,在算法执行的某时刻,已考虑了0~2的顶点,现考虑顶点3,则以下叙述中正确的是()。
A.只可能修改从顶点0~2到顶点3的最短路径
B.只可能修改从顶点3到顶点0~2的最短路径
C.只可能修改从顶点0~2到顶点4的最短路径
D.所有两个顶点之间的路径都可能被修改
第1题:
第2题:
阅读下列说明,回答问题l和问题2,将解答填入答题纸的对应栏内。
【说明】
现需在某城市中选择一个社区建一个大型超市,使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图,其中顶点表示社区,边表示社区间的路线,边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置:即在给定图中选择一个顶点,使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径,即需要计算任意两个顶点之间的最短路径;然后对每个顶点,计算其他各顶点到该顶点的最短路径之和;最后,选择最短路径之和最小的顶点作为建大型超市的最佳位置。
下面是求解该问题的伪代码,请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下:
W:权重矩阵
n:图的顶点个数
sP:最短路径权重之和数组,SP[i]表示顶点i到其他各顶点的最短路径权重之和,i从1到n
rain_SP:最小的最短路径权重之和
min_v:具有最小的最短路径权重之和的顶点
i:循环控制变量
j:循环控制变量
k:循环控制变量
LOCATE-SHOPPINGMALL(W,n)
1 D(0)=W
2 for(1)
3 for i=1 t0 n
4 for j=1 t0 n
5
6 (2)
7 else
8 (3)
9 for i=1 to n
10 sP[i] =O
11 for j=1 to n
12 (4)
13 min sP=sP[1]
14 (5)
15 for i=2 t0 n
16 if min sP>sP[i]
17 min sP=sP[i]
18 min V=i
19 return (6)
第3题:
此题为判断题(对,错)。
第4题:
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
对有向图进行拓扑排序的方法是:
(1)初始时拓扑序列为空;
(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;
(3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。
函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号,顶点序列为vl,v2,…,vn,图G采用邻接表表示,其数据类型定义如下:
define MAXVNUM 50 /*最大顶点数*/
typedef struct ArcNode| /*表结点类型*/
int adjvex; /*邻接顶点编号*/
struct ArcNode*nextarc; /*指示下一个邻接顶点*/
{ArcNode;
typedef struct AdjList{ /*头结点类型*/
char vdata; /*顶点的数据信息*/
ArcNode*firstarc; /*指向邻接表的第一个表结点*/
}AdjList;
typedef struct LinkedDigraph /*图的类型*/
int n: /*图中顶点个数*/
AdjList Vhead[MAXVNUM]; /*所有顶点的头结点数组*/
}LinkedDigraph;
例如,某有向图G如图4-1所示,其邻接表如图4-2所示。
函数TopSort中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如下表所示:
【C代码】
int*TopSort(LinkedDigraph G){
ArcNode*P; /*临时指针,指示表结点*/
Queue Q; /*临时队列,保存入度为0的顸点编号*/
int k=0; /*临时变量,用作数组元素的下标*/
int j=0,w=0; /*临时变量,用作顶点编号*/
int*topOrder,*inDegree;
topOrder=(int*)malloc((G.n+1)*sizeof(int));/*存储拓扑序列中的顶点编号*/
inDegree=(int*)malloc((G.n+1)*sizeof(int));/*存储图G中各顶点的入度*/
if(!inDegree||!topOrder) return NULL;
(1); /*构造一个空队列*/
for(j=1;j<=Gn;j++){ /*初始化*/
topOrder[j]=0;inDegree[j]=0;
}
for(j=1;j<=Gn;j++) /*求图G中各顶点的入度*/
for(p=G.Vhead[j].firstarc;p;p=p->nextarc)
inDegree[P->adjvex]+=1;
for(j=i;j<=G.n;J++) /*将图G中入度为0的顶点保存在队列中*/
if(0==inDegree[j]) EnQueue(&Q,j);
while(! IsEmpty(Q)){
(2); /*队头顶点出队列并用w保存该顶点的编号*/
topOrder[k++]=w; /*将顶点W的所有邻接顶点的入度减l(模拟删除顶点w及该顶点出发的弧的操作)*/
for(p=G.Vhead[w].firstarc;p;p=p->nextarc){
(3)-=1;
if(0== (4) ) EnQueue(&Q,P->adjvex);
}/*for*/
}/ * while*/
free(inDegree);
if( (5) )
return NULL;
return topOrder;
}/*TopSort*/
根据以上说明和C代码,填充C代码中的空(1)
第5题:
下列算法中,()算法用来求图中某顶点到其他顶点所有顶点之间的最短路径。
A.Dijkstra
B.Floyed
C.Prim
D.Kruskal
第6题:
对于连通无向图G,以下叙述中,错误的是( )。
A. G 中任意两个顶点之间存在路径 B. G 中任意两个顶点之间都有边 C. 从 G 中任意顶点出发可遍历图中所有顶点 D. G的邻接矩阵是对称的
第7题:
第8题:
第9题:
第10题:
在有向图G中,若对于任意一对顶点都存在两条方向相反的路径,则称有向图G为()
第11题:
用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度()的次序来得到最短路径的。
第12题:
第13题:
求顶点间的最短路径问题,考虑的是下面的哪一种图()。
A、无向图
B、有向图
C、带权的无向图
D、带权的有向图
第14题:
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。
1. 【说明】
实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。
【算法】
第一步:首先访问连通图G的指定起始顶点v;
第二步:从V出发,访问一个与v(1)p,再从顶点P出发,访问与p(2)顶点q,然后从q出发,重复上述过程,直到找不到存在(3)的邻接顶点为止。
第三步:回退到尚有(4)顶点,从该顶点出发,重复第二、三步,直到所有被访问过的顶点的邻接点都已被访问为止。
因此,在这个算法中应设一个栈保存被(5)的顶点,以便回溯查找被访问过顶点的未被访问过的邻接点。
第15题:
此题为判断题(对,错)。
第16题:
一个有8个顶点的有向图,所有顶点的入度出度之和与所有顶点的出度之和的差是()
A.16
B.4
C.0
D.2
第17题:
B.Floyed算法求解所有顶点对之间的最短路径:
procedure floyed;
begin
for I:=1 to n do
for j:=1 to n do
if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点}
for k:=1 to n do {枚举中间结点}
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]<a[i,j] then begin
a[i,j]:=a[i,k]+a[k,j];
p[I,j]:=p[k,j];
end;
end;
第18题:
如果一个有向图(25),则是一棵有向树。
A.恰有一个顶点的人度为0,其余顶点的人度为1
B.恰有一个顶点的人度为1,其余顶点的人度为0
C.恰有一个顶点的人度为1,其余顶点的人度为2
D.恰有一个顶点的人度为1,其余顶点的度大于1
第19题:
第20题:
第21题:
在带权图中,两个顶点之间的路径长度是()。
第22题:
在无向图G中,若对于任意一对顶点都存在路径,则称无向图G为()
第23题:
求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则当图的顶点数为40时,计算时间约为()ms。
第24题: