Question

高分求数据结构高手帮忙！

请帮忙做出下面的题目：
1．图中有关路径的定义是（
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是

2．设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
3．一个n个顶点的连通无向图，其边的个数至少为（ ）
A．n-1 B．n C．n+1 D．nlogn；

5．n个结点的完全有向图含有边的数目（ ）
A．n*n B．n（n＋1） C．n／2 D．n*（n－l）

7．在一个无向图中，所有顶点的度数之和等于所有边数（ 2）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ 1 ）倍
A．1/2 B．2 C．1 D．4

11．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网

15. 下列说法不正确的是（ ）
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程

25．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（ ）。
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
27．一个有向无环图的拓扑排序序列（ ）是唯一的。
A．一定 B．不一定
30. 关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
31. 下面关于求关键路径的说法不正确的是（ ）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
二、判断题
23．带权无向图的最小生成树必是唯一的。（ ）【南京航空航天大学 1996 六、7 （1分）】

25．一个网（带权图）都有唯一的最小生成树。（ ）【大连海事大学 2001 一、14 （1分）】
26．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
三、填空题
1.判断一个无向图是一棵树的条件是__任意两个顶点之间有且仅有一条路径____。
2．有向图G的强连通分量是指______。【北京科技大学 1997 一、7】
3．一个连通图的______是一个极小连通子图。【重庆大学 2000 一、1】
4．具有10个顶点的无向图，边的总数最多为______。【华中理工大学 2000 一、7 （1分）】
10．设G为具有N个顶点的无向连通图，则G中至少有__N-1____条边。
【长沙铁道学院 1997 二、2 (2分)】
13．N个顶点的连通图的生成树含有______条边。【中山大学 1998 一、9 （1分）】
22. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。

26．构造连通网最小生成树的两个典型算法是______。
28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树

**************************************
做得好的再追加分！
**************************************

Answer 1

ABAD
11.B 15 C 25 A 27 B 28 A 31 C

××√

1.有无环路 最短
2.有向图中的极大强连通子图
3.生成树
4.45
13.N-1
22.深度优先
26.Prim（普里姆 kruskal（克鲁斯卡尔
28.边稠密 边稀疏
除了判断题记不大清 ，其他应该都对！