1、计算机专业基础综合数据结构（图）历年真题试卷汇编 3及答案解析(总分：58.00，做题时间：90 分钟)一、综合题(总题数：23，分数：58.00)1.下面的邻接表表示一个给定的无向图。 （分数：2.00）_给出图 G： （分数：4.00）(1).画出 G的邻接表表示图；（分数：2.00）_(2).根据你画出的邻接表，以顶点为根，画出 G的深度优先生成树和广度优先生成树。【南开大学1997五(14 分)】【烟台大学 2007四、3(15 分)】（分数：2.00）_2.已知一个有向图如图所示，则从顶点 a出发进行深度优先遍历，写出所有可能得到的 DFS序列。（分数：2.00）_解答下面的问题：
2、（分数：4.00）(1).如果每个指针需要 4字节，每个顶点的标号占 2字节，每条边的权值占 2字节。下图采用哪种表示法所需的空间较多?为什么?（分数：2.00）_(2).写出下图从顶点 1开始的：DFS 树。（分数：2.00）_3.如下所示的连通图，请画出：(1)以顶点为根的深度优先生成树；(5 分)(2)如果有关节顶点，请找出所有的关节顶点。(5 分)【清华大学 l 998七(10 分)】 （分数：2.00）_某田径赛中各选手的参赛项目表如下： （分数：4.00）(1).根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；（分数：2.00）_(2).写出从元素 A出发按“广度
3、优先搜索”算法遍历此图的元素序列。【北京科技大学 1999五 2000五(12分)】（分数：2.00）_4.考虑下图： （分数：2.00）_5.在什么情况下，Prim 算法与 Kruskual算法生成不同的 MST?【西安电子科技大学 2000计算机应用一、11(5分)】（分数：2.00）_6.已知一个无向图如下图所示，要求分别用 Prim和 Kruskal算法生成最小生成树(假设以为起点，试画出构造过程)。 （分数：2.00）_7.一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。 （分数：2.00）_8.已知顶点 16 和输入边与权值的序列(如右图所示)：每行三个数表示一条边的两个端点
4、和其权值，共11行。请你： （分数：2.00）_9.下图表示一个地区的通信网，边表示城市间的通信线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的 n一 1条线路，画出所有可能的选择。【东北大学 2000一、4(4 分)】（分数：2.00）_10.试列出下图中全部可能的拓扑排序序列。 （分数：2.00）_11.试给出有向图的所有拓扑序列。 （分数：2.00）_12.对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【厦门大学 2006三、3(253 分)】（分数：2.00）_13.对于一个有向图，除了进行拓扑排序，还可以采用什么办法判断图中是否存在回路?请简述判断原
5、则。【北京航空航天大学 2007一、2(3 分)】（分数：2.00）_下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求： （分数：8.00）(1).该带权有向图的图形；（分数：2.00）_(2).从顶点 V1为起点的广度优先周游的顶点序列及对应的生成树(即支撑树)；（分数：2.00）_(3).以顶点 V1为起点的深度优先周游生成树；（分数：2.00）_(4).由顶点 V1到顶点 V3的最短路径。【中山大学 1994四(12 分)】（分数：2.00）_14.已知一有向网的邻接矩阵如下，如
6、需在其中一个结点建立娱乐中心，要求该结点距其他各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处?给出解题过程。 （分数：2.00）_15.求出下图中顶点 1到其余各顶点的最短路径。 （分数：2.00）_16.有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列 A 1 ，A 2 ，A 3 ，A 4 。 （分数：2.00）_17.试利用 Dijkstra算法求下图中从顶点 a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。【东南大学 2000四(10 分)】 （分数：2.00）_18.对于如下的加权有向图，给出算法 Dijkstra产生的最短
7、路径的支撑树，设顶点 A为源点，并写出生成过程。【吉林大学 1999一、2(4 分)】 （分数：2.00）_19.已知图的邻接矩阵为： （分数：2.00）_计算机专业基础综合数据结构（图）历年真题试卷汇编 3答案解析(总分：58.00，做题时间：90 分钟)一、综合题(总题数：23，分数：58.00)1.下面的邻接表表示一个给定的无向图。 （分数：2.00）_正确答案：(正确答案：(1)v 1 v 2 v 4 v 3 v 5 v 6 (2) v 1 v 2 v 3 v 4 v 5 v 6)解析：给出图 G： （分数：4.00）(1).画出 G的邻接表表示图；（分数：2.00）_正确答案：(正确
8、答案： )解析：(2).根据你画出的邻接表，以顶点为根，画出 G的深度优先生成树和广度优先生成树。【南开大学1997五(14 分)】【烟台大学 2007四、3(15 分)】（分数：2.00）_正确答案：(正确答案：广度优先生成树，深度优先生成树，为节省篇幅，生成树横画，下同。 )解析：2.已知一个有向图如图所示，则从顶点 a出发进行深度优先遍历，写出所有可能得到的 DFS序列。（分数：2.00）_正确答案：(正确答案：共 8个：adbcfe，adbfce，adcbfe，adcebf adcefb，adebcj,adebfc，adefbc)解析：解答下面的问题： （分数：4.00）(1).如果每
9、个指针需要 4字节，每个顶点的标号占 2字节，每条边的权值占 2字节。下图采用哪种表示法所需的空间较多?为什么?（分数：2.00）_正确答案：(正确答案：邻接矩阵：(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、)解析：(2).写出下图从顶点 1开始的：DFS 树。（分数：2.00）_正确答案：(正确答案：因未确定存储结构，从顶点 1开始的 DFS树不唯一，现列出两个： )解析：3.如下所示的连通图，请画出：(1)以顶点为根的深度优先生成树；(5 分)(2)如果有关节顶点，请找出所有的关节顶点。(5 分)【清华大学 l 998七(10 分)】 （分数：2.00）_正确答案：(正确答案：(1)未确定存储结构，其 DFS树不唯一，其中之一(按邻接点逆序排列)是： )解析：某田径赛中各选手的参赛项目表如下： （分数：4.00）(1).根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；（分数：
11、2.00）_正确答案：(正确答案： )解析：(2).写出从元素 A出发按“广度优先搜索”算法遍历此图的元素序列。【北京科技大学 1999五 2000五(12分)】（分数：2.00）_正确答案：(正确答案：AFEDBC)解析：4.考虑下图： （分数：2.00）_正确答案：(正确答案：设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列。(1)ABGFDEC (2)EACFBDG (3) )解析：5.在什么情况下，Prim 算法与 Kruskual算法生成不同的 MST?【西安电子科技大学 2000计算机应用一、11(5分)】（分数：2.00）_正确答案：(正确答案：在边有相等权值(特别是边
12、的权值较小且相等)时可能会生成不同的 MST。)解析：6.已知一个无向图如下图所示，要求分别用 Prim和 Kruskal算法生成最小生成树(假设以为起点，试画出构造过程)。 （分数：2.00）_正确答案：(正确答案：设连通网 N=(V,E)，设 V是 N的顶点的集合，E 是 N上边的集合。Prim 算法从U=u 0 u 0 V)，TE=开始，重复执行下述操作：在所有 uU，vVU 的边(u，v)E 中找一条代价最小的边(u 0 ，v 0 )并入集合 TE，同时 v 0 并入 U，直至 U=V为止。此时，TE 中必有 n一 1条边，则T=(U,TE)为 N的最小生成树。Prim 算法适合边稠密
13、的情况，算法的时间复杂度为 O(n 2 )。Kruskal算法：开始令最小生成树的初始状态为只有刀个顶点而无边的非连通图 T=(V,)，图中每个顶点自成一个连通分量。在 E中选择代价最小的边，若该边依附的顶点落在 T中不同的连通分量上，则将此边加入 T中，否则舍去此边而选择下一条代价最小的边，直到 T中所有顶点都在同一连通分量上为止。算法的时间复杂度为 O(eloge)，适合于求稀疏网的最小生成树。Prim 算法构造最小生成树的步骤如 26题所示，为节省篇幅，这里不再用 Prim方法做，而是用 Kruskal算法来构造最小生成树，过程过程如下(下图也可选(2，4)代替(3，4)，选(5，6)。
14、代替(1，5)： )解析：7.一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。 （分数：2.00）_正确答案：(正确答案：设顶点集合为1，2，3，4，5，6，由下边的逻辑图可以看出，在1，2，3和4，5，6回路中，各任选两条边，加上边(2，4)，则可构成 9棵不同的最小生成树。 )解析：8.已知顶点 16 和输入边与权值的序列(如右图所示)：每行三个数表示一条边的两个端点和其权值，共11行。请你： （分数：2.00）_正确答案：(正确答案：(1) )解析：9.下图表示一个地区的通信网，边表示城市间的通信线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的 n一 1条
15、线路，画出所有可能的选择。【东北大学 2000一、4(4 分)】（分数：2.00）_正确答案：(正确答案：最小生成树的顶点集合：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，2，16)，(2，3，5)，(3，6，6)，(2，4，11)，(6，5，18)解析：10.试列出下图中全部可能的拓扑排序序列。 （分数：2.00）_正确答案：(正确答案：7 个：561234，516234，512634，512364，156234，152364，152634)解析：11
16、.试给出有向图的所有拓扑序列。 （分数：2.00）_正确答案：(正确答案：3 个：23 1546，213546，123546)解析：12.对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【厦门大学 2006三、3(253 分)】（分数：2.00）_正确答案：(正确答案：图的深度优先遍历可用于拓扑排序，使用 dfs遍历所得顶点序列是逆拓扑序列。)解析：13.对于一个有向图，除了进行拓扑排序，还可以采用什么办法判断图中是否存在回路?请简述判断原则。【北京航空航天大学 2007一、2(3 分)】（分数：2.00）_正确答案：(正确答案：图的深度优先遍历可用于判断图中是否存在回路。若从有向图某顶
17、点 V出发进行遍历，在 dfs(v)结束之前出现从顶点 W到顶点 V的回边，由于 W在生成树上是 V的子孙，则有向图中必定存在包含顶点 V和 W的环。)解析：下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求： （分数：8.00）(1).该带权有向图的图形；（分数：2.00）_正确答案：(正确答案： )解析：(2).从顶点 V1为起点的广度优先周游的顶点序列及对应的生成树(即支撑树)；（分数：2.00）_正确答案：(正确答案：V1，V2，V4，V6，V3，V5 )解析：(3).以顶点 V
18、1为起点的深度优先周游生成树；（分数：2.00）_正确答案：(正确答案：顶点集合 V(G)=V1，V2，V3，V4，V5，V6边的集合 E(G)=，)解析：(4).由顶点 V1到顶点 V3的最短路径。【中山大学 1994四(12 分)】（分数：2.00）_正确答案：(正确答案：V1 到 V3最短路径(V1 一 V4一 V3)为 67。)解析：14.已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其他各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处?给出解题过程。 （分数：2.00）_正确答案：(正确答案：下面用 Floyd算法求出任意两顶点
19、的最短路径(如图 A (b) 所示)。题目要求娱乐中心“距其他各结点的最长往返路程最短”，结点 V1和 V3最长往返路径最短都是 9。按着“相同条件下总的往返路径越短越好”，选顶点 V5，总的往返路径是 34。 )解析：15.求出下图中顶点 1到其余各顶点的最短路径。 （分数：2.00）_正确答案：(正确答案：本表中 DIST中各列最下方的数字是顶点 1到顶点的最短路径。 )解析：16.有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列 A 1 ，A 2 ，A 3 ，A 4 。 （分数：2.00）_正确答案：(正确答案： )解析：17.试利用 Dijkstra算法求下图中从顶
20、点 a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。【东南大学 2000四(10 分)】 （分数：2.00）_正确答案：(正确答案：求解过程略。顶点 a到顶点 b，c，d，e，f，g 间的最短路径分别是15，2，11，10，6，13。)解析：18.对于如下的加权有向图，给出算法 Dijkstra产生的最短路径的支撑树，设顶点 A为源点，并写出生成过程。【吉林大学 1999一、2(4 分)】 （分数：2.00）_正确答案：(正确答案：顶点 A到顶点 B，C，D，E 的最短路径依次是 3，1 8，38，43，按 Dijkstra所选顶点过程是 B，C，D，E。支撑树的边集合为A，B，B，C，C，D，B，E。)解析：19.已知图的邻接矩阵为： （分数：2.00）_正确答案：(正确答案：(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 设一栈，将入度为零的顶点放入栈中 )解析：
