(9)--数据结构第七章课后作业.pdf

学院:______________专业:_____________学号:_____________班级:________姓名:___________

第七章图

一、单选题

1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A．1/2B．1C．2D．4

2、有8个结点的无向连通图最少有条边。

A．5B．6C．7D．8

3、有8个结点的有向完全图有条边。

A．14B．28C．56D．112

4、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A．栈B．队列C．树D．图

5、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某

个顶点出度的时间复杂度为。

2

A．O(n)B．O(e)C．O(n+e)D．O(n)

6、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列

是。

A．0243156B．0136542

C．0134256D．0361542

7、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列

是。

A．0243651B．0123456

C．0423156D．0134256

08、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列

是。

A．0132B．0231C．0321D．0123

09、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列

是。

A．0321B．0123C．0132D．0312

10、图的广度优先遍历类似于二叉树的。

学院:______________专业:_____________学号:_____________班级:________姓名:___________

A．先序遍历B．中序遍历C．后序遍历D．层次遍历

11、任何一个无向连通图的最小生成树。

A．只有一棵B．一棵或多棵C．一定有多棵D．可能不存在

12、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，

所有边链表中边结点的总数为。

A．n、2eB．n、eC．n、n+eD．2n、2e

13、判断有向图是否存在回路，可以利用算法。

A．关键路径B．最短路径的DijkstraC．拓扑排序D．广度优先遍历

14、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。

A．图中每个顶点的入度