图练习：
1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列
B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n
5．n个结点的完全有向图含有边的数目（）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。
A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A．1/2 B．2 C．1 D．4
8. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度
遍历是一个递归过程
9．无向图G=(V,E),其中：
V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图
进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
10. 关键路径是事件结点网络中（）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（）
2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）
3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=。（）
4. 有e条边的无向图，在邻接表中有e个结点。（）
5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）
6．强连通图的各顶点间均可达。（）
7．邻接多重表是无向图和有向图的链式存储结构。（）
8. 十字链表是无向图的一种存储结构。（）
9．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）10．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零
元素之和的一半。（）
11. 有向图的邻接矩阵是对称的。（）
12．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）
13. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）
14. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）
15. 广度遍历生成树描述了从起点到各顶点的最短路径。（）
16．任何无向图都存在生成树。（）
17. 不同的求最小生成树的方法最后得到的生成树是相同的.（）
18．带权无向图的最小生成树必是唯一的。（）
19. 最小代价生成树是唯一的。（）
20．一个网（带权图）都有唯一的最小生成树。（）
21．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）22．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（）23．带权的连通无向图的最小代价生成树是唯一的。（）
24. 最小生成树问题是构造连通网的最小代价生成树。（）
三、填空题
1.判断一个无向图是一棵树的条件是______。
2．有向图G的强连通分量是指______。
3．一个连通图的______是一个极小连通子图。
4．具有10个顶点的无向图，边的总数最多为______。
5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。
6. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______
7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
9．在有n个顶点的有向图中，每个顶点的度最大可达______。
10．设G为具有N个顶点的无向连通图，则G中至少有______条边。
11．n个顶点的连通无向图，其边的条数至少为______。
12．如果含n个顶点的图形形成一个环，则它有______棵生成树。
13．N个顶点的连通图的生成树含有______条边。
14．构造n个结点的强连通图，至少有______条弧。
15．有N个顶点的有向图，至少需要量______条弧
才能保证是连通的。
16．右图中的强连通分量的个数为（
17．N个顶点的连通图用邻接矩阵表示时,该矩阵
至少有_______个非零元素。
18．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说
等于该顶点的______；对于有向图来说等于该顶点的______。
19. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。
20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为
______，邻接表的边结点个数为______。
21. 已知一无向图G=（V，E），其中V={a,b,c,d,e }
E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历
图，得到的序列为abecd，则采用的是______遍历方法。
答案：
1.有n个顶点，n-1条边的无向连通图
2.有向图的极大强连通子图
3. 生成树
4. 45
5. n(n-1)/2 6 .
7. 9 8. n
9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n
15. N
16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e
22. 深度优先 23.宽度优先遍历
四、应用题
1．（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？
（2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？
（3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？
2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？3．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。
4．给出图G：
（1）．画出G的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。5．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有
哪些？
6．考虑下图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，求它的最小生成树从A点开始
（4）根据kruskal 算法，求它的最小生成树
7．考虑下图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，求它的最小生成树从1点开始
（4）根据kruskal 算法，求它的最小生成树
答案：
1．（1）G1最多n(n-1)/2条边，最少n-1条边
(2) G2最多n(n-1)条边，最少n条边
(3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的)
2．n-1，n
3．深度优先遍历序列：125967384
宽度优先遍历序列：123456789
注：（1）邻接表不唯一，这里顶点的邻接点按升序排列
（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一
（3）这里的遍历，均从顶点1开始
4.略
5.遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
6．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列
(1)ABGFDEC (2)EACFBDG
7.略
选择是难，更何况是心灵选择。高渐离为了荆轲，他选择了死；马本斋母亲为了革命，她选择了牺牲；祝英台为了真挚爱情，她选择了化蝶。在这友情、亲情与爱情之间选择，他们是这样做
图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度
⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。
1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧
关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）
第8次作业参考答案 1、请回答 （1）n 个顶点的无向连通图至少有多少条边？ （2）n 个顶点的有向强连通图至少有多少条边？ （3）试分别举例画图说明。 参考答案： （1）当n=1时，n 个顶点的无向连通图至少有0条边；当n>1时，至少有n-1条边。 （2）当n=1时，n 个顶点的有向强连通图至少有0条边；当n>1时，至少有n 条边。 2、对于有n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题(想法描述)： （1）图中有多少条边？ （2）任意两个顶点i 和j 之间是否有边相连？ （3）任意一个顶点的度是多少？ 参考答案： （1）若有n 个非零值，则边为n/2条边。 （2）设邻接矩阵为A ，若aij=1，则i,j 有边直接相连；若aik=1和akj=1，则顶点i 和顶点j 经过k 有边直接相连。 （3）统计以该点为行的非零元素个数。 3、已知一个无向图的邻接表如下图所示，要求： (1) 画出该无向图； (2) 根据邻接表，分别写出用DFS 和BFS 算法从顶点V0开始的遍历该图后所得到的遍历序列，并画出DFS 生成树和BFS 生成树。 参考答案： (1) 该无向图如下图(a)所示 (2) 根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0 V2 V3 V1 V4 V6 V5，其相应的DFS 生成树如下图(b)所示；其广度优先遍历序列为：V0 V2 V5 V6 V1 V3 V4，其相应的BFS 生成树如下图(c)所示。 2 ∧ V1 3 0 4 V0 2 5 6 V2 0 3 6 V3 1 2 4 ∧ V4 1 V5 0 V6 2 5 0 ∧ 3 ∧ 6 ∧ 1 ∧ 1 ∧
数据结构图练习题 数据结构图练习题 在计算机科学领域中，数据结构是一种用来组织和存储数据的方式。而图是一 种常见的数据结构，它由一组节点和连接这些节点的边组成。图可以用来表示 各种各样的关系，比如社交网络中的用户关系、城市之间的道路网络等等。在 本文中，我们将探讨一些与图相关的练习题，帮助读者更好地理解和应用图的 概念。 1. 最短路径问题 最短路径问题是图论中的经典问题之一。给定一个带权重的有向图，我们需要 找到从一个起始节点到目标节点的最短路径。这里的权重可以表示为距离、时 间或者其他度量。解决这个问题的算法有很多，其中最著名的是Dijkstra算法 和Bellman-Ford算法。读者可以尝试使用这些算法来解决一些具体的实例，比 如计算两个城市之间的最短路径。 2. 拓扑排序 拓扑排序是对有向无环图(Directed Acyclic Graph，简称DAG)进行排序的一种算法。在一个DAG中，节点之间存在一种偏序关系，即某些节点必须在其他节点之前进行处理。拓扑排序可以帮助我们确定这种偏序关系，从而找到一种合理 的处理顺序。比如，在编译器中，拓扑排序可以用来确定源代码中各个函数的 调用顺序。读者可以尝试编写一个拓扑排序算法，并应用到一些具体的场景中。 3. 最小生成树 最小生成树是一个无向连通图中一棵权值最小的生成树。在一个连通图中，最 小生成树可以帮助我们找到一种最优的连接方式，以满足一些约束条件。最常
用的算法是Prim算法和Kruskal算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个城市之间建设光纤网络，以最小的成本实现全覆盖。4. 图的遍历 图的遍历是指按照某种方式访问图中的所有节点。常见的遍历算法有深度优先 搜索(DFS)和广度优先搜索(BFS)。DFS通过递归地访问每个节点的邻居节点，直 到所有节点都被访问完。BFS则通过队列来实现，先访问起始节点的邻居节点，然后依次访问它们的邻居节点，直到所有节点都被访问完。读者可以尝试实现 这两种遍历算法，并观察它们的不同特点。 5. 最大流问题 最大流问题是图论中的一个经典问题，它可以用来解决一些网络流的优化问题。在一个有向图中，每条边都有一个容量，表示通过这条边的最大流量。最大流 问题的目标是找到从源节点到汇节点的最大流量。常用的解决方法是Ford-Fulkerson算法和Edmonds-Karp算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个供水网络中确定最大供水量。 通过以上的练习题，读者可以更好地理解和应用图的概念。图作为一种重要的 数据结构，广泛应用于计算机科学领域的各个方面。掌握图的基本概念和算法，对于解决实际问题和提高编程能力都有很大的帮助。希望读者能够通过练习和 实践，深入理解图的特性，并能够灵活运用它们解决各种问题。
数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧
(4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径
一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在 5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、1/2 B、1 C、2 D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、1/2 B、1 C、2 D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（） A、(n+1)*(n-1) B、(n-1)*(n-1) C、n D、n*n 11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1 C、n-1 D、n+e (2)A、e/2 B、e C、2e D、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（） A、求关键路径的方法 B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀疏图G，则G采用（邻接表）存储较省空间。 3、设有一稠密图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I 行）。 6、图的深度优先遍历序列（不是）唯一的。 7、n个顶点e条边的图，若用邻接表存储，深度优先遍历算法的时间复杂度为（n+e）。
习题7 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b
数据结构(树与图部份)练习题 一、填空题 1.不考虑顺序的3个结点可组成种不同形态的树，种不同形态的二叉树。 2.已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数 为：。 3.已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。 4.一棵具有110个结点的完全二叉树，若i＝54，则结点i的双亲编号是；结点i 的左孩子结点的编号是，结点i的右孩子结点的编号是。 5.一棵具有48个结点的完全二叉树，若i＝20，则结点i的双亲编号是______；结点i的 左孩子结点编号是______，右孩子结点编号是______。 6.在有n个叶子结点的Huffman树中，总的结点数是：______。 7.图是一种非线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的非空有限 集合，E(G)是______的有限集合。 8.遍历图的大体方式有优先搜索和优先搜索两种方式。 9.图的遍历大体方式中是一个递归进程。 10.n个极点的有向图最多有条弧；n个极点的无向图最多有条边。 11.在二叉树的二叉链表中，判断某指针p所指结点是叶子结点的条件是。 12.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于。 二、单项选择题 1.树型结构的特点是：任意一个结点：（） A、可以有多个直接前趋 B、可以有多个直接后继 C、至少有1个前趋 D、只有一个后继
2. 如下图所示的4棵二叉树中，（ ）不是完全二叉树。 A B C D 3. 深度为5的二叉树最多有（ ）个结点。 A 、16 B 、32 C 、31 D 、10 4. 64个结点的完全二叉树的深度为：（ ）。 A 、8 B 、7 C 、6 D 、5 5. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行 编号，根结点编号为1，则编号为49的结点的左孩子的编号为：（ ）。 A 、98 B 、99 C 、50 D 、48 6. 在一个无向图中，所有极点的度之和等于边数的（ ）倍。 A 、1/2 B 、1 C 、2 D 、4 7. 设有13个值，用它们组成一棵Huffman 树，则该Huffman 树中共有( )个结点。 A 、13 B 、12 C 、26 D 、25 8. 若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x ，它的双亲结 点及右孩子结点的编号别离为( )。 A 、2,14 B 、2,15 C 、3,14 D 、3,15 9. 若对一棵有20个结点的完全二叉树按层编号，则对于编号为5的结点x ，它的双亲结 点及左孩子结点的编号别离为( )。 A 、2,11 B 、2,10 C 、3,9 D 、3,10 10. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行 编号，根结点编号为1，则编号最大的非叶结点的编号为： A 、48 B 、49 C 、50 D 、51 11. 无向图的邻接矩阵是一个( )。 A 、对称矩阵 B 、零矩阵 C 、上三角矩阵 D 、对角矩阵 12. 由64个结点组成的完全二叉树，其深度为：( )。 A 、8 B 、7 C 、6 D 、5 13. 若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x ，它的双亲结 点及右孩子结点的编号别离为( )。 A 、2,14 B 、2,15 C 、3,14 D 、3,15 14. 图示二叉树的中序遍历序列是：（ ）
数据结构练习题(含答案)数据结构练习题(含答案) 一、单项选择题 1. 在数组中插入和删除元素最慢的时间复杂度是： A. O(1) B. O(log n) C. O(n) D. O(n^2) 答案：C 2. 在链表中插入和删除元素最慢的时间复杂度是： A. O(1) B. O(log n) C. O(n) D. O(n^2) 答案：A 3. 下列哪种数据结构采用了“先进先出”的存储方式： A. 栈 B. 队列
D. 二叉树 答案：B 4. 下列哪种数据结构采用了“先进后出”的存储方式： A. 栈 B. 队列 C. 哈希表 D. 二叉树 答案：A 5. 以下哪种排序算法的时间复杂度最好： A. 冒泡排序 B. 插入排序 C. 快速排序 D. 选择排序 答案：C 二、填空题 1. 假设有一个长度为10的数组arr，要访问第7个元素，应该使用arr[]表示。
2. 栈的特点是后进先出，所以从栈中取出第一个元素需要调用的操作是。 答案：pop 3. 结点的度可以理解为： 答案：与该结点相连的边的数目 4. 图中的结点称为： 答案：顶点 5. 在二叉树中，度为 2 的结点称为。 答案：内部结点 三、编程题 1. 使用Python编写代码，实现冒泡排序算法，并对以下数组进行排序：[5, 2, 9, 1, 3, 6, 8, 7, 4] 答案： ```python def bubble_sort(arr): n = len(arr) for i in range(n):
for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] arr = [5, 2, 9, 1, 3, 6, 8, 7, 4] bubble_sort(arr) print(arr) ``` 2. 使用Java编写代码，实现队列的基本操作：入队（enqueue）、出队（dequeue）、查看队首元素（peek）。 答案： ```java import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { Queue
数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 数据结构习题 第七章图 一、选择题 1、一个有n个顶点的无向图最多有（ C ）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有4个顶点的无向完全图有（ A ）条边。 A、6 B、12 C、16 D、20 3、具有6个顶点的无向图至少有（ A ）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 4、设连通图G的顶点数为n，则G的生成树的边数为（ A ）。 A、n-1 B、n C、2n D、2n-1 5、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ D ）和（ B ） （1）A、abecdf B、acfebd C、acebfd D、acfdeb （2）A、abcedf B、abcefd C、abedfc D、acfdeb 6、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ B ）和（ D ）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 7、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ C ）和（ B ）。 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2 8、已知一个图如下，在该图的最小生成树中各边上权值之和为（ C ），在该图的最小生成树中，从v1到v6的路径为（ G ）。 A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6 9、正确的AOE网必须是（ C ） A、完全图 B、哈密尔顿图 C、无环图 D、强连通图 10、已知一个图如下，则由该图得到的一种拓扑序列为（ A ）。 A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5 11、下面结论中正确的是（ B ） A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。 E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右 子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A ．不确定 B ．2n C ．2n+1 D ．2n-1 7．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 8. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ） A ．?logn ?+1 B ．logn+1 C ．?logn ? D ．logn-1 9．深度为h 的满m 叉树的第k 层有（ A ）个结点。(1= 1、假设一棵二叉树的层序序列是ABCDEFGHIJ 和中序序列是DBGEHJACIF,请画出该树。 21、有一个完全二叉树按层次顺序存放在一维数组中，如下所示： 请指出结点P 的父结点，左子女，右子女。 3、给出下列二叉树的先序序列。 4、已知二叉树的先序遍历序列为ABCDEFGH ，中序遍历序列为CBEDFAGH ，画出二叉树。 答案：二叉树形态 A F H G D E C B （2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林）。 A B F D ( C E H G (1) (2) 1、已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。 i.写出该二叉树的后序序列； ii.画出该二叉树； iii.求该二叉树的高度(假定空树的高度为－1)和度为2、度为1、及度为0的结点个数。 该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。 该二叉树的形式如图所示： 该二叉树高度为：5。 度为2的结点的个数为：3。 度为1的结点的个数为：5。 度为0的结点个数为：4。 5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 答案： 2 1 5 6 1118 73 4 12 30 WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69 6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL 。 答案：(1)树形态： 3 2 5 5 1019 9 7 6 13 32 (2)带权 路 径 长 度 ： WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79 （3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 ① 试为这8个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32 （100） （40） （60） 19 21 32 （28） （） （11） 7 10 6 （5） 图练习： 1．图中有关路径的定义是（）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 8. 下列说法不正确的是（）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度 遍历是一个递归过程 9．无向图G=(V,E),其中： V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图 进行深度优先遍历，得到的顶点序列正确的是（）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 10. 关键路径是事件结点网络中（）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 一、单选题 1、树最适合用来表示（）。 A.元素之间具有分支层次关系的数据 B.有序数据元素 C.元素之间无联系的数据 D.无序数据元素 正确答案：A 2、在树结构中，若结点A有三个兄弟，且B是A的双亲，则B的度是（）。 A.5 B.4 C.3 D.2 正确答案：B 3、下列陈述中正确的是（）。 A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中每个结点最多只有两棵子树，并且有左右之分 D.二叉树中必有度为2的结点 正确答案：C 4、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至少为（）。 A.2h-1 B.2h+1 C.h+1 D.2h 正确答案：A 解析： A、除根之外，每层只有两个结点，且互为兄弟。 5、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至多为（）。 A.2h-1 B. 2h+1-1 C. 2h-1-1 D. 2h+1 正确答案：A 解析： A、构成完全二叉树。 6、具有n(n>0)个结点的完全二叉树的深度为（）。 A.⌊ log2(n)⌋ +1 B.⌈log2(n)⌉ C.⌊ log2(n)⌋ D.⌈log2(n)+1⌉ 正确答案：A 7、具有32个结点的完全二叉树有（）个叶子结点。 A.16 B.14 C.15 D.17 正确答案：A 解析： A、对结点按层序编号，32号结点的双亲结点编号为16，则17至32号结点都为叶子，共16个。 8、一棵完全二叉树的第6层上有23个叶子结点，则此二叉树最多有（）结点。 A.81 B.78 C.80 D.79 正确答案：A 解析： A、完全二叉树的叶子结点只能在最下两层，要使结点最多，这棵二叉树深度 为7，前6层结点数共为63，第6层有32个结点，其中叶子为23个，非叶子为9个，它们的度都为2，第7层只有18个结点，故整棵二叉树结点数为81. 9、具有3个结点的二叉树有（）种。 A.6 B.3 C.5 D.4 正确答案：C 10、若一棵二叉树有9个度为2的结点，5个度为1的结点，则叶子结点的个数为（）。 A.15 B.10 C.9 D.不确定 正确答案：B 11、一棵二叉树有35个结点，则所有结点的度之和为（）。 A.16 B.35 C.34 D.33 正确答案：C 12、二叉树是非线性数据结构，所以（）。 A.顺序存储结构和链式存储结构都能存储 B.顺序结构和链式结构都不能使用 C.它不能用链式存储结构存储 图练习： 1．图中有关路径的定义是〔〕。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有〔〕条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为〔〕。 A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要〔〕条边。 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目〔〕。 A．n*n Ｂ．n〔n＋１〕 C．n／2 D．n*〔n－l〕6．一个有n个结点的图，最少有〔〕个连通分量，最多有〔〕个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数〔〕倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的〔〕倍。 A．1/2 B．2 C．1 D．4 8. 以下说法不正确的选项是〔〕。 A．图的遍历是从给定的源点出发每一个顶点仅被一次 C．图的深度遍历不适用于有向图 B．遍历的根本算法有两种：深度遍历和广度遍历 D．图的深度 遍历是一个递归过程 9．无向图G=(V,E),其中： V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图 进展深度优先遍历，得到的顶点序列正确的选项是〔〕。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 10. 关键路径是事件结点网络中〔〕。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 二、判断题 1.树中的结点和图中的顶点就是指数据构造中的数据元素。〔〕 2．在n个结点的无向图中，假设边数大于n-1,则该图必是连通图。〔〕 3．对有n个顶点的无向图，其边数e与各顶点度数间满足以下等式e=。〔〕 4. 有e条边的无向图，在邻接表中有e个结点。〔〕 5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。〔〕 6．强连通图的各顶点间均可达。〔〕 7．邻接多重表是无向图和有向图的链式存储构造。〔〕 8. 十字链表是无向图的一种存储构造。〔〕 9．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。〔〕 10．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零 元素之和的一半。〔〕 11. 有向图的邻接矩阵是对称的。〔〕 12．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 〔〕 数据结构练习第七章图 一、选择题 1.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 2. 设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 3．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。 A. n-1 B. n C. n+1 D. 2n-1 4．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。 A. n，e B e，n C 2n，e D n，2e 5．设某强连通图中有n个顶点，则该强连通图中至少有（）条边。 A. n(n-1) B. n+1 C. n D. n(n+1) 6．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。 A .n B. e C. 2n D. 2e 7．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 A. n B. n-1 C. m D. m-1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d， f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。 A. abedfc B. acfebd C. aebdfc D. aedfcb 9．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。 A. O(n+e) B. O(n2) C. O(ne) D. O(n3) 10．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 A. 第i行非0元素的个数之和 B.第i列非0元素的个数之和 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和 11．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。 A. 2n B. n C. n/2 D. n(n-1) 12．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。 A. n B. n-1 C. 2n D. 2n-1 13．设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 C．0 14．设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。 A. 1，2，3，4 B. 2，3，4，1 C. 1，4，2，3 D. 1，2，4，3 15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。A．n B．2n C．n-1 D．n+1 16．在一个图中，所有顶点的度数之和等于所有边数的（）倍。 A．2 B．1 C．3 D．4数据结构第7章图习题
数据结构 图 作业及部分答案
数据结构第6章 树习题+答案
数据结构应用题练习
数据的结构图练习
数据结构(树)习题与答案
数据结构图练习试题
数据结构练习_第七章_图
相关主题
文本预览