数据结构习题11级用(12)

A． 出发点不同、遍历方法不同 B． 出发点不同、存储结构不同 C． 遍历方法不同、存储结构不同

D． 出发点不同、存储结构不同、遍历方法不同 17．已知某有向图

（ ）。

A． V3,V1,V4,V5,V2,V6 B． V3,V4,V1,V5,V2,V6 C． V1,V3,V4,V5,V2,V6 D． V1,V4,V3,V5,V2,V6

18. 若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻

接矩阵必定为（ ）。

A． 对称矩阵 B． 稀疏矩阵 C． 三角矩阵 D． 一般矩阵

二、填空题

1．图的主要存储结构有两种，分别为 和 。 2．对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为 。

3.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 。

34

G=(V,E),其中V={V1,V2,V3,V4,V5,V6}, E={,

,,,,,,}, G的拓扑序列是

4．已知无向图的结点个数为n，边的个数为e，则在其邻接表的存储结构中，表结点

与头结点共有 个。

5．若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的 ，它所用到的

数据结构为 。

6．若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的 ，它所用到的

数据结构为 。

7. G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的

每个顶点，则该图一定是 图。 8 n个顶点的连通图的生成树有 条边。 9. AOV-网以结点和有向边分别代表 。 10. AOE-网以结点和有向边分别代表 。

三、基础知识题

1．有如下数据结构的形式定义，试画出此结构的图形表示。 DS={D, S}, 其中：D={1, 2, 3, 4}, S={R},

R={<1,2>,<1,3>,<2,3>,<2,4>,<3,4>}。 2．已知如下图所示的有向图，请给出该图的 （1）每个顶点的入/出度； （2）邻接矩阵； （3）邻接表。

3．什么是无向图的连通分量和生成树？

4．如果含n个顶点的图形成一个环，则它有多少棵生成树？

5．对于n顶点的无向图G，采用邻接矩阵A表示，如何判断下列问题： (1) 图中有多少条边？

(2) 任意两个顶点i和j是否有边相连？

35

(3) 任意一个顶点的度是多少？

6．求网的最小生成树有哪些算法？各适用于何种情况？为什么？

7．给出下列无向图的邻接表存储结构，并由邻接表写出由E出发的广度优先搜索序

列和深度优先搜索序列。

8．下图为一无向连通网络，分别根据普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法从顶点１出发构造出它的最小生成树。

9. 对如下带权图，请： (1) 给出结点的一个拓扑序列；（2）找出一条从v1 到v7

的最短路径（要求写出求解步骤）。

36

10．对下图所示的AOE网络，给出其关键路径。

四、算法设计题

1．编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建

立有向图的邻接表。

2. 假设图采用邻接表存储，编写利用深度优先搜索方法和广度优先搜索方法遍历图

的算法。

3．试基于图的深度优先搜索方法和广度优先搜索方法编写算法，判断以邻接表方式

存储的有向图中是否存在由顶点到顶点vj的路径(i≠j)。

4．采用邻接表存储结构，编写一个判断无向图中任意给定的两各顶点之间是否存在

一条长度为k的简单路径的算法。

37