网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
已知某带权图G的邻接表如下所示，其中表结点的结构为：
以下关于该图的叙述中，正确的是( )。
以下关于该图的叙述中，正确的是( )。
A.图G是强连通图
B.图G具有14条弧
C.顶点B的出度为3
D.顶点B的入度为3
B.图G具有14条弧
C.顶点B的出度为3
D.顶点B的入度为3
参考答案
参考解析
解析：本题考查数据结构基础知识。
从题图中可知，顶点A、B、C、D、E的编号为1～5，因此顶点A的邻接表中的两个结点表示：存在顶点A至顶点B的弧且权值为5，存在顶点A至顶点D的弧且权值为8，再考查顶点B只有一个邻接顶点E，因此该图为有向图，有7条弧，如下图所示。
若在有向图中，每对顶点之间都存在路径，则是强连通图。上图不是强连通图，例如，顶点C至B有路径，反之则没有路径。在有向图中，顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目。对于顶点B，其出度为1，而入度为3。
从题图中可知，顶点A、B、C、D、E的编号为1～5，因此顶点A的邻接表中的两个结点表示：存在顶点A至顶点B的弧且权值为5，存在顶点A至顶点D的弧且权值为8，再考查顶点B只有一个邻接顶点E，因此该图为有向图，有7条弧，如下图所示。
若在有向图中，每对顶点之间都存在路径，则是强连通图。上图不是强连通图，例如，顶点C至B有路径，反之则没有路径。在有向图中，顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目。对于顶点B，其出度为1，而入度为3。
更多 “已知某带权图G的邻接表如下所示，其中表结点的结构为： 以下关于该图的叙述中，正确的是( )。A.图G是强连通图 B.图G具有14条弧 C.顶点B的出度为3 D.顶点B的入度为3 ” 相关考题
考题
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是：对于图G中的每个顶点 vi，将所有邻接于vi的顶点vj连成一个单链表，这个单链表就称为顶点vi的邻接表，其中表头称作顶点表结点VertexNode，其余结点称作边表结点EdgeNode。将所有的顶点表结点放到数组中，就构成了图的邻接表AdjList。邻接表表示的形式描述如下： define MaxVerNum 100 /*最大顶点数为100*/typedef struct node{ /*边表结点*/int adjvex; /*邻接点域*/struct node *next; /*指向下一个边表结点的指针域*/ }EdgeNode;typedef struct vnode{ /*顶点表结点*/int vertex; /*顶点域*/EdgeNode *firstedge; /*边表头指针*/}VertexNode;typedef VertexNode AdjList[MaxVerNum]; /*AdjList是邻接表类型*/typedef struct{AdjList adjlist; /*邻接表*/int n; /*顶点数*/}ALGraph; /*ALGraph是以邻接表方式存储的图类型*/深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。下面的函数利用递归算法，对以邻接表形式存储的图进行深度优先搜索：设初始状态是图中所有顶点未曾被访问，算法从某顶点v出发，访问此顶点，然后依次从v的邻接点出发进行搜索，直至所有与v相连的顶点都被访问；若图中尚有顶点未被访问，则选取这样的一个点作起始点，重复上述过程，直至对图的搜索完成。程序中的整型数组visited[]的作用是标记顶点i是否已被访问。[函数]void DFSTraverseAL(ALGraph *G)/*深度优先搜索以邻接表存储的图G*/{ int i;for(i=0;i＜(1);i++) visited[i]=0;for(i=0;i＜(1);i++)if((2)) DFSAL(G,i);}void DFSAL(ALGraph *G,int i) /*从Vi出发对邻接表存储的图G进行搜索*/{ EdgeNode *p;(3);p=(4);while(p!=NULL) /*依次搜索Vi的邻接点Vj*/{ if(! visited[(5)]) DFSAL(G,(5));p=p-＞next; /*找Vi的下一个邻接点*/}}
考题
已知某图的邻接表如图4-12所示。①此邻接表所对应的无向图为(14)。②此图由F开始的深度优先遍历为(15)。③此图由9开始的深度优先遍历的支撑树为(16)。④此图由F开始的广度优先遍历为(17)。⑤此图由9开始的广度优先遍历的支撑树为(18)。A．B．C．
考题
阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的语句填写完整。[说明]函数int Toplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下。例如，某AOE-网如图6-22所示，其邻接表存储结构如图6-23所示。[函数]
考题
阅读下列函数说明和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*/
考题
对于下面的有向图，其邻接矩阵是一个（41）的矩阵, 采用邻接链表存储时，顶点0的表结点个数为 2，顶点3的表结点个数为0，顶点1的表结点个数为（42）。
A.0
B.1
C.2
D.3
考题
对于下面的有向图，其邻接矩阵是一个（41）的矩阵, 采用邻接链表存储时，顶点0的表结点个数为 2，顶点3的表结点个数为0，顶点1的表结点个数为（42）。
A.3X4
B.4X3
C.6X6
D.7X7
考题
某有向图G的邻接表如下图所示,可看出该图中存在弧,而不存在从顶点Vi出发的弧。关于图G的叙述中,错误的是()。
A.G中存在回路
B.G中每个顶点的入度都为1
C.G的邻接矩阵是对称的
D.G中不存在弧瓜
考题
某有向图G的邻接表如下图所示，可看出该图中存在弧，而不存在从顶点v.出发的弧。以下关于图G的叙述中，错误的是（ ）
A.G中存在回路
B.G中每个顶点的入度都为1
C.G的邻接矩阵是对称的
D.不存在弧小于V3,vi>
考题
对于如下所示的有向图，其邻接矩阵是一个（ ）的矩阵，采用邻接链表存储时顶点的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为（请作答此空）
A.2.1
B.2.2
C.3.4
D.4.3
考题
对于如下所示的有向图，其邻接矩阵是一个（请作答此空）的矩阵，采用邻接链表存储时顶点的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为（ ）
A.5*5
B.5*7
C.7*5
D.7*7
考题
单选题设无向图G有n个顶点m条边，则其邻接表中表结点数是（）A
nB
2nC
mD
2m
热门标签
最新试卷