考研类计算机专业图

1、2.n个顶点的连通无向图,其边的条数至少为.哈尔滨工业大学 2000二21 分分数:2.003.如果具有 n个顶点的图是一个环,则它有棵生成树.中南大学 2005二92 分分数:2.004.N个顶点的连通图的生成树含有条边.中山大学 199。

2、2.1对于有向无环图,叙述求拓扑有序序列的步骤;2对于以下的图,写出它的四个不同的拓扑有序序列.南开大学 1998二12 分 分数:2.003.有向图的拓扑排序能否用图的深度搜索模式来查找若能,请简述方法;若不能,请简述原因.西北大学 20。

3、V,E中含有 7个顶点,要保证图 G在任何情况下都是连通的,则需要的边数最少是 .2010 年全国试题 72分分数:2.00A.6B.15C.16D.213.对下图进行拓扑排序,可以得到不同拓扑序列的个数是 .2010 年全国试题 82分 。

4、技大学 2007 一112 分分数:2.00A.8B.9C.10D.113.n 个结点的完全有向图含有边的数目 .中山大学 1998 二92 分分数:2.00A.n nB.nn1C.n2D.n n14.一个有 n 个结点的图,最少有 个连通。

5、 分数:4.001.画出 G的邻接表表示图;分数:2.002.根据你画出的邻接表,以顶点为根,画出 G的深度优先生成树和广度优先生成树.南开大学1997五14 分烟台大学 2007四315 分分数:2.002.已知一个有向图如图所示,则从顶。

6、广度优先遍历算法类似于树的 .北京交通大学 2007分数:2.00A.中序遍B.先序遍历C.后序遍D.按层次遍历3.执行 操作时,需要使用队列作辅助存储空间.华中科技大学 2006一12 分分数:2.00A.查找哈希Hash表B.广度优先搜。

7、2.求图的最小生成树有两种算法,算法适合于求稀疏图的最小生成树.南京理工大学 2001二62 分北京交通大学 2005二72 分分数:2.003.Prim普里姆算法适用于求的网的最小生成树;Kruskal克鲁斯卡尔算法适用于求的网的最小生成。

8、华南理工大学 2007分数:2.00A.邮电图B.AOV网C.公路网D.AOE网3.关键路径是 AOE网中 .中南大学 2003一101 分分数:2.00A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径。

9、2.下列函数是在无向图的邻接表中删除一条边的算法,请完善该程序. V0id deledgeALGraphG,int i, int j EdgeNodep,q; pG 一adj listifirstedge; iffG 一adjlistifi。

10、试问该算法是哪一种求最小生成树的算法 APrim普里姆算法B Kruskal克鲁斯卡尔算法C罗巴赫算法D其他算法2 邻接表是图的一种 .A顺序存储结构B链接存储结构C索引存储结构D散列存储结构3 下面试图对图中路径进行定义,说法正确的是 。

11、 A.5 B.6 C.7 D.8分数:1.00A.B.C.D.3.下列关于无向连通图特性的叙述中,正确的是.所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1 A.只有 B.只有 C.和 D.和分数:1.00A.B.C.D。

12、的算法 A.Prim普里姆算法 B.Kruskal克鲁斯卡尔算法 C.罗巴赫算法 D.其他算法分数:1.00A.B.C.D.2.邻接表是图的一种. A.顺序存储结构 B.链接存储结构 C.索引存储结构 D.散列存储结构分数:1.00A.B。

13、数目U U. A.nn B.nn1 C.n2 D.nn1分数:2.00A.B.C.D.3.在图采用邻接表存储时,求最小生成树的 Prim算法的时间复杂度为U U. A.On B.One C.On2 D.On3分数:2.00A.B.C.D.4。

14、2.下面是一个求最小生成树的算法,其中 G是连通无向图,T 是所求的生成树. T:G: While T 中存在回路 do begin在 T中找一条权值最大的边 e; T:T 一e; T 中去掉 e边 EnD 试问该算法是哪一种求最小生成树的。

15、一条从 vj 到 vi 的路径2 以下关于图的说法中正确的是 .I一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩阵存储图,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定。

16、法是哪一种求最小生成树的算法 APrim普里姆算法B Kruskal克鲁斯卡尔算法C罗巴赫算法D其他算法2 邻接表是图的一种 .A顺序存储结构B链接存储结构C索引存储结构D散列存储结构3 下面试图对图中路径进行定义,说法正确的是 .A由顶点。

17、法是哪一种求最小生成树的算法 APrim普里姆算法B Kruskal克鲁斯卡尔算法C罗巴赫算法D其他算法2 邻接表是图的一种 .A顺序存储结构B链接存储结构C索引存储结构D散列存储结构3 下面试图对图中路径进行定义,说法正确的是 .A由顶点。

18、 到 vi 的路径2 以下关于图的说法中正确的是 .一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩阵存储图,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的A。

19、2.在有向图 G 的拓扑序列中,若顶点 v i 在顶点 v j 之前,则下列情形不可能出现的是 .分数:2.00A.G 中有弧 i,v hB.G 中有一条从 v i 到 v j 的路径C.G 中没有弧 i,v jD.G 中有一条从 v j 。

20、2.下面是一个求最小生成树的算法,其中 G 是连通无向图,T 是所求的生成树. T:G: While T 中存在回路 do begin 在 T 中找一条权值最大的边 e; T:T 一e; T 中去掉 e 边 EnD 试问该算法是哪一种求最小。