1.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个
( )。
A. 上三角矩阵 C. 对角矩阵
B. 稀疏矩阵 D. 对称矩阵
2.有n个顶点的无向连通图中最少有 n-1 条边，最多有 n(n-1)/2 条边。
3.在有n个顶点的有向图的邻接表中顶点I的入度为 顶点I在所有邻接点单链表中出现的次数 ，顶点I的出度为 顶点I的邻接点单链表中结点的个数 。
4.有n个顶点的强连通图中最少有 n 条边，最多有 n(n-1) 条边。 5.在有n个顶点的有向图的邻接矩阵中顶点I的入度为 第I列1的个数 ，最顶点I的出度为 第I行1的个数 。
6.对AOV网进行拓扑排序，则其拓扑排序序列一定包含图中的所有顶点。（错） 7.Prim（普里姆）算法适用于求__稠密性____网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求__稀疏性_____网的最小生成树。
8.具有10个顶点的无向图，边的总数最多为 45_ ，最少为 0 。 9.G是一个非连通无向图，共有28条边，则该图至少有__8__个顶点。 10.n个顶点的强连通图至多有( )条边
A) 2（n-1） B)n（n-1）
C)n－1 D)2n(n-1)
11.在一个有向图中，所有顶点入度之和等于所有顶点出度之和的( )倍
A)1/2
B) 1
C) 2
D) 4
12.下列关于无向连通图特性的叙述中，正确的是：
Ⅰ.所有顶点的度之和为偶数 Ⅱ.边数大于顶点数减1 Ⅲ.至少有一个顶点的度为1
A.只有Ⅰ B.只有Ⅱ C.Ⅰ和Ⅱ D.Ⅰ和Ⅲ 13.（ ）方法可以判断出一个有向图中是否有环(回路)。
A.深度优先遍历 B. 求关键路径 C.求最短路径 D. 拓扑排序 14.下列有关图遍历的说法中不正确的是( )。 A.连通图的深度优先搜索是一个递归过程
B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C.非连通图不能用深度优先搜索法 D.图的遍历要求每一顶点仅被访问一次
15.在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍，在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的 1 倍。 16.一个带权的无向连通图的最小生成树（ ）
A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在
17.具有n个顶点的无向图G最少应该有 n-1 条边才能确保是一个连通图。 18.带权有向图G用邻接矩阵A[][]存储，则顶点i的入度等于A中________。 A．第i行非∞的元素之和 B．第i行非∞的元素个数 C．第i列非∞的元素之和 D．第i列非∞的元素个数 19.图的广度优先遍历类似于二叉树的 按层次 遍历。 20.已知一个图如下，则由该图得到的一种拓扑序列为（ ）。 A、1,4,6,2,5,3 B、1,2,3,4,5,6 C、1,4,2,3,6,5 D、1,2,4,6,3,5
21.已知一有向图的邻接表存储结构如下图所示，根据图的深度优先搜索遍历算法，从顶点v1出发，得到的顶点序列为（ ）。 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2
22.若无向图中度为1的顶点有3个, 度为2的顶点有4个, 度为3的顶点有3个, 度为4的顶点有1个, 则该无向图有__12___条边。
23.某无向图的邻接表如下图所示, 从A开始深度优先搜索遍历所得到的结点序列为__AEDCB 。从B开始广度优先搜索遍历所得到的结点序列为 BCADE 。
0 A 1 B 2 C 3 D 4 E 4 2 3 4 3 3 0 ^ 1 ^ 2 0 ^ 0 ^ 1 ^
24.图的邻接矩阵表示法适用于表示( ) A．无向图 C．稠密图
B．有向图 D．稀疏图
25.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中___边_____的数目正相关。
26.将1-N排成一个圈，使任意相邻两个数之和为素数。N为任意大于1的正整数；如有解，求出所有满足条件的解以及解的个数
当N=5时，没有解
当N=6时，有2组满足条件的解：1 4 3 2 5 6 1 6 5 2 3 4 当N=7时，没有解
当N=8时，有4组满足条件的解：
1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2
因篇幅问题不能全部显示，请点此查看更多更全内容