某有向图G的邻接表如下图所示,可看出该图中存在弧,而不存在从顶点Vi出发的弧。关于图G的叙述中,错误的是()。 A.G中存在回路 B.G中每个顶点的入度都为1 C.G的邻接矩阵是对称的 D.G中不存在弧瓜

题目
某有向图G的邻接表如下图所示,可看出该图中存在弧,而不存在从顶点Vi出发的弧。关于图G的叙述中,错误的是()。

A.G中存在回路
B.G中每个顶点的入度都为1
C.G的邻接矩阵是对称的
D.G中不存在弧瓜
相似考题

1.● 若无向连通图 G 具有 n个顶点，则以下关于图 G的叙述中，错误的是（43）。（43）A.G 的边数一定多于顶点数B.G 的生成树中一定包含 n个顶点C.从 G 中任意顶点出发一定能遍历图中所有顶点D.G 的邻接矩阵一定是n阶对称矩阵

2.试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

3.用相邻矩阵A表示图，判定任意两个顶点Vi和Vi，之间都有长度为m的路径相连，则只要检查(40)的第i行第j列的元素是否为0即可。从邻接矩阵可以看出，该图共有(41)个顶点。如果是有向图，该图有(42)条弧；如果是无向图，则共有(43)条边。A．mAB．AC．AmD．Am-1

4.阅读下列函数说明和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的下一个邻接点*/}}

