数据结构-图习题介绍

7.1 选择题1. 对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为()A) O(n)B)O(n+e)C) O(n*n)D)O(n*n*n)【答案】B2. 设无向图的顶点个数为n,则该图最多有()条边。

A) n-1B)n(n-1)/2C)n(n+1)/2【答案】B3. 连通分量指的是()A) 无向图中的极小连通子图B) 无向图中的极大连通子图C) 有向图中的极小连通子图D) 有向图中的极大连通子图【答案】B4. n 个结点的完全有向图含有边的数目()A) n*n B) n(n+1) C) n/2【答案】D5. 关键路径是()A) AOE网中从源点到汇点的最长路径B) AOE网中从源点到汇点的最短路径C) AOV网中从源点到汇点的最长路径D) n2D) n* (n-1)D) AOV网中从源点到汇点的最短路径【答案】 A 6．有向图中一个顶点的度是该顶点的()A)入度B)出度C)入度与出度之和D)(入度+出度)12【答案】C7．有e 条边的无向图，若用邻接表存储，表中有()边结点。

A) e B) 2eC) e-1D) 2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为()A)栈B)队列C)二叉树D)树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为()A)栈B)队列C)二叉树D)树【答案】 A 10．存储无向图的邻接矩阵一定是一个()A)上三角矩阵B)稀疏矩阵C)对称矩阵D)对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的()倍A) B) 1C) 2D) 4答案】B12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为(A) O(n)B) O(n+e)C 0(n2)D) 0(n3))【答案】B13 .下列关于AOE网的叙述中，不正确的是()A) 关键活动不按期完成就会影响整个工程的完成时间B) 任何一个关键活动提前完成，那么整个工程将会提前完成C) 所有的关键活动提前完成，那么整个工程将会提前完成D) 某些关键活动提前完成，那么整个工程将会提前完成【答案】B14. 具有10 个顶点的无向图至少有多少条边才能保证连通()A ) 9B) 10C) 11D) 12【答案】A15. 在含n 个顶点和e 条边的无向图的邻接矩阵中，零元素的个数为()A)e B)2eC)n2-e D)n2-2e【答案】D7.2 填空题1 .无向图中所有顶点的度数之和等于所有边数的________________ 倍。

《数据结构》期末复习题及参考答案- 第7章图//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 注意：做复习题时，请结合阅读教材，钻研教材，参考课件////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、以下数据结构中，哪种具有非线性结构？A．栈B．队列C．双向链表D．十字链表2、下面关于图的存储的叙述中正确的是（）。

A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。

C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。

D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历4、图的广度优先遍历算法类似于树的（）。

A. 中根遍历B. 先根遍历C. 后根遍历D. 按层次遍历5、设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．06、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A．n-1 B．n C．n+1 D．nlogn；7、一个含有n个顶点的非连通图，则（）：A．它的边一定不大于n-1 B．它的边一定不大于nC．它的边一定小于n-1 D．它的边一定大于08、要连通具有n个顶点的有向图，至少需要（）条边。

图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组成的图进行拓扑排序。

习题七图一、单项选择题1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（）A．G’为G的子图 B．G’为G的连通分量C．G’为G的极小连通子图且V’=V D．G’是G的无环子图2.任何一个带权的无向连通图的最小生成树（）A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在3．以下说法正确的是（）A．连通分量是无向图中的极小连通子图。

B．强连通分量是有向图中的极大强连通子图。

C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。

D．对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。

4．图中有关路径的定义是（）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是5．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n26．要连通具有n个顶点的有向图，至少需要（）条边。

A．n-l B．n C．n+l D．2n7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

A．1/2 B．2 C．1 D．48．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图 B．无向图 C．AOV网 D．AOE网9. 下列说法不正确的是（）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程10．下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径11. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

数据结构习题第七章图一、选择题1、一个有n个顶点的无向图最多有（ C ）条边。

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

A、6B、12C、16D、203、具有6个顶点的无向图至少有（ A ）条边才能保证是一个连通图。

A、5B、6C、7D、84、设连通图G的顶点数为n，则G的生成树的边数为（ A ）。

A、n-1B、nC、2nD、2n-15、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ D ）和（B ）（1）A、abecdf B、acfebd C、acebfd D、acfdeb（2）A、abcedf B、abcefd C、abedfc D、acfdeb6、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ B ）和（ D ）。

A、中序遍历B、先序遍历C、后序遍历D、层次遍历7、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ C ）和（ B ）。

A、v1,v2,v3,v4,v5B、v1,v3,v2,v4,v5C、v1,v2,v3,v5,v4D、v1,v4,v3,v5,v28、已知一个图如下，在该图的最小生成树中各边上权值之和为（ C ），在该图的最小生成树中，从v1到v6的路径为（G ）。

A、31B、38C、36D、43E、v1,v3,v6F、v1,v4,v6G、v1,v5,v4,v6H、v1,v4,v3,v69、正确的AOE网必须是（C ）A、完全图B、哈密尔顿图C、无环图D、强连通图10、已知一个图如下，则由该图得到的一种拓扑序列为（ A ）。

