1、计算机专业基础综合数据结构（图）历年真题试卷汇编 9 及答案与解析一、综合题1 下面的邻接表表示一个给定的无向图。 (1)给出从顶点 v1 开始，对图 G 用深度优先搜索法进行遍历时的顶点序列； (2)给出从顶v1，1 开始，对图 G 用广度优先搜索法进行遍历时的顶点序列。 【复旦大学 1998六(10 分 )】1 给出图 G：2 画出 G 的邻接表表示图；3 根据你画出的邻接表，以顶点为根，画出 G 的深度优先生成树和广度优先生成树。【南开大学 1997 五(14 分)】【烟台大学 2007 四、3(15 分)】4 已知一个有向图如图所示，则从顶点 a 出发进行深度优先遍历，写出所有可能得到
2、的 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 各表示一数据元素，若两项目不能同时举行，则将其连线(约束条
3、件)。8 根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；9 写出从元素 A 出发按“ 广度优先搜索” 算法遍历此图的元素序列。【北京科技大学 1999 五 2000 五(12 分)】10 考虑下图： (1)从顶点 A 出发，求它的深度优先生成树。 (2)从顶点 E 出发，求它的广度优先生成树。(3)根据普利姆 (Prim)算法，求它的最小生成树。【上海交通大学 1999 六(12 分)】11 在什么情况下，Prim 算法与 Kruskual 算法生成不同的 MST?【西安电子科技大学 2000 计算机应用一、11(5 分)】12 已知一个无向图如下图所示，要求分别用 Pri
4、m 和 Kruskal 算法生成最小生成树(假设以为起点，试画出构造过程 )。 【哈尔滨工业大学2000 九(8 分)】13 一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。【浙江大学 1994 五(8 分)】14 已知顶点 16 和输入边与权值的序列(如右图所示)：每行三个数表示一条边的两个端点和其权值，共 11 行。请你： (1)采用邻接多重表表示该无向网，用类 Pascal 语言描述该数据结构，画出存储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。(2)分别写出从顶点 1 出发的深度优先和广度优先遍历顶点序列，以及相应的生成树。(3)按 Prim 算法列表计算，从
5、顶点 1 始求最小生成树，并图示该树。【北京工业大学 1999 四(20 分)】15 下图表示一个地区的通信网，边表示城市间的通信线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的 n 一 1 条线路，画出所有可能的选择。【东北大学 2000 一、4(4 分)】16 试列出下图中全部可能的拓扑排序序列。 【中国海洋大学 2007 一、2(8 分) 】17 试给出有向图的所有拓扑序列。 【北京交通大学 2005 五、3(5 分)】18 对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【厦门大学 2006三、3(25 3 分) 】19 对于一个有向图，除了进行拓扑排序
6、，还可以采用什么办法判断图中是否存在回路?请简述判断原则。 【 北京航空航天大学 2007 一、2(3 分)】19 下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：20 该带权有向图的图形；21 从顶点 V1 为起点的广度优先周游的顶点序列及对应的生成树 (即支撑树)；22 以顶点 V1 为起点的深度优先周游生成树；23 由顶点 V1 到顶点 V3 的最短路径。【中山大学 1994 四(12 分)】24 已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其他各结
7、点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处? 给出解题过程。 【北京邮电大学 2002 四、1(10 分 )】25 求出下图中顶点 1 到其余各顶点的最短路径。【厦门大学 2002 八、2(5 分)】26 有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A1，A 2，A 3，A 4。 【北京邮电大学 2001 四、5(5 分)】27 试利用 Dijkstra 算法求下图中从顶点 a 到其他各顶点间的最短路径，写出执行算法过程中各步的状态。【东南大学 2000 四(10 分)】28 对于如下的加权有向图，给出算法 Dijkstra 产生的最短路
8、径的支撑树，设顶点A 为源点，并写出生成过程。【吉林大学 1999 一、 2(4 分)】29 已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点 V1 为出发点的唯一的深度优先遍历序列；(2)以顶点 V1 为出发点的唯一的广度优先遍历序列；(3)该图唯一的拓扑有序序列。【同济大学 1998 一(12 分)】计算机专业基础综合数据结构（图）历年真题试卷汇编 9 答案与解析一、综合题1 【正确答案】 (1)v 1v2v4v3v5v6 (2) v1v2v3v4v5v62 【正确答案】 3 【正确答案】 广度优先生成树，深度优先生成树，为节省篇幅，生成
9、树横画，下同。4 【正确答案】 共 8 个：adbcfe，adbfce ，adcbfe，adcebf adcefb，adebcj,adebfc，adefbc5 【正确答案】 邻接矩阵：(6*6 个元素)*2 字节元素=72 字节邻接表：表头向量 6*(4+2)+边结点 9*(2+2+4)*2=180 字节邻接多重表：表头向量 6*(4+2)+边结点 9*(2+2+2+4+4)=162 字节邻接表占用空间较多，因为边较多，边结点又是边数的 2 倍，一般来说，邻接矩阵所占空间与边个数无关(不考虑压缩存储)，适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点
10、下标域和一个指针域。6 【正确答案】 因未确定存储结构，从顶点 1 开始的 DFS 树不唯一，现列出两个：7 【正确答案】 (1)未确定存储结构，其 DFS 树不唯一，其中之一 (按邻接点逆序排列)是： (2)关节顶点有 3，1，8，7，2。8 【正确答案】 9 【正确答案】 AFEDBC10 【正确答案】 设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列。(1)ABGFDEC (2)EACFBDG (3)11 【正确答案】 在边有相等权值(特别是边的权值较小且相等)时可能会生成不同的 MST。12 【正确答案】 设连通网 N=(V,E)，设 V 是 N 的顶点的集合，E 是 N 上
11、边的集合。Prim 算法从 U=u0u0V)，TE=开始，重复执行下述操作：在所有uU， vVU 的边(u ，v)E 中找一条代价最小的边(u 0，v 0)并入集合 TE，同时 v0并入 U，直至 U=V 为止。此时， TE 中必有 n 一 1 条边，则 T=(U,TE)为 N 的最小生成树。Prim 算法适合边稠密的情况，算法的时间复杂度为 O(n2)。Kruskal算法：开始令最小生成树的初始状态为只有刀个顶点而无边的非连通图 T=(V,)，图中每个顶点自成一个连通分量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入 T 中，否则舍去此边而选择下一条
12、代价最小的边，直到 T 中所有顶点都在同一连通分量上为止。算法的时间复杂度为O(eloge)，适合于求稀疏网的最小生成树。Prim 算法构造最小生成树的步骤如 26题所示，为节省篇幅，这里不再用 Prim 方法做，而是用 Kruskal 算法来构造最小生成树，过程过程如下(下图也可选(2，4)代替(3 ，4)，选(5，6) 。代替(1，5)：13 【正确答案】 设顶点集合为1，2，3，4，5，6 ，由下边的逻辑图可以看出，在1， 2，3和4，5，6回路中，各任选两条边，加上边 (2，4)，则可构成 9 棵不同的最小生成树。14 【正确答案】 (1) (2)深度优先遍历序列：1，4，6，5，3，
13、2；深度优先生成树的边集合：(1，4)，(4 ，6)，(6，5)，(5，3)，(3，2)(3)广度优先遍历序列：1 4 3 2 6 5；广度优先生成树的边集合：(1，4)，(1，3)，(1 ， 2)，(4，6)，(4，5)：(4)按：Prim 构造过程只画出最小生成树的边和权值：E(G)=(1，4，3)，(4，3，4)，(3，5，1)，(3，2，2)，(3，6， 10)15 【正确答案】 最小生成树的顶点集合：V(G)=1，2，3，4，5，6，下面两个边的集合都可以。E1(G)=(1，2，16)， (2 ，3，5)， (2，6，6)， (2，4，11)， (6，5，18) ，E2(G)=(1，
14、2，16)，(2 ，3，5)，(3，6，6)，(2，4，11)，(6，5，18)16 【正确答案】 7 个：561234，516234，512634，512364，156234，152364，15263417 【正确答案】 3 个：23 1546，213546，12354618 【正确答案】 图的深度优先遍历可用于拓扑排序，使用 dfs 遍历所得顶点序列是逆拓扑序列。19 【正确答案】 图的深度优先遍历可用于判断图中是否存在回路。若从有向图某顶点 V 出发进行遍历，在 dfs(v)结束之前出现从顶点 W 到顶点 V 的回边，由于 W在生成树上是 V 的子孙，则有向图中必定存在包含顶点 V 和
15、W 的环。20 【正确答案】 21 【正确答案】 V1，V2，V4，V6，V3，V522 【正确答案】 顶点集合 V(G)=V1，V2，V3，V4，V5，V6边的集合 E(G)=， ，)23 【正确答案】 V1 到 V3 最短路径(V1 一 V4 一 V3)为 67。24 【正确答案】 下面用 Floyd 算法求出任意两顶点的最短路径(如图 A(b)所示)。题目要求娱乐中心“ 距其他各结点的最长往返路程最短” ，结点 V1 和 V3 最长往返路径最短都是 9。按着“ 相同条件下总的往返路径越短越好” ，选顶点 V5，总的往返路径是 34。25 【正确答案】 本表中 DIST 中各列最下方的数字
16、是顶点 1 到顶点的最短路径。顶点 1 到其他顶点的最短路径依次是 20，31，28，10，17，25，35。按 Dijkstra 算法所选顶点依次是 5，6，2，7，4，3，8。26 【正确答案】 27 【正确答案】 求解过程略。顶点 a 到顶点 b，c ，d，e，f，g 间的最短路径分别是 15，2，11，10，6，13。28 【正确答案】 顶点 A 到顶点 B，C，D，E 的最短路径依次是 3，1 8，38，43，按 Dijkstra 所选顶点过程是 B，C，D ，E。支撑树的边集合为A， B，B，C ，C，D，B，E。29 【正确答案】 (1)V1 ， V4，V9，V10，V7，V6，V8，V3，V2 ，V5 深度优先遍历生成树如右面第一图(2)V1，V4，V3，V2，V9， V7，V6，V5，V8 广度优先遍历生成树如右面第二图(3)V1，V2，V5，V3，V4， V6，V7，V9，V10 设一栈，将入度为零的顶点放入栈中
