[考研类试卷]计算机专业基础综合数据结构（图）历年真题试卷汇编8及答案与解析.doc

1、计算机专业基础综合数据结构（图）历年真题试卷汇编 8 及答案与解析一、填空题1 在 AOE(Activuty On Edge)网中，从源点到汇点路径上各个活动的时间总和最长的路径称为_。【哈尔滨工业大学 2005 一、2(1 分)】2 下列函数是在无向图的邻接表中删除一条边的算法，请完善该程序。V0id deledge(ALGraph*G，int i， int j)EdgeNode*p，*q;p=G 一adj listifirstedge；if()fG 一adjlisti firstedge=p 一next; free(p)；)elsewhile(p 一next 一adjvex!=j )p=G

2、 一adj lisjfirstedge ；if(p 一adjvex= =i)G 一adj listjfirstedge=p 一12ext； free(p)；)elsefwhile(p 一12ext 一adlvex!=i p 一next)；if(p 一next!=null)q=p 一next；free(q)；)【东南大学 2005 数据结构部分三(10 分)】3 应用 Prim 算法求解连通网络的最小生成树问题。(1) 针对右图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(每边 1 分，共 5分)(始顶点号，终顶点号，权值) (2)下面是 Prim 算法的实现，中间有

3、 5 个地方缺失，请阅读程序后将它们补上。 const int MaxInt=INT MAX； INT MAX 的值在中 const int n：6； 图的顶点数，应由用户定义 typedef int AdjMatrixnn； 用二维数组作为邻接矩阵表示 typedef struct 生成树的边结点 int fromVex，toVex ； 边的起点与终点 int weight； 边上的权值 TreeEdgeNode； typedef TreeEdgeNode MST n 一 1； 最小生成树定义 void PrimMST(AdjMatrix G，MST T，int rt) 从顶点 rt 出发构

4、造图 G 的最小生成树 T，rt 成为树的根结点 TreeEdgeN0de e； int i， k=0，min ，minpos，V； for(i=0；i4 n 个顶点的有向图用邻接矩阵 array 表示，下面是其拓扑排序算法，试补充完整。注：(1)图的顶点号从 0 开始计；(2)indegree 是有 n 个分量的一维数组，放顶点的入度； (3)函数 crein 用于算顶点入度；(4)有三个函数 push(data)、pop()、check()其含义为数据 data 进栈、退栈和测试栈是否空(不空返回 1，否则 0)。crein(array，indegree，n)for(i=0；ivertex

5、；graphk count 一一； if()graphkcount=top；top=k；) 【浙江大学 2000 六(15 分)】二、综合题6 如果 G1 是一个具有 n 个顶点的连通无向图，那么 G1 最多有多少条边?G1 最少有多少条边?7 如果 G2 是一个具有 n 个顶点的强连通有向图，那么 G2 最多有多少条边?G2 最少有多少条边?8 如果 G3 是一个具有 n 个顶点的弱连通有向图，那么 G3 最多有多少条边?G3 最少有多少条边? 【复旦大学 1997 一(9 分) 】9 有 n 个顶点的有向强连通图最少有几条边?最多有几条边? 【厦门大学 2006 三、1(25 3 分) 】

6、10 表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?该矩阵是否为稀疏矩阵? 【厦门大学 2006 三、2(25 3 分)】11 一个二部图的邻接矩阵 A 是一个什么类型的矩阵 ?【北京科技大学 1999 一、8(2分)】12 证明：具有 n 个顶点和多于 n 一 1 条边的无向连通图 G 一定不是树。【东南大学 1993 四(10 分) 】13 证明对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全零的充要条件是该图是无环图。【北京邮电大学 2002 三(10 分)】14 如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 l 都集中到对

7、角线以上? 【清华大学 1999 一、5(2 分) 】15 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边?任意两个顶点 i 和 j 之间是否有边相连?任意一个顶点的度是多少?【北京理工大学 2006 六、4(507 分)】【华南理工大学 2005 二、5(4 分)】16 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关?与边的条数是否有关? 【西安电子科技大学 2000 计算机应用一、6(5 分)】16 请回答下列关于图(Graph)的一些问题：(每题 4 分)17 有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?18 表示一个有 1000 个

8、顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?19 对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【清华大学 2000一(12 分 )】19 解答问题。设有数据逻辑结构为：B=(K,R) ，K=K1，K2 ，K9R=，)20 画出这个逻辑结构的图示。(3 分)21 相对于关系 R，指出所有的开始结点和终端结点。(2 分)22 分别对关系 R 中的开始结点，举出一个拓扑序列的例子。(4 分)23 分别画出该逻辑结构的正向邻接表和逆向邻接表。(6 分)【山东工业大学 1999三(15 分 )】24 试用下列三种表示法画出图 G(编者略)的存储结构，并评述这三种表示

9、法的优、缺点：(1)邻接矩阵表示法；(2) 邻接表表示法；(3) 其他表示法。【华中理工大学2000 三(12 分) 】25 已知无向图 G，V(G)=1，2，3，4)，E(G)=(1，2)，(1，3)，(2，3)，(2，4) ，(3，4)。试画出 G 的邻接多重表，并说明，若已知点 i，如何根据邻接多重表找到与 i 相邻的点 j?【东南大学 1994 一、2(8 分)1998 一、6(8 分)】26 对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些? 【北京航空航天大学 1998 一、7(4 分)】27 图的深度优先遍历和广度优先遍历各采用什么样的数据结构来暂

