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

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

一、综合题

1 下面的邻接表表示一个给定的无向图。(1)给

出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列；(2)给出从顶v1，1开始，对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)】

1 给出图G：

2 画出G的邻接表表示图；

3 根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。【南开大学1997五(14分)】【烟台大学2007四、3(15分)】

4 已知一个有向图如图所示，则从顶点a出发进行深度优先遍历，写出所有可能得

到的DFS序列。

【北京交通大学2006四、4(5分)】

答案见麦多课文库

4 解答下面的问题：分)】

【西安电子科技大学2000计算机应用六(10

5 如果每个指针需要4字节，每个顶点的标号占2字节，每条边的权值占2字节。下图采用哪种表示法所需的空间较多?为什么?

6 写出下图从顶点1开始的：DFS树。

7 如下所示的连通图，请画出：(1)以顶点①为根的深度优先生成树；(5分)(2)如果有关节顶点，请找出所有的关节顶点。(5分)【清华大学l 998七(10分)】

7 某田径赛中各选手的参赛项目表如下：

设项目A，B，…，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。

8 根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；

9 写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。【北京科技大学1999五2000五(12分)】

答案见麦多课文库

10 考虑下图：(1)从顶点A出发，求它的深度优先生成树。(2)从

顶点E出发，求它的广度优先生成树。(3)根据普利姆(Prim)算法，求它的最小生成树。【上海交通大学1999六(12分)】

11 在什么情况下，Prim算法与Kruskual算法生成不同的MST?【西安电子科技大学2000计算机应用一、11(5分)】

12 已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小生成树

(假设以①为起点，试画出构造过程)。2000九(8分)】

【哈尔滨工业大学

13 一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。

【浙江大学1994五(8分)】

14 已知顶点1～6和输入边与权值的序列(如右图所示)：每行三个数表示一条边的

两个端点和其权值，共11行。请你：(1)采用邻接多重表表示该无向

答案见麦多课文库

网，用类Pascal语言描述该数据结构，画出存储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。(2)分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的生成树。(3)按Prim算法列表计算，从顶点1始求最小生成树，并图示该树。【北京工业大学1999四(20分)】

15 下图表示一个地区的通信网，边表示城市间的通信线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n一1条线路，画出所有

可能的选择。【东北大学2000一、4(4分)】

16 试列出下图中全部可能的拓扑排序序列。大学2007一、2(8分)】

【中国海洋

17 试给出有向图的所有拓扑序列。五、3(5分)】

【北京交通大学2005

18 对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【厦门大学2006三、3(25／3分)】

19 对于一个有向图，除了进行拓扑排序，还可以采用什么办法判断图中是否存在回路?请简述判断原则。【北京航空航天大学2007一、2(3分)】

答案见麦多课文库