1、计算机专业基础综合数据结构（图）历年真题试卷汇编 11 及答案与解析一、设计题1 已知连通图如下： (1)若从顶点 B 出发对该图进行遍历，在(1)的基础上分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列；(2)写出按深度优先搜索的递归程序。【厦门大学 200l 三(12 分)】2 设计算法以实现对无向图 G 的深度遍历，要求：将每一个连通分量中的顶点以一个表的形，式输出。例如，下图的输出结果为：(1，3)(2，6，7，4，5，8)(9，10)。注：本算法中可以调用以下几个函数：firstadj(g，1，)返回图 g 中顶点 v 的第一个邻接点的号码，若不存在，则返回0。nextadj(
2、g，v，w) 返回图 g 中顶点 v 的邻接点中处于 w 之后的邻接点的号码，若不存在，则返回 0。nodes(g)返回图 g 中的顶点数。【合肥工业大学2000 五、4(8 分) 】3 请设计一个图的抽象数据类型(只需要用类 Pascal 或类 CC+语言给出其主要功能函数或过程的接口说明，不需要指定存储结构，也不需要写出函数或过程的实现方法)，利用抽象数据类型所提供的函数或过程编写图的广度优先周游算法。算法不应该涉及具体的存储结构，也不允许不通过函数或过程而直接引用图结构的数据成员，抽象数据类型和算法都应该加足够的注释。【北京大学 1999 二、1(10 分)】4 设计算法以判断给定的无向
3、图 G 中是否存在一条以网为起点的包含所有顶点的简单路径，若存在，返回 TRUE，否则，返回 FALSE(注：本算法中可以调用以下几个函数：FIRSTADJ(G， V)返回图 G 中顶点 V 的第一个邻接点的号码，若不存在，则返回 0；NEXTADJ(G，W) 返回图 G 中顶点 V 的邻接点中处于 W之后的邻接点的号码，若不存在，则返回 0；NODES(G)返回图 G 中的顶点数)。【合肥工业大学 1999 五、5(8 分)】5 已有邻接表表示的有向图，请编程判断从第 u 顶点至第 v 顶点是否有简单路径，若有，则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的
4、运算要自己实现。(尽量采用非递归算法，否则满分 15 分)【北京工业大学 2000 六(20 分) 】6 图的 D 搜索类似于 BFS，不同之处在于使用栈代替 BFS 中的队列，入出队列的操作改为入出栈的操作，即当一个顶点的所有邻接点被搜索之后，下一个搜索出发点应该是最近入栈(栈顶) 的顶点。(1) 用邻接表做存储结构，写一个 D 一搜索算法；(15 分)(2)用 D 搜索方法搜索右图，设初始出发点为 1，写出顶点的访问次序和相应的生成树，当从某顶点出发搜索它的邻接点时，请按邻接点序号递增序搜索，以使答案唯一。(5 分) 【中科院计算所 1998 六(20 分)】7 令 G=(V，E)为一个有
5、向无环图，编写一个给图 G 中每一个顶点赋以一个整数序号的算法，并满足以下条件：若从顶点 i 至顶点 j 有一条弧，则应使 ij 。【清华大学 1996 七】8 二部图(biparite graph)G=(V，E)是一个能将其结点集 V 分为两个不相交子集 V1和 V2= V-V1 的无向图，使得：V1 中的任何两个结点在图 G 中均不相邻，V2 中的任何两个结点在图 G 中也均不相邻。(1)请各举一个结点个数为 5 的二部图和非二部图的例子。(2)请用 C 或 Pascal 编写一个函数 BIPARTITE 判断一个连通无向图 G 是否是二部图，并分析程序的时间复杂度。设 G 用二维数组 A
6、 来表示，大小为 n*n(n 为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【浙江大学 1998 八(15 分) 】9 我们可用“ 破圈法” 求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边” ，反复执行这一步骤，直到没有圈为止。请给出用“破圈法 ”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。【复旦大学 1997 六(13 分)】10 设图用邻接表表示，写出求从指定顶点到其余各顶点的最短路径的 Dijksua 算法。要求：(1)对所用的辅助数据结构，邻接表结构给以必要的说明
7、；(6 分)(2)写出算法描述。(C，类 Pascal，类 C 均可)(14 分)【南京理工大学 1996 四、1(20 分)】11 已知 n 个顶点的有向图，用邻接矩阵表示，编写函数，计算每对顶点之间的最短路径。【南京航空航天大学 2001 九(10 分)】12 给定 n 个村庄之间的交通图，若村庄 i 和 j 之间有道路，则将顶点 i 和 j 用边连接，边上的 mj 表示这条道路的长度，现在要从这 n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。【中国矿业大学 2000 十五
8、(15 分) 】13 求解下面有向图的有关问题：(1)判断此有向图是否有强连通分量?若有请画出。(2)画出此有向图的十字链表存储结构；其顶点表结点结构为(data，firstin，firstout)，其中 data，是顶点的有关信息；firstin 是指向以该顶点为弧头的第一条边的指针；firstout 是指向以该顶点为弧尾的第一条边的指针。其表结点的结构为(tailvex，headvex，weight，hlink，tlink)，其中 tailvex、headvex 分别为弧尾和弧头在图中的序号；weight 是弧上的权值，hlink、tlink 分别为指向弧头相同和弧尾相同的下一条边的指针。
9、“(3)设其顶点 a，b，c，d,e 表示一个乡的 5 个村庄，弧上的权值表示为两村之间的距离。求每个村庄到其他村庄的最短距离； 乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近。【北京邮电大学 1997 五(15 分)】“14 设计算法求距离顶点 V0 的最短路径长度(以弧数为单位)为 K 的所有顶点，要求尽可能地节省时间。【东南大学 2002 八(10 分)2005 五(10 分)】15 采用链接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为 k 的简单路径算法。【中国海洋大学 2005 九(18 分)】16 自由树(即无环连通图)T=(K,E)的
10、直径是树中所有点对间最短路径长度的最大值，即 T 的直径定义为 MAX D(u，v)，这里 D(u，v)表示顶点 u 到顶点 v 的最短路径长度(路径长度为路径中所包含的边数)。试写一算法求 T 的直径，并分析算法的时间复杂度。(时间复杂度越小得分越高。)【中科院计算所 1999 五、3(20 分)】17 设 G 是含有 n 个顶点(设顶点编号为 1，2，n)的有向无环图。将 G 用如下定义的邻接表存储(编者略)。请编写一个非递归算法求 G 的每个顶点出发的最长路径的长度(每条弧的长度均为 1)并存入 mpl 域中。要求：首先写出算法思想，然后写算法过程。18 设有向无环图 G 以邻接矩阵方式
11、存储，编写程序，求 G 图中最长的路径长度，并写出算法思想。【南京航空航天大学 2005 八(10 分)】19 编写程序，实现用拓扑排序方法求最长路径的算法。【南京航空航天大学 2003七(10 分 )】20 图 G 有 n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生 G的最小生成树的算法。【东南大学 1994 四(1 8 分)】21 设 G 是一个用邻接表表示的连通无向图。对于 G 中某个顶点 v，若从 G 中删去顶点 v 及与顶点 v 相关联的边后，G 变成由两个或两个以上非空连通分量所组成的图，则称 v 是原来图 G 的一个关节顶点。如下图中，只有顶点 4 和顶点 6 是
12、关节顶点，而其他顶点都不是关节顶点。试叙述寻找图 G 的所有关节顶点的算法，并用算法语言(Pascal 或 C)编写一个实现你所给出的算法的程序。【复旦大学 1996 八(20 分)】22 对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中的所有顶点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为 0 的邻接到的顶点进行递归。(1)给出完成上述功能的图的邻接表定义(结构) 。(4 分)(2)定义在算法中使用的全局辅助数组。(4 分)(3)写出在遍历图的同时进行拓扑排序的算法。(10 分)【东北大学 1999 五(
13、1 8 分)】【清华大学 1997 一(18 分)】【中科院研究生院 2003 十一(15 分)】23 设有向图以邻接矩阵 adj 表示，每个顶点的入度用数组 nodein 存储，已知 adj和 nodein。请写出对该图进行拓扑排序的算法。【中国海洋大学 2007 十(15 分)】24 已知一具有 n 个顶点的有向图 G=(V，E)采用邻接表存储方法，请写一算法，检查任意给定序列 v1，v 2，v n，(v iV，1in)是否为该有向图的一个拓扑序列。若是，算法给出信息是 1，否则，给出信息 0。【北京航空航天大学 2005 三(10 分)】25 欲用四种颜色对地图上的国家涂色，有相邻边界的
14、国家不能用同一种颜色(点相交不算相邻)。(1)试用一种数据结构表示地图上各国相邻的关系。(6 分)(2)描述涂色过程的算法。(不要求证明)(12 分)【浙江大学 2002 八(18 分)】26 设有 n(n0)个顶点的无向连通图 G，可以邻接矩阵 Ann 存储，由于邻接矩阵的对称性，只将其下三角顺序存储在数组 S 中。请编写对以数组 S 存储的图 G 进行广度优先遍历的算法。另，请讨论若是无向非连通图，你的算法有何变化。【厦门大学 2004 七(15 分) 】【烟台大学 2005 五、3(15 分)】27 用有向无环图表示只含二元运算的算术表达式，可共享公共子表达式，设用邻接表存储算术表达式的
15、有向无环图，每个操作数都用单个字母表示。试写出邻接表的类型定义；编写输出算术表达式的逆波兰表达式(后缀表达式)的算法(请写明算法的基本思路，并在算法的主要步骤上加注释)。【北京理工大学 2002 82(7 分)】28 一个有向图 G=(V,E)的平方图 G2=(V,E2)满足下述性质：(u，w) E2 当且仅当存在某个顶点 vV，使得(u ，v) E 且(v，w) E。写一个算法从给定的 G 求出 G2，G和 G2 可分别用两个邻接表表示。【中国科学技术大学 1998 六(15 分)】28 设在 4 地(A，B，C，D)之间架设有 6 座桥，如图所示。要求从某一地出发，经过每座桥恰巧一次，最后
16、仍回到原地。29 试就以上图形说明：此问题有解的条件是什么? (5 分)30 设图中的顶点数为 n，试用 C 或 Pascal 描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。(10 分)【清华大学 2001 一(1 5 分)】31 从根到叶子的最大距离称为树的半径。给定一个无向连通图，写一个算法以找出半径最小的生成树。【东北大学 2003 五(10 分)】计算机专业基础综合数据结构（图）历年真题试卷汇编 11 答案与解析一、设计题1 【正确答案】 (1)在邻接点按升序排列的前提下，其 dfs 和 bfs 序列分别为BADCEF 和 BACEDF。(2)深度优先遍历的递归
17、程序 dfso 如下：void dfs(v) v 是顶点信息(i=GraphLocateVertex(g，v)； 定位顶点visitedi=1；coutadjvex=0)dfs(gp-adjvexvertex)；p=p 一next； while dfs2 【正确答案】 对无向图 G 的深度优先遍历，dfs 算法上面已有几处(见上面 22 题、23 题)。这里仅给出将连通分量的顶点用括号括起来的算法的语句。各顶点的邻接点要按升序排列。for(i=1； iadjvex=0)SPathdfs(p 一adjvex)； 深度优先遍历p=p 一next； 下一个邻接点 whilevisitedv0_0 ；
18、 num 一一； 取消访问标记，使该顶点可重新使用5 【正确答案】 与上题类似，这里给出非递归算法，顶点信息仍是编号。S+t0p=u；viSitedu=1；while(top0 p)(P=g Istopfirstarc； 第一个邻接点while(p!=nullvisitedp 一adjvex=1)p=p-next； 下一个访问邻接点if(p=null)top 一； 退栈elsei=p 一 adjvex； 取邻接点(编号)if(i=v) 找到从 u 到 v 的一条简单路径，输出(for(k=1；kadjvex=p 一 weight ； P=p 一next ； dist 数组存放最短路径for(i
19、=1；iadjvex ；if(Sj=0 第一邻接点while(p)j=p 一num；if(visitedj=0)visitedj=1；dfs(p 一adjvex)；p=p 一next；结束 dfs()31 【正确答案】 采用广度优先遍历，其邻接点均已遍历的结点是叶子结点，记下结点的半径(以分支个数记)。int MiniRadius(AdjList g，int v)图 g 以邻接表形式存储，求半径最小的生成树。设顶点信息就是编号，从顶点v 开始遍历typedef structint v，level;node; 队列元素int MAX=100； 设最大层次数int visitedMAX=0； 访问数组node R，Q Q 为队列，容量足够大R V=V； R1evel=1；QueueInit(Q)； QueueIn(Q，R)；while(!Empty(Q)R=QueueDel(Q)； 出队v=Rv； 1=Rlevel；P=gvfirstarc ；flag=0； flag 是顶点是否是叶子的标记while(p)w=p 一adjvex ；if(visitedw=0)flag=1;R.level=l+l；QueueIn(Q，R)；p=p 一next；if(flag=0) 其邻接点均已遍历的顶点是叶子结点(if(1MAX)MAX=1；return MAX；