10、存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?【吉林大学 2007 二、7(3 分)】计算机专业基础综合数据结构（图）历年真题试卷汇编 8 答案与解析一、填空题1 【正确答案】 关键路径2 【正确答案】 p 一adjvex=jp=p 一next p 一next=q-nextp=p 一next p 一next=-q-next3 【正确答案】 (1)(0，3 ，1)，(3，5，4)，(5，2 ，2)，(3，1，5)，(1，4，3)(2)QTk.tovex=imin=Maxintmispos=iexit(0)Tifromvex=v4 【正确答案】 (1)0(2)j(3)i(4)0(5)in

11、degreei=0(6)vexi(7)k=1(8)indegreei=05 【正确答案】 (1)V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列给出的。)(2)top=一 1 top=graphjcount graphk count=0二、综合题6 【正确答案】 G1 最多 n(n1)2 条边，最少 n 一 1 条边。7 【正确答案】 G2 最多 n(n1)条边，最少 n 条边。8 【正确答案】 )G3 最多 n(n 一 1)条边，最少 n 一 1 条边。说明：弱连通有向图是指把有向图看作无向图时，仍是连通的。9

12、 【正确答案】 最少 n 条边，最多 n(n 一 1)条边。10 【正确答案】 1 000 000 个矩阵元素。稀疏矩阵的定义是矩阵中非零元素远少于矩阵元素个数，且分布无规律。本题未说明分布情况，因此，不能确定为稀疏矩阵。11 【正确答案】 分块对称矩阵。12 【正确答案】 证明：具有 n 个顶点、n 一 1 条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于 n 一 1 条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。13 【正确答案】 证明：该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由

13、于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为 0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(Aij=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为 0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度的大小进行顺序编号。)14 【正确答案】 按各顶点的出度进行排序。n 个顶点的有向图，其顶点最大出度是 n1，最小出度为 0。这 样排序后，出度最大的顶点编号为 1，出度最小的顶点编号为 n。之后，进行调整，即若存在弧i，j，而顶点 j 的出度大于顶点 i 的出

14、度，则将把 j 编号在顶点 i 的编号之前。15 【正确答案】 设邻接矩阵为 A，则 A 中非零元素个数的一半即为图的边数；若Aij!=0，则顶点 i 和 j 间有边相连；顶点 i 的度是第 i 行(或第 i 列)非零元素的个数。16 【正确答案】 设图的顶点个数为 n(n1)，则邻接矩阵元素个数为 n2，即顶点个数的平方，与图的边数无关。17 【正确答案】 n(n 一 1)，n18 【正确答案】 100，不一定是稀疏矩阵。19 【正确答案】 使用深度优先遍历，按退出 dfs 过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行 dfs(v)未退出前，出现顶点 u 到 v 的回边，则说明存在

15、包含顶点 v 和顶点 u 的环。20 【正确答案】 如右图。21 【正确答案】 开始结点： (入度为 0)K1，K 2，终端结点(出度为 0)K6，K 7.22 【正确答案】 拓扑序列 K1，K 2，K 3，K 4，K 5， K6，K 8，K 9，K 7 K2，K 1，K 3，K 4，K 5，K 6，K 8，K 9，K 7 规则：开始结点为 K1 或 K2，之后，若遇多个人度为 0 的顶点，按顶点编号顺序选择。23 【正确答案】 邻接表和逆邻接表24 【正确答案】 图 G 的具体存储结构略。对于邻接矩阵表示法，有 n 个顶点的图占用 n2 个元素的存储单元，与边的个数无关，当边数较少时，存储效

16、率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有 n(n0)个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边(弧)也很方便，但因指针多占用了存储空间。 另外，某两顶点间是否有边(弧)也不如邻接矩阵那么直观。对有向图的邻接表，查顶点出度容易，而查顶点入度却很困难，要遍历整个邻接表。要想查入度也像查出度那样容易，就要建立逆邻接表。无

17、向图邻接表中边结点是边数的二倍，这也增加了存储量。十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息(至少弧尾、弧头顶点在向量中的下标及指向弧头相同和弧尾相同的下一条弧的指针四个信息)。查询顶点的出度、入度、邻接点等信息非常方便。邻接多重表是无向图的另一种存储结构，边结点至少包括 5 个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息(如该边是否被访问)。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。25 【正确答案】 已知顶点 i，找与 i 相邻的顶点 j 的规则如下：在顶点向量中，找到顶点 i,顺其指针找到第一个边结点(若其指针为空，则顶点 i 无邻接点)。在边结点中，取出两顶点信息，若其中有 j，则找到顶点 j；否则，沿从 i 发出的另一条边的指针(ilink)找 i 的下一邻接点。在这种查找过程中，若边结点中有 j，则查找成功，若最后 ilink 为空，则顶点 i 无邻接点 j。26 【正确答案】 遍历起始顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。27 【正确答案】 栈和队列，广度优先遍历