国开放大学数据结构(本科)单元7图-单元测试题含答案

第第页国开放大学数据结构(本科)单元7图单元测试题含答案试题

1在一个图G中，所有顶点的度数之和等于所有边数之和的（

）倍。选择一项：A.4B.1/2C.2D.1反馈正确答案是：2试题

2邻接表是图的一种（

）。选择一项：A.索引存储结构B.链式存储结构C.顺序存储结构D.散列存储结构反馈正确答案是：链式存储结构试题

3如果从无向图的任一顶点出发进行一次\o"深度优先搜索"深度优先搜索即可访问所有顶点，则该图一定是（

）。选择一项：A.完全图B.一棵树C.连通图D.有回路反馈正确答案是：连通图试题

4下列有关图遍历的说法不正确的是（

）。选择一项：A.连通图的\o"深度优先搜索"深度优先搜索是一个递归过程B.图的遍历要求每一顶点仅被访问一次C.非连通图不能用\o"深度优先搜索"深度优先搜索法D.图的\o"广度优先搜索"广度优先搜索中邻接点的寻找具有“先进先出”的特征反馈正确答案是：非连通图不能用\o"深度优先搜索"深度优先搜索法试题

5无向图的邻接矩阵是一个（

）。选择一项：A.对角矩阵B.上三角矩阵C.对称矩阵D.零矩阵反馈正确答案是：对称矩阵试题

6图的深度优先遍历算法类似于二叉树的（

）遍历。选择一项：A.后序B.层次C.中序D.先序反馈正确答案是：先序试题

7已知下图所示的一个图，若从顶点V1出发，按\o"深度优先搜索"深度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。选择一项：A.V1V2V4V5V8V3V6V7B.V1V2V4V8V3V5V6V7C.V1V2V4V8V5V3V6V7D.V1V3V6V7V2V4V5V8反馈正确答案是：V1V2V4V8V5V3V6V7试题

8已知如图2所示的一个图，若从顶点a出发，按\o"广度优先搜索"广度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。选择一项：A.abcefdB.aebcfdC.abcedfD.acfdeb反馈正确答案是：abcefd试题

9已知如图3所示的一个图，若从顶点a出发，按\o"深度优先搜索"深度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。选择一项：A.aebcfdB.aedfcbC.acfebdD.abecdf反馈正确答案是：aedfcb试题

10一个具有n个顶点的无向完全图包含（

）条边。选择一项：A.n（n+1）B.n（n-1）/2C.n（n-1）D.n（n+1）/2反馈正确答案是：n（n-1）/2试题

11已知如图4所示的一个图，若从顶点a出发，按\o"深度优先搜索"深度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。选择一项：A.aedfcbB.abecdfC.aebcfdD.acfebd反馈正确答案是：aedfcb试题

12已知如图5所示的一个图，若从顶点a出发，按\o"广度优先搜索"广度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。选择一项：A.abcefdB.abcedfC.aebcfdD.acfdeb反馈正确答案是：abcefd试题

13已知如图6所示的一个图，若从顶点V1出发，按\o"深度优先搜索"深度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。选择一项：A.V1V2V4V5V8V3V6V7B.V1V3V6V7V2V4V5V8C.V1V2V4V8V3V5V6V7D.V1V2V4V8V5V3V6V7反馈正确答案是：V1V2V4V8V5V3V6V7试题

14已知如图7所示的一个图，若从顶点V1出发，按深广优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。选择一项：A.V1V2V3V4V5V8V6V7B.V1V2V3V4V8V5V6V7C.V1V2V3V4V5V6V7V8D.V1V2V3V6V7V4V5V8反馈正确答案是：V1V2V3V4V5V6V7V8试题

15采用邻接表存储的图的\o"广度优先搜索"广度优先搜索遍历算法类似于二叉树的（

）。选择一项：A.中序遍历B.后续遍历C.先序遍历D.层次遍历反馈正确答案是：层次遍历试题

16下面结论中不正确的是（

）。选择一项：A.无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍B.按\o"广度优先搜索"广度优先搜索遍历时，与始点相邻的结点先于不与始点相邻的结点访问C.图的多重邻接表表示法中，表中结点的数目等于图中边的条数D.一个图按\o"广度优先搜索"广度优先搜索法遍历的结果是唯一的反馈正确答案是：一个图按\o"广度优先搜索"广度优先搜索法遍历的结果是唯一的试题

17下面说法不正确的是（

）。选择一项：A.图的深度遍历不适用于有向图B.图的深度遍历是一个递归过程C.遍历的基本算法有两种：深度遍历和广度遍历D.图的遍历是从给定的原点出发每一个顶点仅被访问一次反馈正确答案是：图的深度遍历不适用于有向图试题

18任何一棵无向连通图的最小生成树（

）。选择一项：A.有一棵或多棵B.只有一棵C.一定有多棵D.可能不存在反馈正确答案是：有一棵或多棵试题

19在一个具有n个顶点的无向图中，要连通全部顶点至少需要（

）边。选择一项：A.nB.n+