A、v1,v4,v6,v2,v5,v3B、v1,v2,v3,v4,v5,v6C、v1,v4,v2,v3,v6,v5D、v1,v2,v4,v6,v3,v511、下面结论中正确的是（ B ）A、在无向图中，边的条数是顶点度数之和。

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

第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作： InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为eIsAscending(C)操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

05 图【单选题】1. 设无向图G 中有五个顶点，各顶点的度分别为2、4、3、1、2，则G 中边数为（C ）。

Ａ、4条 Ｂ、5条 Ｃ、6条 Ｄ、无法确定2. 含n 个顶点的无向完全图有（D ）条边；含n 个顶点的有向图最多有（C ）条弧；含n 个顶点的有向强连通图最多有（C ）条弧；含n 个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n 个顶点，则要接通全部顶点至少需（G ）条边。

A 、n 2B 、n(n+1)C 、n(n-1)D 、n(n-1)/2E 、n+1F 、nG 、n-13. 对下图从顶点a 出发进行深度优先遍历，则（A ）是可能得到的遍历序列。

A 、acfgdebB 、abcdefgC 、acdgbefD 、abefgcd对下图从顶点a 出发进行广度优先遍历，则（D ）是不可能得到的遍历序列。

A 、abcdefgB 、acdbfgeC 、abdcegfD 、adcbgef4. 设图G 的邻接矩阵A=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡010101010，则G 中共有（C ）个顶点；若G 为有向图，则G 中共有（D ）条弧；若G 为无向图，则G 中共有（B ）条边。

A 、1B 、2C 、3D 、4E 、5F 、9G 、以上答案都不对5. 含n 个顶点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。

A 、0B 、1C 、n-1D 、n6. 用邻接表存储图所用的空间大小（A ）。

A 、与图的顶点数和边数都有关B 、只与图的边数有关C 、只与图的顶点数有关D 、与边数的平方有关7. n 个顶点的无向图的邻接表最多有（B ）个表结点。

A 、n 2B 、n(n-1)C 、n(n+1)D 、n(n-1)/28. 无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。

数据结构图习题习题7 图7.1 单项选择题1．在⼀个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2B. 1C. 2D. 42．任何⼀个⽆向连通图的最⼩⽣成树。

A.只有⼀棵B.有⼀棵或多棵C.⼀定有多棵D.可能不存在3．在⼀个有向图中，所有顶点的⼊度之和等于所有顶点的出度之和的____倍。

A. 1/2B. 1C. 2D. 44．⼀个有n个顶点的⽆向图最多有____条边。

A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的⽆向完全图有____条边。

A. 6B. 12C. 16D. 206．具有6个顶点的⽆向图⾄少应有____条边才能确保是⼀个连通图。

A. 5B. 6C. 7D. 87．在⼀个具有n个顶点的⽆向图中，要连通全部顶点⾄少需要____条边。

A. nB. n+1C. n-1D. n/28．对于⼀个具有n个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵的⼤⼩是____。

A. nB. (n-1)2C. n-1D. n29．对于⼀个具有n个顶点和e条边的⽆向图，若采⽤邻接表表⽰，则表头向量的⼤⼩为_①___；所有邻接表中的接点总数是_②___。

①A. n B. n+1 C. n-1 D. n+e②A. e/2 B. e C.2e D. n+e10．已知⼀个图如图7.1所⽰，若从顶点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图 7.1 ⼀个⽆向图11．已知⼀有向图的邻接表存储结构如图7.2所⽰。

⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

一、单选题1、设有5个结点的无向图，该图至少应有_________条边才能确保是一个连通图。

A.7B.8C.6D.5正确答案：A2、设图G=(V,VR)，其中: V={A,B,C,D,G}，VR={(A,C),(A,D),( B,C),(B,D) ,(G,C),(B,G)}，则对应的图形为_________。

A.B.C.D.正确答案：C3、设某有向图中有n个顶点，则该有向图对应的邻接表中有_________个表头结点。

A.n-1B.n+2C.nD.n+1正确答案：C4、在一个无向图中所有顶点的度数之和等于所有边数的_________倍。

A.1B.2C.3D.1/2正确答案：B5、一个无向连通图的生成树是该连通图的_____。

A.极小连通子图B.强连通子图C.连通子图D.极大连通子图正确答案：A6、设某无向图中有n个顶点，则该无向图邻接矩阵的大小是_________。

A.n(n+1)/2B.（n-1）2C. n2D. （n+1）2正确答案：C7、设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi 关联的所有边算法的时间复杂度为_________。

A.O(n2)B.O(n+e）C.O(n*e）正确答案：D8、设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为_________。

A.O(n）B.O(n*e）C.O(n+e）D.O(n2)正确答案：C9、设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下列说法中错误的是_____。

A.G'是G的连通分量B.G'是G的一个无环子图C.G'是G的极小连通子图且V=V'D.G'是G的子图正确答案：A10、设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。

A.7B.6C.5D.8正确答案：B11、 n个顶点的有向图为强连通图时，至少含有________。