计算机专业基础综合数据结构图历年真题试卷汇编3

1、计算机专业基础综合数据结构（图）历年真题试卷汇编（总分：58.00 ,做题时间：90分钟）综合题（总题数：23,分数：58.00）1.下面的邻接表表示一个给定的无向图。（1）给出从顶点v1开始，对图G用深度优先搜索法进行遍【复旦大学历时的顶点序列；（2）给出从顶v1, 1开始，对图G用广度优先搜索法进行遍历时的顶点序歹U。1998 六（10 分）（分数：2.00） 正确答案：(正确答案：(1)v 1 V 2 v 4 v 3 v 5 v 6 v 1 V 2 v 3 V 4 V 5 V s) 解析：给出图G: | （分数：4.00）.画出G的邻接表表示图；（分数： 2.00）正确答案：（正确答案:

2、 解析:.根据你画出的邻接表，以顶点为根，画出G的深度优先生成树和广度优先生成树。【南开大学 1997五（14分）】【烟台大学2007四、3（15分）】（分数：2.00）正确答案：（正确答案：广度优先生成树，深度优先生成树，为节省篇幅，生成树横画，下同。II）解析：写出所有可能得到的DFS序列。正确答案：（正确答案：因未确定存储结构，从顶点1开始的DFS树不唯一，现列出两个:口）2.已知一个有向图如图所示， 则从顶点a出发进行深度优先遍历, 京交通大学2006四、4（5分）】（分数：2.00） 正确答案：（正确答案：共 8 个：adbcfe , adbfce , adcbfe , adcebf

3、 adcefb , adebcj,adebfc , adefbc） 解析：解答下面的问题：【西安电子科技大学 2000计算机应用六（10分）】（分数：4.00）.如果每个指针需要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倍，一般来说，邻接矩

4、阵所占空间与边个数无关（不考虑压缩存储），适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个 顶点下标域和一个指针域。） 解析：.写出下图从顶点1开始的：DFS树。（分数：2.00）解析：下所示的连通图，请画出：（1）以顶点为根的深度优先生成树；（5分）（2）如果有关节顶点，请找出所有的关节顶点（分数:2.00）（5分）【清华大学l 998七（10分）】正确答案：（正确答案：（1）未确定存储结构, 关节顶点有3, 1, 8, 7, 2。）解析：其DFS树不唯一，其中之一（按邻接点逆序排列)是:某田径赛中各选手的参赛项目表如下:设项目A, B,F各表示一数据

5、元素，若两项目不能同时举行，则将其连线（约束条件）。（分数：4.00）.根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；（分数：2.00 ）正确答案：（正确答案:解析:【北京科技大学 1999五2000五（12.写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列分）】（分数：2.00） 正确答案：（正确答案：AFEDBC）解析：.考虑下图：|1（1）从顶点A出发，求它的深度优先生成树。（2）从顶点E出发，求它的广度优先生成树。（3）根据普利姆（Prim）算法，求它的最小生成树。【上海交通大学1999六（12分）】(1)ABGFDEC（分数：2.00） 正确答案：（正确答

6、案：设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列(2)EACFBDG (3)解析:.在什么情况下，Prim算法与Kruskual算法生成不同的 MST?西安电子科技大学 2000计算机应用一、11（5分）1（分数：2.00）正确答案：（正确答案：在边有相等权值 解析：（特别是边的权值较小且相等）时可能会生成不同的 MST ）6.已知一个无向图如下图所示，要求分别用出构造过程）。【哈尔滨工业大学Prim和Kruskal算法生成最小生成树（假设以为起点，试画2000九（8分）】（分数：2.00）正确答案：（正确答案：设连通网N=（V,E），设V是N的顶点的集合，E是N上边的集合。Pr

7、im算法从U=u 0 u 0 GV）, TE=开始，重复执行下述操作：在所有uU, vGV- U的边（u , v） G E中找一条代价最小的边（u 0 , v 0 ）并入集合TE,同时v 0并入U,直至U=V为止。此时，TE中必有n 1条边，则T=（U, | TE| ）为N的最小生成树。Prim算法适合边稠密的情况，算法的时间复杂度为O（n 2 ）。Kruskal算法：开始令最小生成树的初始状态为只有刀个顶点而无边的非连通图T=（V,），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T中，否则舍去此边而选择下一条代价最小的边，直到O

