)条边.
A、n(n+1)/2
C、n
D、n(n-1)
2、有向图中一个顶点i的出度等于其邻接矩阵中第i列的非零元素的个数(
)
3、有向图中一个顶点i的入度等于其邻接矩阵中第i列的非零元素的个数(
)
4、一个具有n个顶点的连通有向图至多有_________条弧.
5、一个具有n个顶点的连通有向图至少有________条弧.
6、已知图G如下:
求(1) 图G的邻接矩阵
(2) 图G的最小生成树
7、网是带_
__的图
8、连通图G的生成树是G的极小连通子图(
9、连通网络的最小生成树是唯一的(
)
10、连通图是有向图(
)
11、连通图的邻接矩阵是对称的,有向图的邻接矩阵是不对称的(
)
12、有n个顶点,n-1条边的图一定是生成树(
13、已知图G的邻接矩阵为
│0
1
0
1│
│0
0
1
1│
│1
0
1
0│
│0
1
1
0│
问(1)该图是有向图还是无向图?为什么?
(2)各结点的度是多少?
14、已知某有向图的邻接表如下:
求出每个顶点的入度和出度.
15、图的常用存储结构有________和________.
16、图的遍历方法一般有________和_________两种.
17、何为子图?
18、何为连通图?
19、树是一种特殊形式的图(
20、 从邻接矩阵│0 1
0│可以看出,该图共有____个顶点,
│1 0 1│
│0 1 0│
如果是有向图,该图共有___条弧;如果是无向图则共有____条边.
21、有向图中,所有的顶点的入度之和与出度之和的关系_________
22、无向图G是连通的无回路图,有且仅有_______条边.
23、何为网络?
24、已知如下图所示的有向图,请给出该图的
(1) 每个顶点的入度/出度
(2)邻接表
25、试利用dijkstra算法求右图中从顶点a到其它各顶点间的最短路径长度,写出执行算法过程中各步的状态.
26、试给出以邻接矩阵表示无向图的深度优先搜索算法
27、试给出此邻接表表示有向图的广度优先搜索算法
28、设有无向图G,从顶点V1出发,对它进行深度优先遍历得到的顶点序列是______;而进行广度优先遍历得到的顶点序列是_____.
29、在一个图中，所有顶点的度数之和等于图的边数的(
)倍。
A、1/2
B、 1
C、 2
D、
4
30、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(
)倍。
A、1/2
1
C、 2
D、 4
31、有8个结点的无向图最多有(
)条边。
A、14
B、 28
C、
56
D、 112
32、有8个结点的无向连通图最少有(
)条边。
A、5
B、 6
C、 7
D、
8
33、有8个结点的有向完全图有(
)条边。
A、14
B、 28
C、 56
D、
112
34、用邻接表表示图进行广度优先遍历时，通常是采用(
)来实现算法的。
A、栈
B、队列
C、 树
D、
图
35、用邻接表表示图进行深度优先遍历时，通常是采用(
)来实现算法的。
A、栈
B、队列
C、 树
D、 图
36、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是(
)
37、已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是(
)
38、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是(
)
39、深度优先遍历类似于二叉树的(
)
A、先序遍历
B、中序遍历
C、 后序遍历
D、 层次遍历
40、广度优先遍历类似于二叉树的(
)
A、先序遍历
B、
中序遍历
C、后序遍历
D、层次遍历