数据结构1800题和答案第7章 图

数据结构（C语言版）1800道题及答案[完整版]数据结构(C语言版)1800道题及答案[完整版]数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B．复杂性 C．现实性 D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所 1998 二、1 （2分）】A．问题的规模 B．待处理数据的初态 C．A和B D．都不是3．计算机算法指的是（① C ），它必须具备（② B ）这三个特性。

① A．计算方法B．排序方法C．解决问题的步骤序列 D．调度方法② A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（ B ）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D ）。

第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。

7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。

在遍历中若发现顶点j，则说明顶点i和j间有路径。

{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。

设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。

第7章 图 自测卷解答 姓名 班级一、单选题（每题1分，共16分） 前两大题全部来自于全国自考参考书！（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6 （ ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6 （建议：0 1 2 3 4 5 6） （ C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D. 0 3 6 1 5 4 2建议：先画出图，再深度遍历⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110（ A ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发不是深度优先遍历的结点序列是A．0 1 3 2 B. 0 2 3 1C. 0 3 2 1D. 0 1 2 3（A）14. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）15. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）16. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

习题参考答案习题7一．（1）有向图——在一个图中，如果每条边都有方向，则称该图有向图。

（2）无向图——在一个图中，如果每条边都没有方向，则称该图为无向图。

（3）完全有向图——在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。

（在一个含有n 个顶点的有向完全图中，有n (n-1) 条弧。

）（4）最小生成树——若无向连通图是一个网，则它的所有生成树中必有一棵边的权值之和为最小的生成树，简称为最小生成树。

二．（1）√ （2）√ （3）ㄨ （4）√ （5）ㄨ （6）ㄨ （7）√ （8）ㄨ 三．（1） 邻接矩阵 邻接表 深度优先遍历 广度优先遍历（2） 没有 2n （3） 有 弧 （4） 顶点 （5） 出度（6） O(n 2) （7） 邻接表 邻接矩阵 （8） 有向 （9） 不是 （10）O(n 2) （11）n （n-1）/2 （12）全部 四．（1） C （2） B 3） B 4） C （5） C （6） B （7） A （8） A （9） D （10）A （11） B （12）D 五．简答题1．解（1）邻接矩阵 （2）邻接表1 2 3 4 5⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0100000001100000100010110543212从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 34 5 （不惟一）。

从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3 （不惟一）。

3．解（1） （2）深度优先搜索：a b d c e （或a b d e c ）广度优先搜索：a b e d c4．解习题8一．（1）查找——查找有称为检索，是在一批记录中按某个域的镇定域值，找出相应记录的操作。

（2）散列函数——根据关键字值求存储地址的函数称为散列函数（也称为哈希函数）（3）冲突——两个不同的关键字，其散列函数值相同，因而得到同一个表的相同地址的现象称为冲突。

（即经过Hash函数换算后，每个存储地址出现了存放两个以上标识符的现象，因而导致数据丢失称为冲突） （4）平衡因子——二叉排序树中每个结点的左子树的高度减去右子树的高度称为该结点的平衡因子。

数据结构第七章的习题答案数据结构第七章的习题答案数据结构是计算机科学中非常重要的一门学科，它研究如何组织和管理数据以便高效地访问和操作。

第七章是数据结构课程中的一个关键章节，它涵盖了树和二叉树这两个重要的数据结构。

本文将为读者提供第七章习题的详细解答，帮助读者更好地理解和掌握这些概念。

1. 问题：给定一个二叉树，如何判断它是否是二叉搜索树？解答：要判断一个二叉树是否是二叉搜索树，我们可以使用中序遍历的方法。

中序遍历会按照从小到大的顺序访问二叉树中的节点。

所以，如果一个二叉树是二叉搜索树，那么它的中序遍历结果应该是一个有序的序列。

具体实现时，我们可以使用递归或者迭代的方式进行中序遍历，并将遍历的结果保存在一个数组中。

然后，我们检查这个数组是否是有序的即可判断二叉树是否是二叉搜索树。

2. 问题：给定一个二叉树，如何找到它的最大深度？解答：要找到一个二叉树的最大深度，我们可以使用递归的方式。

对于每个节点，它的最大深度等于其左子树和右子树中的最大深度加1。

递归的终止条件是节点为空，此时深度为0。

具体实现时，我们可以定义一个递归函数，该函数接收一个节点作为参数，并返回以该节点为根节点的子树的最大深度。

在递归函数中，我们先判断节点是否为空，如果为空则返回0；否则，我们分别计算左子树和右子树的最大深度，然后取两者中的较大值加1作为当前节点的最大深度。

3. 问题：给定一个二叉树，如何判断它是否是平衡二叉树？解答：要判断一个二叉树是否是平衡二叉树，我们可以使用递归的方式。

对于每个节点，我们分别计算其左子树和右子树的高度差，如果高度差大于1，则该二叉树不是平衡二叉树。

具体实现时，我们可以定义一个递归函数，该函数接收一个节点作为参数，并返回以该节点为根节点的子树的高度。

在递归函数中，我们先判断节点是否为空，如果为空则返回0；否则，我们分别计算左子树和右子树的高度，然后取两者中的较大值加1作为当前节点的高度。

最后，我们判断左子树和右子树的高度差是否大于1，如果大于1，则该二叉树不是平衡二叉树。

一、选择题1、有6个结点的有向完全图有（）条弧。

A、36B、28C、30D、152、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。

A、栈B、队列C、树D、图3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。

A、栈B、队列C、树D、图4、任何一个无向连通图的最小生成树（）A、只有一棵B、一棵或多棵C、一定有多棵D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。

A、1/2B、1C、2D、46、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A、1/2B、1C、2D、47、一个有n个顶点的无向图最多有（）条边。

A、nB、n(n-1)C、n(n-1)/2D、2n8、具有5个顶点的无向完全图有（）条边。

A、6B、8C、10D、209、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。

A、nB、n+1C、n-1D、n/210、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、nD、n*n11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（）(1)A、n B、n+1 C、n-1 D、n+e(2)A、e/2 B、e C、2e D、n+e12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）A、先序遍历B、中序遍历C、后序遍历D、按层遍历13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）A、先序遍历B、中序遍历C、后序遍历D、按层遍历14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法C、宽度优先遍历算法D、深度优先遍历算法15、关键路径是AOE网中的（）A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最短的回路D、活动的最早开始时间与最迟发生时间相等二、填空题1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。

第7章图部分答案解释如下。

2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上权值之和相等26. 是自由树，即根结点不确定35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。

42. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。

45. 能求出关键路径的AOE网一定是有向无环图46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩短工期。

48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。

自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

三．填空题1.有n个顶点，n-1条边的无向连通图2.有向图的极大强连通子图3. 生成树4. 455. n(n-1)/2 6 . 7. 9 8. n9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n15. N16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同(5)队列和栈22. 深度优先 23.宽度优先遍历 24.队列25.因未给出存储结构，答案不唯一。

本题按邻接表存储结构，邻接点按字典序排列。

25题（1） 25题（2）26.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法 27.克鲁斯卡尔28.边稠密边稀疏 29. O(eloge）边稀疏 30.O(n2） O(eloge)31.(1）（V i，V j）边上的权值都大的数（2）1 负值（3）为负边32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增负值35.16036.O(n2） 37. 50，经过中间顶点④ 38. 75 39.O(n+e）40.(1）活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间41.关键路径 42.（1）某项活动以自己为先决条件（2）荒谬（3）死循环43.（1）零（2）V k度减1，若V k入度己减到零，则V k顶点入栈（3）环44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout(5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti(9)p<>nil (10)p^.vexj=j(11)firstadj(g,v0) (12)not visited[w] (13)nextadj(g,v0,w)46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1(8)indegree[i]==047.(1)p^.link:=ch[u].head (2)ch[u].head:=p (3)top<>0 (4)j:=top(5)top:=ch[j].count(6)t:=t^.link48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。

第七章图
1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索
算法写出从C开始的深度优先搜索序列。

0A13^
1B35^
2C30^
3D4^
4E^
5F4^
【解答】
A B F
C D E
C开始的深度优先搜索序列：CDEABF（唯一的结果）
2．假定要在某县所辖六个镇（含县城）之间修公路，若镇I和镇J之间有可能通
过道路连接，则Wij表示这条路的长度。

要求每个镇都通公路且所修公路总里程
最短，那么应选择哪些线路来修。

I11112233445 J23564546566 W ij1239102626474
(1).画出该图。

(2).用C语言描述该图的数组表示法存储结构，并注明你所使用变量的实际含义。

(3).图示你所定义的数据结构。

(4).标识出你选择的线路。

【解答】
（1）
（2）
#define MAX 6
char vexs[MAX];
出该图的所有强连通分量。

(2).在图中删除弧<2,1>，然后写出从顶点1开始的拓扑有序序列。

【解答】
(1) 共4个强连通分量：
(2) 1,3,2,6,5,4
5 4
6 1 3 2
4
15 10
2
15 20 30 4 10
10。

数据结构习题参考答案第一章答案一、填空题1．数据元素，数据项2． O(1)，O(n)，O(log 2n)，O(n 2)3．线性结构，非线性结构，顺序结构，链式结构4．无，一，无，一5．前驱，一，无，任意6．任意7． O(n 1/2)8.O(1)<o(2n<="") 第二章答案一、填空题1． n/2，(n-1)/2分析：当在顺序线性表中的第i （1<=i<=n+1）个位置之前插入一个新元素时，从第i 个元素起向后的n+1-i 个元素均要向后移动一个位置。

因此在等概率情况下，插入操作中元素的平均移动次数为∑+==-++=112)1(11)(n i ni n n n f ；当在顺序线性表中删除第i （1<=i<=n ）个位置上的元素，从第i+1个元素起向后的n-i 个元素均要向前移动一个位置。

因此在等概率情况下，删除操作中元素的平均移动次数为∑=-=-= n i n i n n n f 121)(1)(。

2．向后3．向前4．指针域5．一定，不一定6． O(n)7． O(n)8．消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。

9．前驱，后继10．O(n)二、填空题1． (1)2． (1)3． (4)4． (2)5． (2)6． (4)7． (4)8． (1)9． (4)10．(1)11．(2)12．(3)第三章参考答案一、填空题1．线性，任何，栈顶，队尾，队头2．先进后出（FILO ），队尾，队头，先进先出（FIFO ）3． top==0，top==m4． 235415．前一个位置，所在位置，m-1分析：在顺序循环队列中约定头指针front 和尾指针rear 所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。

6． (rear+1)%m==front ，rear==front7． O(1)8．返回地址，返回地址二、选择题1.(3) 2.(3) 3.(3) 4. (2)5. (2)6. (3)7. (1)8. (4)因为：顺序循环队列中的元素个数=??<+-≥-front rear m front rear front rear front rear ，整理合并可写成(rear-front+m)%m 。