8、(eloge),适合于求稀疏网的最小生成树。T中所有顶点都在同一连通分量上为止。算法的时间复杂度为Prim算法构造最小生成树的步骤如这里不再用Prim方法做，而是用 Kruskal算法来构造最小生成树，过程过程如下26题所示，为节省篇幅，(下图也可选(2 , 4)代替(3, 4),选(5, 6) o 代替(1 , 5):解析：. 一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。(分数：2.00)【浙江大学1994五(8分)】正确答案：(正确答案：设顶点集合为5, 6回路中，各任选两条边，加上边 解析：1 , 2, 3, 4, 5, 6,由下边的逻辑图可以看出，在1,2, 3和4,(2,

9、4),则可构成9棵不同的最小生成树.已知顶点16和输入边与权值的序列(如右图所示)：每行三个数表示一条边的两个端点和其权值，共11行。请你:采用邻接多重表表示该无向网，用类Pascal语言描述该数据结构，画出存储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。(2)分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的生成树。(3)按Prim算法列表计算，从顶点1始求最小生成树，并图示该树。【北京工业大学 1999四(20分)】(分数：2.00)正确答案：(正确答案：(1) |(2)深度优先遍历序列:1, 4, 6, 5, 3, 2;深度优先生成树的边集合：(1 ,

10、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) 解析：.下图表示一个地区的通信网，边表示城市间的通信线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的1条线路，画出所有可能的选择。【东北大学

11、2000 、4(4分)】(分数：2.00) 正确答案：(正确答案：最小生成树的顶点集合：6)=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)II【中国海洋大学2007 、2(8分)】解析：.试列出下图中全部可能的拓扑排序序列(分数：2.00)正确答案：(正确答案：7 个：561234, 516234, 512634, 512364, 15

12、6234, 152364, 152634)解析：11.试给出有向图的所有拓扑序列【北京交通大学2005五、3(5分)】(分数：2.00) 正确答案：(正确答案：3个：23 1546, 213546, 123546)解析：.对于一个有向图，不用拓扑排序，如何判断图中是否存在环？【厦门大学2006三、3（25/3分）】（分数：2.00）正确答案：（正确答案：图的深度优先遍历可用于拓扑排序，使用dfs遍历所得顶点序列是逆拓扑序列。）解析：.对于一个有向图，除了进行拓扑排序，还可以采用什么办法判断图中是否存在回路？请简述判断原则。【北京航空航天大学 2007 、2（3分）】（分数：2.00）正确答案：

13、（正确答案：图的深度优先遍历可用于判断图中是否存在回路。若从有向图某顶点V出发进行遍历，在dfs（v）结束之前出现从顶点 W到顶点V的回边，由于 W在生成小上是V的子孙，则有向图中必定存 在包含顶点V和W的环。） 解析：下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另rwrn一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：I I （分数：8.00）.该带权有向图的图形；（分数：2.00）|刖石正确答案：（正确答案：I）解析：.从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）；（分数：2.00）正确答案：（正确答案

14、：V1, V2, V4, V6, V3, V5|_|）解析：.以顶点V1为起点的深度优先周游生成树；（分数：2.00）正确答案：（正确答案：顶点集合 V（G）=V1 , V2, V3, V4, V5, V6边的集合E（G）=，）解析：.由顶点V1到顶点V3的最短路径。【中山大学 1994四（12分）】（分数：2.00）正确答案：（正确答案：V1到V3最短路径（V1 一 V4 V3）为67。）解析：.已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其他各结点的最长往电大学2002四、1（10分）（分数：2.00）正确答案：（正确答案：下面用Floyd算法求出任意两顶点的最

15、短路径（如图A （b）所示）。题目要求娱乐中 心“距其他各结点的最长往返路程最短”，结点V1和V3最长往返路径最短都是 9。按着“相同条件下总的往返路径越短越好”，选顶点V5,总的往返路径是 34o II）解析:【厦门大学2002八、2（5分）】.求出下图中顶点1到其余各顶点的最短路径。（分数：2.00）正确答案：（正确答案：本表中 DIST中各列最下方的数字是顶点 1到顶点的最短路径。顶点1到其他顶点的最短H径依次是20, 31 , 28, 10, 17, 25, 35。按Dijkstra算法所选顶点依次是 5, 6, 2, 7, 4, 3, 8。）解析：.有一图的邻接矩阵如下，试给出用弗洛

16、伊德算法求各点间最短距离的矩阵序列【北京邮电大学2001四、5（5分）】（分数：2.00）正确答案：（正确答案：解析：.试利用Dijkstra 算法求下图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。【东南大学2000四（10分）】（分数：2.00） 正确答案：（正确答案：求解过程略。顶点 a到顶点b, c, d, e, f, g间的最短路径分别是15, 2, 11,10, 6, 13o ）解析：18.对于如下的加权有向图，给出算法Dijkstra 产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。【吉林大学1999 一、2（4分）】（分数：2.00） 正确答案：（正确答案：顶点 A到顶点B, C, D, E的最短路径依次是 3, 1 8, 38, 43,按Dijkstra 所选 顶点过程是B, C, D, Eo支撑树的边集合为, , , 。） 解析：19.已知图的邻接矩阵为:当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，