在无向图G的邻接矩阵A中，若A[i，j]等于1，则A[j，i]等于（）A、i+jB、i-jC、1D、0

题目

在无向图G的邻接矩阵A中，若A[i，j]等于1，则A[j，i]等于（）

A、i+j
B、i-j
C、1
D、0

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为(58)，其中非零元素数目为(59)。

A．E2

B．N2

C．N2-E2

D．N22+E2

正确答案：B

第2题：

若定义一维数组为:Dim a(i To j),则该数组的元素为______个。

A. j-i

B. j-i+1

C. j*i

D. i+j

参考答案：B

第3题：

●试题六

阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值;c为二维数组，存储有向网中每一对顶点间的最短路径长度;kay为二维数组，存储最短路径，kay［i］［j］=k表示顶点i 到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有：

Input():输入有向网的顶点数、各条弧及权值，建立带权领接矩阵a。若顶点i到顶点j有弧，则a［i］［j］取弧上的权值，否则a［i］［j］的值取NoEdge。

AllPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。

OutShortestPath(int i,int j):计算顶点i到顶点j的最短路径。

outputPath(int i,int j):输出顶点i到顶点j的最短路径上的顶点。

Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1，C2，…，Cn,其中C0是已知的带权邻接矩阵，a,Ck(i,j)(0≤i,j＜n)表示从顶点i到顶点j的中间顶点序号不大于k 的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n,有Ck(i,j)=C0(i,j)=a［i］［j］。递推地产生C1，C2，…，Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。

【C++代码】

#include<iostream．h>

＃define NoEdge 10000 //当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示

void Make2DArray(int * * &x,int rows,int cols);

class AdjacencyWDigraph{

private

int n;//有向网中的顶点数目

int**a;//存储顶点间弧上的权值

int**c;//存储计算出的最短路径长度

int**kay;//存储求出的最短路径

pubic:

int Vertices()const {return n;}

void AllPairs();

void Input();//输入有向网的顶点数、各条弧及权值，建立邻接矩阵a

void OutShortestPath(int i,int j);//计算顶点i到j的最短路径(试卷中未列出)

~AdjacencyWDigraph();//析构函数(试卷中未列出)

private:

void outputPath(int i,int j);

};

void AdjacencyWDigraph::AllPairs()

