计算机类
单选题图中有关路径的定义是（ ）。A 由顶点和相邻顶点序偶构成的边所形成的序列B 由不同顶点所形成的序列C 由不同边所形成的序列D 上述定义都不是
题目
由顶点和相邻顶点序偶构成的边所形成的序列
由不同顶点所形成的序列
由不同边所形成的序列
上述定义都不是
参考答案和解析
相似问题和答案
第1题：
● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点 vi 必然在顶点 vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定 （57）
（57）
A. 包含回路
B. 是强连通图
C. 是完全图
D. 是有向树
第2题：
A、线框造型
B、曲面造型
C、表面造型
D、实体造型
第3题：
第4题：
在由许多项目组成的大型工程中，用顶点表示项目，有向边表示项目之间开始的先后秩序关系，这种用顶点表示活动的图称为AOV网络，其常用的一种存储结构是(15)。
为规划整个工程的实现，通常要对上述的顶点进行(16)排序，据此可获得项目的(17)序列。但并不是所有图都能获得这样的系列，如(18)图就不能获得这种序列。因为在这种情况下，所体现的先后关系不是(19)。
A．队列表
B．连通表
C．邻接表
D．路径表
第5题：
在由许多项目组成的大型工程中，用顶点表示项目，有向边表示项目之间谁先开工的先后关系，这种用顶点表示活动的图称为AOV网络，其常用的一种存储结构是(40)。为规划整个工程的实现，通常要对上述图的顶点进行(41)排序，据此可获得项目的(42)序列。
A．队列表
B．连通表
C．邻接表
D．路径表
第6题：
A、通过该顶点的简单路径数
B、与该顶点相邻接的顶点数
C、通过该顶点的回路数
D、与该顶点连通的顶点数
第7题：
阅读下列说明和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)
(1)InitQueue(&Q) (2)DeQueue(&Q，&w) (3)inDegree[p->adjvex] (4)inDegree[p->adjvexj (5)k!=G．N 解析：根据空(1)的后面注释是构造一个空队列，程序的开始已经定义了一个队列Q，那么此处只需初始化这个队列即可，所以空(1)应填InitQueue(&Q)。
根据空(2)后面的解释，如果队列不空，那么就将队列的元素依次出队列，所以空(2)应为DeQueue(＆Q，＆w)。
空(3)、(4)上下端的功能是将顶点w的所有邻接顶点的入度减l，数组inDegree中存放各个顶点的入度，所以空(3)应为inDegree[p->adjvex]，并判断与顶点w相邻的顶点有没有入度为零的顶点，如果有，就把这个顶点入队列，所以空(4)也填inDegree[p->adjvex]。
最后，最外层循环结束，如果拓扑序列中元素的个数k不等于定点数n，那么就说明有向图中存在环，返回NULL上，所以空(5)填k!=G．n。
第8题：
拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，(52)为下图所示有向图的一个拓扑序列。
A．1 2 3 4 5 6 7
B．1 5 2 6 3 7 4
C．5 1 2 6 3 4 7
D．5 1 2 3 7 6 4
解析：本题考查有向图的应用。
拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在图中存在从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点cj之前。
对有向图进行拓扑排序的方法如下：
①在有向图中选择一个入度为零(没有前驱)的顶点且输出之；
②从网中删除该顶点及从该顶点出发的所有弧；
③重复上述两步，直至图中不存在入度为零的顶点为止。
对题目中所给的有向图进行拓扑排序的顶点序列为：5126374、5126734、1526374、 1526734。
第9题：
拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，V一定在w之前。下面有向图的拓扑序列是( )
A.41235
B.43125
C.42135
D.41=325
第10题：
B.1526734
C.5123764
D.5126374