《数据结构》习题汇编07第七章图试题.pdf

《数据结构》习题汇编07第七章图试题--第1页

第七章图试题

一、单项选择题

1.在无向图中定义顶点的度为与它相关联的（）的数目。

A.顶点B.边C.权D.权值

2.在无向图中定义顶点v与v之间的路径为从v到达v的一个（）。

ijij

A.顶点序列B.边序列C.权值总和D.边的条数

3.图的简单路径是指（）不重复的路径。

A.权值B.顶点C.边D.边与顶点均

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

A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)

5.n个顶点的连通图至少有（）条边。

A.n-1B.nC.n+1D.0

6.在一个无向图中，所有顶点的度数之和等于所有边数的()倍。

A.3B.2C.1D.1/2

7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个()。

A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵

8.图的深度优先搜索类似于树的（）次序遍历。

A.先根B.中根C.后根D.层次

9.图的广度优先搜索类似于树的（）次序遍历。

A.先根B.中根C.后根D.层次

10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助

结构，判断一条边的两个端点是否在同一个连通分量上。

A.位向量B.堆C.并查集D.生成树顶点集合

11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该

边不能在图中构成（）。

A.重边B.有向环C.回路D.权值重复的边

12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是

（）。

A.非零B.非整C.非负D.非正

13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件

是它至少有（）子女。

《数据结构》习题汇编07第七章图试题--第1页

《数据结构》习题汇编07第七章图试题--第2页

A.1B.2C.3D.0

14.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算

时间为（）。

2

A.O(nloge)B.O(n+e)C.O(ne)