第1题
设无向图的顶点个数为n,则该图最多有( )条边。
n-1
n(n-1)/2
n(n+1)/2
0
n^2
第2题
在一个无向图中,所有顶点的度数之和等于所有边数2倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。
1/2
2
1
4
第3题
下列哪一种图的邻接矩阵是对称矩阵?( )
有向图
无向图
AOV网
AOE网
第4题
从邻接矩阵 可以看出,该图共有( )个顶点。
3
6
以上答案均不正确
第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出发进行深度优先遍历,得到的顶点序列正确的是( )
a,b,e,c,d,f
a,c,f,e,b,d
a,e,b,c,f,d
a,e,d,f,c,b
第9题
对题11中的无向图G=(V,E)从a出发进行广度优先遍历,得到的顶点序列正确的是( )
第10题
在无向图G的邻接表表示中,每个顶点的邻接点建立一个单链表,称之为结点的邻接表,邻接表中所含的结点数等于该顶点的( )
度数
依附的边数
出度
入度
第11题
在有向图G的邻接表表示中,每个顶点的邻接点建立一个单链表,称之为结点的邻接表,邻接表中所含的结点数等于该顶点的( )
第12题
在图采用邻接矩阵存储时,Prim 算法的时间复杂度为( )
O(n)
O(n+e)
O(n^2)
O(n^3)
第13题
求解Floyd算法的时间复杂度为( )
O(n)
O(n+c)
O(n*n)
O(n*n*n)
第14题
任何一个无向连通图的最小生成树( )
只有一棵
有一棵或多棵
一定有多棵
可能不存在
第15题
构造连通网最小生成树的两个典型算法是( )
Floyd算法和Prim 算法
Prim 算法和kruskal算法
Prim 算法和Dijkstra算法
Dijkstra算法和Prim 算法
第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题
可以利用图的遍历过程来判断一个图是否连通,并可得到其连通分量。如果在遍历的过程中,不止一次调用遍历过程,则说明该图是一个非连通图。调用遍历过程的次数就是该图连通分量的个数。( )
选择题(1 - 31题,共计100分)