更多“某有向图G的邻接表如下图所示,可看出该图中存在弧,而不存在从顶点Vi出发的弧。关于图G的叙述中,错误的是()。 ”相关问题

  • 第1题：

    阅读下列说明和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)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。

  • 第2题：

    若无向连通图G具有n个顶点，则以下关于图G的叙述中，错误的是( )。

    A．c的边数一定多于顶点数

    B．G的生成树中一定包含n个顶点

    C．从c中任意顶点出发一定能遍历图中所有顶点

    D．G的邻接矩阵一定是n阶对称矩阵


    正确答案：A
    解析：设无向连通图G如下图(a)所示，其邻接矩阵如图(b)所示。cl无向连通图的生成树是该图的极小连通子图，如果图中有n个顶点，则生成树包含n个顶点、n-1条边。如果在图的生成树上任意加一条边，则必然形成回路。无向连通图可能正好是一棵生成树，如下图(c)所示，其边数小于顶点数。无向图的邻接矩阵一定是对称矩阵，因为顶点i与j之间的边即表示i到j的边，也表示j到i的边，如图(b)所示。

  • 第3题：

    在一个有向图G的拓扑序列中,顶点Vi排列在Vj之前,说明图G中(59)。A.一定存在弧B.

    在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（59）。

    A.一定存在弧＜vi,vj＞

    B.一定存在弧＜vj,vi＞

    C.可能存在vi到vj的路径，而不可能存在vj到vi的路径

    D.可能存在vj到vi的路径，而不可能存在vi到vj的路径


    正确答案：C
    拓扑序列是拓扑排序的产出物。对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。由此可见，如果Vi排列在Vj之前，说明可能存在vi到vj的路径，而不可能存在vj到vi的路径。

  • 第4题：

    某图G的邻接矩阵如下所示。以下关于该图的叙述中，错误的是（ ）。

    A.该图存在回路（环）B.该图为完全有向图C.图中所有顶点的入度都大于0D.图中所有顶点的出度都大于0


    正确答案：B

  • 第5题：

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

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


    正确答案：B

  • 第6题：

    对于连通无向图 G，以下叙述守，错误的是（43）

    A.G 中任意两个顶点之间存在路径
    B.G 中任意两个顶点之间都有边
    C.从 G 中任意顶点出发可遍历图中所有顶点
    D.G 的邻接矩阵是对称的

    答案：B
    解析：
    在一个无向图G中，若从顶点vi到顶点vj有路径相连（当然从vj到vi也一定有路径），则称vi和vj是连通的。如果图中任意两点都是连通的，那么图被称作连通图。但不是任意两顶点之间都存在边。

  • 第7题：

    拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是（ ）。

    A.41235
    B.43125
    C.42135
    D.41325

    答案：A
    解析：
    拓扑排序通俗一点来讲，其实就是依次遍历没有前驱结点的结点。而某一时刻没有前驱结点的结点有可能存在多个，所以一个图的拓扑排序可能有多个。
    4号结点没有前戏，所以拓扑排序的第一个元素是4。当4访问完了就可以访问1，1号访问完了就可以访问2，2号访问完了就可以访问3或5。所以拓扑排序结果为：412(35)。


  • 第8题：

    在有向图的邻接表中，顶点Vi在表结点中出现的次数是顶点Vi的（）。

    • A、度
    • B、入度
    • C、出度
    • D、依附于顶点Vi的弧数

    正确答案:B

  • 第9题：

    在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的（），对于有向图来说等于该顶点的（）


    正确答案:度数；出度数

  • 第10题：

    单选题
    在有向图的邻接表中，顶点Vi在表结点中出现的次数是顶点Vi的（）。
    A

    度

    B

    入度

    C

    出度

    D

    依附于顶点Vi的弧数


    正确答案： A
    解析： 暂无解析

  • 第11题：

    单选题
    在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。
    A

    G中有弧<Vi，Vj>

    B

    G中有一条从Vi到Vj的路径

    C

    G中没有弧<Vi，Vj>

    D

    G中有一条从Vj到Vi的路径


    正确答案： D
    解析：

  • 第12题：

    填空题
    若在有向图G中存在一条弧i,Vj>，则称顶点Vj（）于顶点Vi。

    正确答案： 邻接
    解析： 暂无解析

  • 第13题：

    设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。

    若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。


    正确答案：(6)O(n+e) (7)O(n2)
    (6)O(n+e) (7)O(n2) 解析：邻接表：对有n个顶点和e条弧的有向图而言，在拓扑排序中，若有向图无环，则每个顶点进出队列各一次，共执行e次，搜索算法时间复杂度是由n和e共同决定的，所以总的时间复杂度为O(n+e)。
    当用邻接矩阵：对于每个顶点，查找相邻边的时间复杂度是O(n)，一共有n个顶点，所以总的时间复杂度是O(n2)。

  • 第14题：

    在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()。

    A.G中有弧

    B.G中有一条从Vi到Vj的路径

    C.G中没有弧

    D.G中有一条从Vj到Vi的路径


    正确答案：D

  • 第15题：

    对于连通无向图G，以下叙述中，错误的是（ ）。

    A. G 中任意两个顶点之间存在路径 B. G 中任意两个顶点之间都有边 C. 从 G 中任意顶点出发可遍历图中所有顶点 D. G的邻接矩阵是对称的


    正确答案：B

  • 第16题：

    某有向图 G 及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中，错误的是（ ）。

    A. 有向图的邻接矩阵可以是对称矩阵B. 第 i行的非零元素个数为顶点 i的出度C. 第 i行的非零元素个数为顶点 i的入度D. 有向图的邻接矩阵中非零元素个数为图中弧的数目


    正确答案：C

  • 第17题：

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

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


    正确答案：D

  • 第18题：

    某有向图G的邻接表如下图所示，可看出该图中存在弧，而不存在从顶点v.出发的弧。以下关于图G的叙述中，错误的是（ ）

    A.G中存在回路
    B.G中每个顶点的入度都为1
    C.G的邻接矩阵是对称的
    D.不存在弧小于V3,vi>

    答案：C
    解析：

  • 第19题：

    以下关于无向连通图 G 的叙述中，不正确的是（60）。

    A.G 中任意两个顶点之间均有边存在
    B.G 中任意两个顶点之间存在路径
    C.从 G 中任意顶点出发可遍历图中所有顶点
    D.G 的临接矩阵是对称矩阵

    答案：A
    解析：

  • 第20题：

    若在有向图G中存在一条弧i,Vj>，则称顶点Vj（）于顶点Vi。


    正确答案:邻接

  • 第21题：

    在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是（）。

    • A、G中有弧
    • B、G中有一条从Vi到Vj的路径
    • C、G中没有弧
    • D、G中有一条从Vj到Vi的路径

    正确答案:D

  • 第22题：

    填空题
    在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的（）；对于有向图来说等于该顶点的（）。

    正确答案： 度,出度
    解析： 暂无解析

  • 第23题：

    单选题
    在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是（）。
    A

    G中有弧

    B

    G中有一条从Vi到Vj的路径

    C

    G中没有弧

    D

    G中有一条从Vj到Vi的路径


    正确答案： D
    解析： 暂无解析

相关内容