[考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编4.doc

[考研类试卷]计算机专业基础综合数据结构（图）历年真题试卷汇编4

一、单项选择题

1 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为( )。【中国科学技术大学1997一、3(1分)2004】

（A）对称矩阵

（B）稀疏矩阵

（C）三角矩阵

（D）一般矩阵

2 采用邻接表存储的图的深度优先遍历算法类似于树的( )，而其广度优先遍历算法类似于树的( )。【北京交通大学2007】

（A）中序遍

（B）先序遍历

（C）后序遍

（D）按层次遍历

3 执行( )操作时，需要使用队列作辅助存储空间。【华中科技大学2006一、1(2分)】

（A）查找哈希(Hash)表

（B）广度优先搜索图

（C）先序(根)遍历二叉树

（D）深度优先搜索图

答案见麦多课文库

4 图的BFS生成树的树高比：DFS生成树的树高( )。【青岛大学2004一、8(3分)】

（A）小或相等

（B）小

（C）大或相等

（D）大

5 无向图G=(V,E)，其中：V={a，b，c，d,e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f,d)，(e，d))，对该图进行深度优先遍历，得到的顶点序列正确的是( )。【南京理工大学2001一、14(1．5分)】

（A）a，b，e，c，d,f

（B）a，c，f,e ，b，d

（C）a，e，b，c,f,d

（D）a，e，d,f, c，b

6 设图如下所示，在下面的5个序列中，符合深度优先遍历的序列有多少? ( )。

【南京理工大学2000一、20(1．5分)】df c b; a efd c b; a efd b c

（A）5个

（B）4个

a e b d f c ;a cf d e b; a e

答案见麦多课文库

（C）3个

（D）2个

6 下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(①)，而进行广度优先遍历得到的顶点序列是(②)。【中科院软件所

1999六、2(1)(2分)】 7 ①

（A）1354267

（B）1347652

（C）1534276

（D）1247653

（E）以上答案均不正确 8 ②

（A）1 534267

（B）1 726453

（C）1 354276

（D）1 247653

（E）以上答案均不正确

答案见麦多课文库

9 下面哪一方法可以判断出一个有向图是否有环(回路)?( )【东北大学2000 4．2(4分)】

（A）深度优先遍历

（B）拓扑排序

（C）求最短路径

（D）求关键路径

10 判断有向图是否有回路，除了可以用拓扑排序外，还可以用( )。【南京理工大学2004一、7(1分)】

（A）求关键路径的方法

（B）广度优先遍历算法

（C）求最短路径的算法

（D）深度优先遍历算法

11 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。【合肥工业大学2001一、2(2分)】

（A）O(n)

（B）O(n+e)

（C）O(n2)

（D）O(n2)

12 在求边稠密的图的最小代价生成树时，采用( )算法较合适。【上海交通大学2005四、7(2分)】

答案见麦多课文库