己知某带权图G的邻接表如下所示，其中表结点的结构为：则图G是______。

● 已知某带权图G 的邻接表如下所示，其中表结点的结构为：

则图G 是 （35） 。

（35）

A. 无向图

B. 完全图

C. 有向图

D. 强连通图

●已知某带权有向图G（顶点数为6，顶点编号为1 至6）的邻接表如下所示，

其中表结点的结构为：

则图G 中含有的弧数为__(39) 。

(39)A．9 B．11 C．15 D．18

●已知某带权有向图G（顶点数为6，顶点编号为1 至6）的邻接表如下所示，

其中表结点的结构为：

则图G 中含有的弧数为() 。

A．9 B．11 C．15 D．18

已知某带权图G的邻接表如下所示，其中表结点的结构为：以下关于该图的叙述中，正确的是（）。

A.图G是强连通图 B.图G具有14条弧 C.顶点B的出度为3 D.顶点B的入度为3

阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的语句填写完整。

[说明]

函数int Toplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下。

例如，某AOE-网如图6-22所示，其邻接表存储结构如图6-23所示。

[函数]

某图 G 的邻接表如下所示。以下关于图 G的叙述中，正确的是 () 。

A. G 是强连通图 B. G 是有 7 条弧的有向图C. G 是完全图 D. G 是有 7条边的无向图

下图是带权的有向图G的邻接表表示法，求： (1)以结点V1出发深度遍历图G所得的结点序列； (2)以结点V1出发广度遍历图G所得的结点序列； (3)从结点V1到结点V8的最短路径； (4)从结点V1到结点V8的关键路径。

【中国海洋大学1999四(10分)】

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

【说明】

函数int Toplogical(Linded WDipaph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：

typedefstruct Gnode{ /* 邻接表的表结点类型*/

iht adjvex; /* 邻接顶点编号*/

iht weight; /* 弧上的权值*/

street Gnode *nextarc; /* 指示下一个弧的结点*/

}Gnode;

typedef struct Adjlist{ /* 邻接表的头结点类型*/

char vdata; /*顶点的数据信息*/

struct Gnode *Firstadj; /* 指向邻接表的第一个表结点*/

}Adjlist;

typedef street LinkedWDigraph{ /* 图的类型*/

int n, e; /* 图中顶点个数和边数*/

struct Adjlist *head; /*指向图中第一个顶点的邻接表的头结点 */

} LinkedWDigraph;

例如，某AOE-网如图5-1所示，其邻接表存储结构如图5-2所示。

【函数】

iht Toplogical(LinkedWDigraph G)

{ Gnode *p;

intj, w, top = 0;

iht *Stack, *ye, *indegree;

ye = (int *)malloe((G.n+1) * sizeof(int));

indegree = (int *)malloc((G.n+1)*sizeof(int)); /* 存储网中各顶点的入度*/

Stack = (int *)malloe((G.n+1)*sizeof(int)); /* 存储入度为0的顶点的编号*/

if(!ve||!indegree || !Stack) exit(0);

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

ve[j] = 0; indegree[j]= 0;

}/*for*/

for(j= 1;j＜=G.n;j++) { /* 求网中各顶点的入度*/

p = G.head[j].Firstadj;

while (p) {

(1); p = p→nextarc;

}/*while*/

}/*for*/

for (j = 1; j ＜= G.n; j++) /*求网中入度为0的顶点并保存其编号*/

if (!indegree[j]) Stack[++top] =j;

while (top ＞ 0) {

w=(2);

printf("%e ", G.head[w].vdata);

p = G.head[w].Firstadj;

while (p) {

(3);

if (!indegree [p→adjvex])

Staek[++top] = p→adjvex;

if((4))

ve[p→adjvex] = ve[w] + p→weight;

p = p→nextarc;

}/* while */

}/* while */ return (5); }/*Toplogieal*/

有6个顶点的图G的邻接表如下所示，以下关于图G的叙述中，正确的是（43）。

A．G是无向图，有9条边

B．G是有向图，有9条弧

C．G是无向图，有15条边

D．G是有向图，有15条弧

●有6个顶点的图G的邻接表如下所示，以下关于图G的叙述中，正确的是(43)。

(43) A.G是无向图，有9条边

B．G是有向图，有9条弧

C．G是无向图，有15条边

D.G是有向图，有15条弧