{int i,j,k,t1,t2,t3;

for(i=1;i＜=n;k++)

for(j=1;j＜=n;++j)

{c［i］［j］= (1) ;kay［i］［j］=0;}

for(k=1;k＜=n;k++)

for(i=1;i＜=n;i++){

if(i==k) continue;

t1=c［i］［k］;

for(j=1;j＜=n;j++){

if(j==k||j==i)continue;

t2=c［k］［j］;t3=c［i］［j］;

if(t1!=NoEdge && t2!=NoEdge &&(t3==NoEdge||t1+t2＜t3))

{c［i］［j］= (2) ；kay［i］［j］= (3) ;}

}//for

}

void AdjacencyWDigraph:: outputPath(int i,int j)

{//输出顶点i到j的最短路径上的顶点

if(i==j)return;

if(kay［i］［j］==0)cout＜＜j＜＜′′;

else { outputPath(i, (4) ); outputPath( (5) );}

}

void Adjacency WDigraph::Input()

{int i,j,u,v,w,E;

cout＜＜″输入网中顶点个数：″;cin＞＞n;

cout＜＜″输入网中弧的个数:″;cin＞＞E;

Make2DArray(a,n+1,n+1);

for(i=1;i＜=n;i++)

for(j=1;j＜=n;j++)a［i］［j］=NoEdge;

for(i=1;i＜=n;i++)a［i］［i］=0;

Make2DArray(c,n+1,n+1);

Make2DArray(kay,n+1,n+1);

for(i=1;i＜=E;i++){

cout＜＜″输入弧的信息(起点终点权值)：″；cin＞＞u＞＞v＞＞w;a［u］［v］=w;

}

void Make2DArray(int**&x,int rows,int cols)

{int i,j;

x=new int*［rows+1］;

for(i=0;i＜rows+1;i++)x［i］=new int ［cols+1］;

for(i=1;i＜=rows;i++)

for(j=1;j＜=cols;j++＝x［i］［j］=0;

}

正确答案：

●试题六

【答案】（1）a［i］［j］（2）t1+t2,其中t1可以写成c［i］［k］,t2可以写成c［k］［j］

（3）k（4）kay［i］［j］（5）kay［i］［j］,j

【解析】（1）此处的双层循环的作用是给数组c赋初值。即把最初的i号结点到j号结点的路径长度存入c。由题目中已经有说明："Input（）；输入有向图的顶点数、各条弧及权值，建立带权邻近矩阵a。若顶点i到顶点j有弧，则a［i］［j］取弧上的权值，否则a［i］［j］的值取NoEdge。"所以应填a［i］［j］。（2）首先应该说明的是此处的三层循环所完成的功能是用递推的方式，在i号结点和j号结点中插入一个k号结点，然后比较c［i］［j］与c［i］［k］＋c［k］［j］，如果c［i］［k］＋c［k］［j］小于c［i］［j］，则用 c［i］［k］+c［k］［j］代替 c［i］［j］。这里用到的原则就是： c［i］［k］，c［k］［j］分别是i到k，k到j的最短路径，若i到j要经过k，则 c［i］［k］+c［k］就是i到j过结点k的最短路径。（3）由于题目中提到"kay为二维数组，存储最短路径，kay［i］［j］=k表示顶点i到达顶点j的最短路径必须经过顶点k。"所以，应填k。（5）此处用到了程序的递归，其实这个过程很好理解，也就是判断当中间结点为0，表示i，j直接为最短路径，则直接打印即可。如果有中间结点k，则先打印从i到k的路径，再打印从k到j的路径。此处的中间结点存在kay［i］［j］里，所以（4）填kay［i］［j］。

第4题：

● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为（60），其中非零元素数目为（61）。

正确答案：B,C

第5题：

利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=共有n个节点,节点编号1~n,设C

利用动态规划法求解每对节点之间的最短路径问题时，设有向图G=＜V，E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度)，则求解该问题的递推关系式为(28)。

A．Dk(i,j)=Dk-1(i,j)+C(i,j)

B．Dk(i,j)=min{Dk-1(i,j),Dk-1(i,j)+C(i,j)}

C．Dk(i,j)=Dk-1(i,k)+Dk-1(k,j)

D．Dk(i,j)=min{Dk-1(i,j),Dk-1(i,k)+Dk-1(k,j)}

正确答案：D
解析：从“Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度”中，我们得到一个提示，在求i,j之间最短路径的时候，会考虑它经过哪些节点能缩短原来的路径。在Dk(i,j)=min{Dk-1(i,j),Dk-1(i,k)+Dk-1(k,j)}中，Dk(i,j)表示i到j不经过k的路径长度，而Dk-1(I,k)+Dk-1(k,j)表示i到j经过k的路径长度，且min()函数用于找最小值，所以此式正确。

第6题：

利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时，设有向图G=＜V，E＞共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用Dk(i，j)表示从i到j并且不经过编号比众还大的结点的最短路径的长度(Dn(i，j即为图G中结点i到j的最短路径长度)，则求解该问题的递推关系式为(56)。

A．Dk(i，j)；Dk-1(i，j)+C(i，j)

B．Dk(i，j)：min{Dk-1(i，j),Dk-1(i，j)+C(i，j)}

C．Dk(i，j)：Dk-1(i，k)+Dk-1(i，j)

D．Dk(i，j)；min{Dk-1(i，j),Dk-1(i，k)+Dk-1(k，j)}

正确答案：D
解析：设p^k(i，j)表示从i到j并且不经过编号比k还大的结点的最短路径，那么p^k(i，j)有以下两种可能：
①p^k(i，j)经过编号为k的结点，此时p^k(i，j)可以分为从i到k和从k到j的两段，易知产p^k(i，j)的长度为D^k-1(i，k)+D^k-1(k，j)。
②p^k(i，j)不经过编号为k的结点，此时产p^k(i，j)的长度为D^k-1(i，j)。

第7题：

在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于______。

参考答案：1

第8题：

阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站0出发乘公交车至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G(用邻接矩阵g表示)，有向图的顶点是车站，若有某条公交线路经i站能到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j＞。如是这样，从站点x至站点y的最少上车次数便对应图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

【函数5-9】

include ＜stdio.h＞

define M 20

define N 50

int a[N+1]; /*用于存放一条线路上的各站编号*/

iht g[N][N]; /*存储对应的邻接矩阵*/

int dist[N]; /*存储站0到各站的最短路径*/

int m,n;

void buildG()

{

int i,j,k,sc,dd;

printf ("输入公交线路数，公交站数\n");

scanf("%d%d", &m, &n);

for(i=0; i＜n; i++) /*邻接矩阵清0*/

for(j = 0; j ＜ n; j++)g[i][j] = 0;

for(i=0; i＜m; i++){

printf("沿第%d条公交车线路前进方向的各站编号(O＜=编号＜=%d,-1结束):\n",

i+1, n-1);

sc=0;/* 当前线路站计数器 */

while(1){

scanf("%d",&dd);

if(dd==-1)break;

if(dd＞=0 && dd＜n) (1);

}

a[sc]=-1;

for(k=1;a[k]＞=0; k++) /* 处理第i+1条公交线路 */

for(j=0; j＜k; j++)

g(2)=1;

}

int minLen()

{

int j, k;

for(j=0;j＜n;j++)dist[j]=g[0][j];

dist[0]=1;

do{

for(k=-1,j=0;j＜n;j++) /* 找下一个最少上车次数的站*/

if(dist[j]＞0&&(k==-1 || dist[j]＜dist[k]))k=j;

if (k＜0 || k==n-1) break;

dist[k]=-dist[k]; /* 设置k站已求得上车次数的标记 */

for(j=1;j＜n;j++) /* 调整经过k站能到达的其余各站的上车次数 */

if ((3) && (dist[j]==0 || -dist[k]+1＜dist[j]))

dist[j]=(4);

}while(1);

j=dist[n-1];

return (5);

}

void main()

{

int t；

buildG();

if((t=minLen()＜0)printf("无解!\n");

else pdnff("从0号站到%d站需换车%d次\n”，n-1，t)；

}

正确答案：(1) a[sc++]=dd (2) [a[j]][a[k]] (3) dist[j]＞=0 && g[k][j]==1 (4) -dist[k]+1 (5) k0 ?-1:j-1
(1) a[sc++]=dd (2) [a[j]][a[k]] (3) dist[j]＞=0 && g[k][j]==1 (4) -dist[k]+1 (5) k0 ?-1:j-1 解析：本题考查图的应用——求最少换车次数。
函数buildG的功能是输入车站数、公交线路数，以及各公交线路的车站等信息，然后构建有向图的邻接矩阵。对每一条线路，按从始发站至终点站的顺序输入线路上的车站编号。空 (1)所在while循环正是用来顺序读入某一条线路上的车站编号。为了实现输入-1表示结束，先将输入值保存在临时变量dd中，若dd不为-1，则将dd的值保存到数组a中，sc是当前线路站计数器，注意到while循环体中并没有类似sc++的语句，故空(1)应填a[sc++]=dd。
某条新路输入完毕后，用for循环来构建有向图G中关于该条线路的邻接矩阵。根据邻接矩阵的定义易得，空(2)应填“[a[j]][a[k]]”。
函数minLen的功能是根据图G的邻接矩阵求从站0到站n-1的最少换车次数。函数中采用求两点间最短路径的算法。先将邻接矩阵的第0行内容复制到数组dist[]，并置dist[0]为1。这样，就在dist[]中预置了能从站0出发直接到达的车站。接着是一个循环，每次循环做以下事情：利用数组dist[]，找出下一个最少上车次数的站号。如果没有这样的站号(站0不可达站n-1)，或下一个最少上车次数的站就是n-1(找到解)，则结束循环。若找到下一个最少上车次数的车站但还不是n-1号站，则设置该站已求得站0到达该站所需最少上车次数dist[k]；将dist[k]的值变为负值。值为负就表示已为站k求得解，到达站k的最少上车次数为-dist[k]。由于已求得站k最少上车次数，那些还未求得的最少上车次数、经过k站可以达到的车站的上车次数应做相应调整。顺序考查各站j(站0除外)，若站j还未求得解(dist[j]＞0)，并且经站 k能直接到达站j(g[k][j]=1)，并且或从站0不能到达站j，或到达站j的上车次数比经过站k到达的次数要多(dits[j]==0|| -dist[k]+1dist[j])，则到达站j的最少上车次数改为-dist[k]+1。故空(3)应为“dist[j]＞=0&& g[k][j]==1”，空(4)应填“-dist[k]+1”。
求解循环结束有两种情况，一是没有找到下一个最少上车次数的站(k0)，二是下一个最少上车次数的站就是n-1号站。若是前者，函数因未找到解而返回-1(任意负值均可)；若是后一种情况，从站0到站n-1上车次数为dist[n-1]，即换车次数是dist[n-1]-1。故空
(5)应填“k0 ?-1:j-1”。

第9题：

●设一个包含N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构（矩阵元素 A[i][j]等于1/0 分别表示顶点i与顶点 j 之间有／无边），则该矩阵中的非零元素数目为 (60)。

(60)

A．N

B．E

C．2E

D．N+E

正确答案：C

第10题：

B 宽度优先（种子染色法）

5．关键路径

几个定义：顶点1为源点，n为汇点。

a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;

b. 顶点事件最晚发生时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);

c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表示，则Ee[I] = Ve[j];

d. 边活动最晚开始时间 El[I], 若边I由<j,k>表示，则El[I] = Vl[k] – w[j,k];

若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。

求解方法：

a. 从源点起topsort,判断是否有回路并计算Ve;

正确答案：

在无向图G的邻接矩阵A中，若A[i，j]等于1，则A[j，i]等

题目

相似问题和答案

更多相关问题

相关内容