itgle.com

对于下面的有向图，其邻接矩阵是一个（41）的矩阵, 采用邻接链表存储时，顶点0的表结点个数为 2，顶点3的表结点个数为0，顶点1的表结点个数为（42）。 A.0 B.1 C.2 D.3

题目
对于下面的有向图，其邻接矩阵是一个（41）的矩阵, 采用邻接链表存储时，顶点0的表结点个数为 2，顶点3的表结点个数为0，顶点1的表结点个数为（42）。

A.0
B.1
C.2
D.3
相似考题

1.对于一个有向图,若一个顶点的入度为k1,、出度为k2,则对应逆邻接表中该顶点单链表中的结点数为()。A、k1B、k2C、k1-k2D、k1+k2

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

3.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为( )。A、 2*nB、 2*eC、 nD、 e

4.在n个顶点和e条边的无向图的邻接表中,边结点的个数为()。A.nB.n*eC.eD.2*e

更多“对于下面的有向图，其邻接矩阵是一个（41）的矩阵, 采用邻接链表存储时，顶点0的表结点个数为 2，顶点3的表结点个数为0，顶点1的表结点个数为（42）。 ”相关问题

  • 第1题：

    对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为(20)，所有边链表中边结点的总数为(21)。

    A．n

    B．n+1

    C．n-1

    D．n+e


    正确答案：A
    解析：此题考的是无向图。

  • 第2题：

    下面关于图的存储的叙述中正确的是()。

    A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关

    B.用邻接表法存储图，占用的存储空间大小与图中边数和顶点个数都有关

    C.用邻接矩阵法存储图，占用的存储空间大小与图中顶点个数和边数无关

    D.用邻接矩阵存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关


    正确答案：B

  • 第3题：

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

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


    正确答案：C

  • 第4题：

    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为()。

    A.e，n
    B.n.e
    C.2n，e
    D.n.2e

    答案：D
    解析：
    使用邻接表存储图，图有多少结点，邻接表就有多少个表头，无向图的表结点个数为2e。

  • 第5题：

    对于下面的有向图，其邻接矩阵是一个（ ）的矩阵。采用邻接链表存储时，顶点0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为（请作答此空）。

    A.0
    B.1
    C.2
    D.3

    答案：C
    解析：
    本题考查数据结构邻接矩阵的基础知识。邻接矩阵：表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。因此有向图有7个结点，则是一个7×7 的矩阵。顶点1分别可以指向2和5，所以表的结点个数为2。第一空正确答案为：D，第二空正确答案为：C

  • 第6题：

    对于如下所示的有向图，其邻接矩阵是一个（ ）的矩阵，采用邻接链表存储时顶点的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为（请作答此空）

    A.2.1
    B.2.2
    C.3.4
    D.4.3

    答案：B
    解析：
    如果是采用邻接表的方式存储，那么对于顶点V0来说，结点个数是2。

    同理，题干是5个结点的有向图若采用邻接矩阵存储是一个5*5 的矩阵，若采用邻接表的方式存储，顶点2和3的表结点个数分别为2、2。

  • 第7题：

    在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有（）和（）结点。


    正确答案:出边；入边

  • 第8题：

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


    正确答案:度数；出度数

  • 第9题：

    在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。

    • A、出边数
    • B、入边数
    • C、度数
    • D、度数减1

    正确答案:A

  • 第10题：

    单选题
    在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。
    A

    出边数

    B

    入边数

    C

    度数

    D

    度数减1


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

  • 第11题：

    单选题
    对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）。
    A

    k1

    B

    k2

    C

    k1-k2

    D

    k1+k2


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

  • 第12题：

    填空题
    对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为（）和（）

    正确答案： 2e,e
    解析： 暂无解析

  • 第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题：

    采用邻接链表存储时，顶点0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为（）。

    A.0

    B.1

    C.2

    D.3


    正确答案：C

  • 第15题：

    对于下面的有向图，其邻接矩阵是一个（41）的矩阵, 采用邻接链表存储时，顶点0的表结点个数为 2，顶点3的表结点个数为0，顶点1的表结点个数为（42）。

    A.3X4
    B.4X3
    C.6X6
    D.7X7

    答案：D
    解析：

  • 第16题：

    下面关于图的存储的叙述中，正确的是()。

    A.用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
    B.用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
    C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
    D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

    答案：A
    解析：
    对于n个节点的图来说，用邻接矩阵法存储图，需要n×n个存储单元，只与图中结点个数有关，与边数无关；用邻接表法存储图，与图的结点个数和边数都有关。

  • 第17题：

    对于下面的有向图，其邻接矩阵是一个（请作答此空）的矩阵。采用邻接链表存储时，顶点0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为（ ）。

    A.3×4
    B.4×3
    C.6×6
    D.7×7

    答案：C
    解析：
    本题考查数据结构邻接矩阵的基础知识。邻接矩阵：表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。因此有向图有7个结点，则是一个7×7 的矩阵。顶点1分别可以指向2和5，所以表的结点个数为2。第一空正确答案为：D，第二空正确答案为：C

  • 第18题：

    对于如下所示的有向图，其邻接矩阵是一个（请作答此空）的矩阵，采用邻接链表存储时顶点的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为（ ）

    A.5*5
    B.5*7
    C.7*5
    D.7*7

    答案：A
    解析：
    有向图的邻接矩阵如下。可以看出有4个结点的邻接矩阵是一个4*4 的矩阵。

    同理，题干是5个结点的有向图若采用邻接矩阵存储是一个5*5 的矩阵

  • 第19题：

    在无向图的邻接矩阵存储结构中，第i列上非零元素的个数是顶点vi的（），而在有向图的邻接矩阵中，第i列上非零元素的个数是顶点vi的（）


    正确答案:度；入度

  • 第20题：

    对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为（）和（）


    正确答案:2e；e

  • 第21题：

    单选题
    对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（）。
    A

     k1

    B

     k2

    C

     k1-k2

    D

     k1+k2


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

  • 第22题：

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

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

  • 第23题：

    单选题
    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）
    A

    n，e

    B

    e，n

    C

    2n，e

    D

    n，2e


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

相关内容