发布时间 : 星期一 文章数据结构精品课程习题更新完毕开始阅读
2、最小生成树的构造可使用（ ）算法。
A.prim算法 B.卡尔算法 C.迪杰斯特拉算法 D.哈夫曼算法 3、生成树的构造方法只有（ ）。
A.深度优先 B.深度优先或广度优先 C.无前驱的顶点优先 D.无后继的顶点优先 4、若图G中（ ）都没有方向，则称G为无向图。
A.每条边 B.部分边 C.一条边 D.个顶点 5、若图G中（ ）都有方向，则称G为无向图。
A.每条边 B.部分边 C.一条边 D.个顶点 6、下列表示方法中，（ ）是有向图的边的表示方法。
A.（1，2） B.（1，2> C.<（1,2） D.<1,2>
7、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A.完全图 B.连通图 C.有回路 D.一棵树 8、无向图的邻接矩阵是一个（ ）。
A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角距阵 9、连通分量是（ ）的极大连通子图。
A.无向图 B.有向图 C.树 D.图 10、强连通分量是（ ）的极大强连通子图。
A.无向图 B.有向图 C.树 D.图 11、有N个顶点的无向图的邻接矩阵是用（ ）数组存储。
A.N行N列 B.一维 C.任意行N列 D.N行任意列 12、有N个顶点的有向图的邻接矩阵是用（ ）数组存储。
A.N行N列 B.一维 C.任意行N列 D.N行任意列 13、下列说法中正确的是（ ）。
A.一个个有n个顶点的无向完全图的边数为n（n-1） B.连通图的生成树是该图的一个极大连通子图 C.图的广度优先搜索是一个递归过程
D.对于非连接通图的遍历过程中的每调用一次深度优先搜索算法都得到该
41
图的一个连通分量
14、用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为（ ）。
A.0(n) B.0(n+e) C.0(e) D.0(n*e)
15、有N条边的有向图的邻接矩阵存储法中，链表中结点的个数是（ ）个。
A.N B.2N C.N/2 D.N*N 16、一个带树的无向连通图的最小生成树（ ）。
A.有一棵或多棵 B.只有一棵 C.一定有多棵 D.可能不存在 17、一列图中：
（1）度为3的结点是（ ）。
A.V1 B.V2 C.V3 D.V4 （2）该图是（ ）。
A.连通图 B.强连通图 C.生成树 D.无环图 18、某图的邻接表如下：
0 V1 1 V2 2 V3 3 V4 4 V5 5 V6 6 V7 7 V8 Nu11 Nu11 2 0 0 6 5 5 Nu11 Nu11 3 7 7 6 Nu11 Nu1 Nu11 Nu11 （1）从V1顶点进行深度优先搜索，搜索中要经过的顺序是（ ）。
A.V1、V2、V3 B.V1、V3、V4 C.V1、V2、V4 D.V1、V3、V5
（2）从V1顶点进行广度优先搜索，搜索中要经过的顺序是（ ）。
A.V1、V2、V3 B.V1、V3、V4
42
C.V1、V2、V4 D.V1、V3、V5 19、下列有关图遍历的说法中不正确的是（ ）。
A.连通图深度优先搜索是个递归过程
B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C.非连通图不能用深度忧先搜索法 D.图的遍历要求每一顶点仅被防问一次 20、拓扑排序的图中（ ）表示活动。
A.顶点 B.边 C.图 D.边或顶点 21、有拓朴排序的图，一定是（ ）。
A.有圈图 B.无圈图任意图 C.无向 D.无圈强连通图 二、填空题
1、在下列有向图中：
（1）该图是强连通图吗？ 。若不是，则给出其强连通分量。 （2）请给出两个有向环： 、 。 （3）请给出每个顶点的入度和出度。
2、对n个顶点的无向图，采用邻接矩阵表示时，如何判别下列有关问题： （1）图中有 条边？
（2）任意两个顶点i和j是否有边相连？ （3）任意一个顶点的度是 。 （4）n个顶点的连通图至少有 条边。
3、一个个有n个顶点的有向完全的弧数为 。 4、若图G中每条边都 方向，则称为G为无向图。 5、若图G中的每条边都 方向，则称G为有向图。
43
6、无向图中的连通分量定义为无向图的 。 7、有向图边的起始点称为 。 8、有向图边的终点称为 。
9、设无向图G的顶点数为n，则C最少有 条边。 10、无向图G的 子图称为G的连通分量。 11、有向图的极大强连通子图称为 。
12、图的邻接矩阵表示法是表示 之间相邻关系的矩阵。
13、无向图的邻接矩阵表示法中，i行j列为1，则表示Vi和Vj两点之间 。
14、有N条边的无向图的邻接矩阵中，有 个1。 15、有N条边的有向图的邻接矩阵中，有 个1。 16、有N条边的无向图的邻接表中，链表共有 个结点。 17、有N条边的有向图的邻接表中，链表共有 个结点。 18、图的遍历有 两种方法。
19、一个图的生成树的顶点是图的 顶点。 20、一个图的生成树的枝是图的 边。 三、应用题
1、已知无向图G的邻接矩阵如下，假设对其每行元素访问时必段从右到左，请写出从V0开始的深度优先搜索的序列。
2、已知无向图G的邻接矩阵如下。假设对其访问时每行元素必须从右到左，请画出其所有的连通分量，并且写出按深度优先搜索时各连通分量的访问序列。
3、假设一幅完全图包含A，B，C，D四个结点，画出其邻接表。
4、按第3题的邻接表写出从A点出发进行广度优先搜索和深度优先搜索的序列。
44