数据结构图测试题

第1题

设无向图的顶点个数为n，则该图最多有（ ）条边。

第2题

在一个无向图中，所有顶点的度数之和等于所有边数2倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 

第3题

下列哪一种图的邻接矩阵是对称矩阵？（ ）

第4题

从邻接矩阵  可以看出，该图共有（ ）个顶点。

第5题

2题中的邻接矩阵A，如果是有向图，该图共有（ ）条弧。

第6题

2题中的邻接矩阵A，如果是无向图，该图共有（ ）条边。

第7题

下列说法不正确的是（ ）

第8题

无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图从a出发进行深度优先遍历，得到的顶点序列正确的是（ ）

第9题

对题11中的无向图G=(V,E)从a出发进行广度优先遍历，得到的顶点序列正确的是（ ）

第10题

在无向图G的邻接表表示中，每个顶点的邻接点建立一个单链表，称之为结点的邻接表，邻接表中所含的结点数等于该顶点的（ ）

第11题

在有向图G的邻接表表示中，每个顶点的邻接点建立一个单链表，称之为结点的邻接表，邻接表中所含的结点数等于该顶点的（ ）

第12题

在图采用邻接矩阵存储时，Prim 算法的时间复杂度为（ ）

第13题

求解Floyd算法的时间复杂度为（ ）

第14题

任何一个无向连通图的最小生成树（ ）

第15题

构造连通网最小生成树的两个典型算法是（ ）

第16题

树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）

第17题

在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ）

第18题

有e条边的无向图，在邻接表中有e个结点。（ ）

第19题

强连通图的各顶点间均可达。（ ）

第20题

用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ）

第21题

有向图G的强连通分量是指有向图的极大强连通子图。（ ）

第22题

在有向图的邻接矩阵表示中，第I个顶点入度就是第I列非零元素个数。（ ）

第23题

邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ ）

第24题

为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需使用队列存放被访问的结点以实现遍历。（ ）

第25题

只有连通无向图存在生成树，不连通的图存在生成森林。（ ）

第26题

Prim（普里姆）算法适用于求边稀疏的网的最小生成树。（ ）

第27题

连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）

第28题

Dijkstra算法是用来求从源点到其余各顶点的最短路径的，该算法是按路径长度递增次序依次产生的。（ ）

第29题

判断一个有n个顶点的无向图是一棵树的条件是有n-1条边。（ ）

第30题

对于一个具有n个顶点e条弧的有向图，用逆邻接表存储，方便获取顶点的入度。（ ）

第31题

可以利用图的遍历过程来判断一个图是否连通，并可得到其连通分量。如果在遍历的过程中，不止一次调用遍历过程，则说明该图是一个非连通图。调用遍历过程的次数就是该图连通分量的个数。（ ）