二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（    ）【青岛大学 2001 四、1 （1分）】
2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（   ）【中科院软件所1997一、4(1分）】 
3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e= 。（    ）
【南京航空航天大学 1996 六、4 （1分）】
4. 有e条边的无向图，在邻接表中有e个结点。（    ）【南京理工大学 1998 二、5 （2分）】
5. 有向图中顶点v的度等于其邻接矩阵中第v行中的1的个数。（   ）【合肥工业大学2001二、7(1分）】
6．强连通图的各顶点间均可达。（    ）【北京邮电大学 2000 一、3 （1分）】
7．强连通分量是无向图的极大强连通子图。（    ）【北京邮电大学 2002 一、7 （1分）】
8．连通分量指的是有向图中的极大连通子图。（    ）【燕山大学 1998  二、4 （2分）】
9．邻接多重表是无向图和有向图的链式存储结构。（    ）【南京航空航天大学 1995 五、5 （1分）】
10. 十字链表是无向图的一种存储结构。（    ）【青岛大学 2001 四、7 （1分）】
11. 无向图的邻接矩阵可用一维数组存储。（    ）【青岛大学 2000 四、5 （1分）】
12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（    ）
【东南大学 2001 一、4 （1分）】 【中山大学 1994 一、3 （2分）】
13．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（    ）
【北京邮电大学 1998 一、5 （2分）】
14. 有向图的邻接矩阵是对称的。（    ）【青岛大学 2001 四、6 （1分）】
15．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（    ）
【东南大学 2001 一、3 （1分）】【哈尔滨工业大学 1999 三、4】
16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（    ）【上海海运学院 1995 一、9（1分） 1997 一、8（1分） 1998 一、9（1分）】 
17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（    ）【上海海运学院 1996 一、8 （1分） 1999 一、9 （1分）】
18．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（    ）【上海交通大学 1998 一、12】
19．需要借助于一个队列来实现dfs算法。（    ）【南京航空航天大学 1996 六、8 （1分）】                                
20. 广度遍历生成树描述了从起点到各顶点的最短路径。（    ）【合肥工业大学 2001 二、8 （1分）】
21．任何无向图都存在生成树。（    ）【北京邮电大学 2000 一、1 （1分）】
22. 不同的求最小生成树的方法最后得到的生成树是相同的.（    ）【南京理工大学 1998 二、3 （2分）】
23．带权无向图的最小生成树必是唯一的。（    ）【南京航空航天大学 1996 六、7 （1分）】
24. 最小代价生成树是唯一的。（    ）【山东大学 2001 一、5 （1分）】
25．一个网（带权图）都有唯一的最小生成树。（    ）【大连海事大学 2001 一、14 （1分）】
26．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（    ）【哈尔滨工业大学 1999 三、3】
27．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（   ）【中山大学 1994 一、10（2分）】
28. 最小生成树的kruskal算法是一种贪心法（greedy）。（    ）【华南理工大学 2002 一、6（1分）】
29. 求最小生成树的普里姆(prim)算法中边上的权可正可负。（    ）【南京理工大学 1998 二、2 （2分）】
30．带权的连通无向图的最小代价生成树是唯一的。（    ）【东南大学 2001 一、5（1分）】
31. 最小生成树问题是构造连通网的最小代价生成树。（    ）【青岛大学 2001 四、10（1分）】
32. 在图g的最小生成树g1中，可能会有某条边的权值超过未选边的权值。（    ）
【合肥工业大学 2000 二、7（1分）】

上一页1234下一页