数据结构图练习题
数据结构图练习题
在计算机科学领域中，数据结构是一种用来组织和存储数据的方式。而图是一
种常见的数据结构，它由一组节点和连接这些节点的边组成。图可以用来表示
各种各样的关系，比如社交网络中的用户关系、城市之间的道路网络等等。在
本文中，我们将探讨一些与图相关的练习题，帮助读者更好地理解和应用图的
概念。
1. 最短路径问题
最短路径问题是图论中的经典问题之一。给定一个带权重的有向图，我们需要
找到从一个起始节点到目标节点的最短路径。这里的权重可以表示为距离、时
间或者其他度量。解决这个问题的算法有很多，其中最著名的是Dijkstra算法
和Bellman-Ford算法。读者可以尝试使用这些算法来解决一些具体的实例，比
如计算两个城市之间的最短路径。
2. 拓扑排序
拓扑排序是对有向无环图(Directed Acyclic Graph，简称DAG)进行排序的一种算法。在一个DAG中，节点之间存在一种偏序关系，即某些节点必须在其他节点之前进行处理。拓扑排序可以帮助我们确定这种偏序关系，从而找到一种合理
的处理顺序。比如，在编译器中，拓扑排序可以用来确定源代码中各个函数的
调用顺序。读者可以尝试编写一个拓扑排序算法，并应用到一些具体的场景中。
3. 最小生成树
最小生成树是一个无向连通图中一棵权值最小的生成树。在一个连通图中，最
小生成树可以帮助我们找到一种最优的连接方式，以满足一些约束条件。最常
用的算法是Prim算法和Kruskal算法。读者可以尝试使用这些算法来解决一些
具体的实例，比如在一个城市之间建设光纤网络，以最小的成本实现全覆盖。4. 图的遍历
图的遍历是指按照某种方式访问图中的所有节点。常见的遍历算法有深度优先
搜索(DFS)和广度优先搜索(BFS)。DFS通过递归地访问每个节点的邻居节点，直
到所有节点都被访问完。BFS则通过队列来实现，先访问起始节点的邻居节点，然后依次访问它们的邻居节点，直到所有节点都被访问完。读者可以尝试实现
这两种遍历算法，并观察它们的不同特点。
5. 最大流问题
最大流问题是图论中的一个经典问题，它可以用来解决一些网络流的优化问题。在一个有向图中，每条边都有一个容量，表示通过这条边的最大流量。最大流
问题的目标是找到从源节点到汇节点的最大流量。常用的解决方法是Ford-Fulkerson算法和Edmonds-Karp算法。读者可以尝试使用这些算法来解决一些
具体的实例，比如在一个供水网络中确定最大供水量。
通过以上的练习题，读者可以更好地理解和应用图的概念。图作为一种重要的
数据结构，广泛应用于计算机科学领域的各个方面。掌握图的基本概念和算法，对于解决实际问题和提高编程能力都有很大的帮助。希望读者能够通过练习和
实践，深入理解图的特性，并能够灵活运用它们解决各种问题。
7.1 选择题 1. 对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为() A) O(n)B)O(n+e)C) O(n*n)D)O(n*n*n) 【答案】B 2. 设无向图的顶点个数为n,则该图最多有()条边。 A) n-1B)n(n-1)/2C)n(n+1)/2 【答案】B 3. 连通分量指的是() A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 【答案】B 4. n 个结点的完全有向图含有边的数目() A) n*n B) n(n+1) C) n/2 【答案】D 5. 关键路径是() A) AOE网中从源点到汇点的最长路径 B) AOE网中从源点到汇点的最短路径 C) AOV网中从源点到汇点的最长路径D) n2
D) n* (n-1) D) AOV网中从源点到汇点的最短路径 【答案】 A 6．有向图中一个顶点的度是该顶点的() A)入度B)出度C)入度与出度之和D)(入度+出度)12 【答案】C 7．有e 条边的无向图，若用邻接表存储，表中有()边结点。 A) e B) 2eC) e-1D) 2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】 A 10．存储无向图的邻接矩阵一定是一个() A)上三角矩阵B)稀疏矩阵C)对称矩阵D)对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的()倍 A) B) 1C) 2D) 4 答案】B 12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为(
第七章 图 一、选择题 1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】 A ．由顶点和相邻顶点序偶构成的边所形成的序列 B ．由不同顶点所形成的序列 C ．由不同边所形成的序列 D ．上述定义都不是 2．设无向图的顶点个数为n ，则该图最多有（ ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 E ．n 2 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】 3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4 分)】 A ．n-1 B ．n C ．n+1 D ．nlogn ； 4．要连通具有n 个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、 6(2分）】 A ．n-l B ．n C ．n+l D ．2n 5．n 个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2分）】 A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ） 6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A ．0 B ．1 C ．n-1 D ．n 【北京邮电大学 2000 二、5 （20/8分）】 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2 分）】 A ．1/2 B ．2 C ．1 D ．4 8．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。【中山大学 1999一、14】 A ．5 B ．6 C ．8 D ．9 9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点 序列是( )。 A ．逆拓扑有序 B ．拓扑有序 C ．无序的 【中科院软件所 1998】 10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。 A ．邻接矩阵 B ．逆邻接表 C ．邻接多重表 D ．十字链表 E ．邻接 表 【北京工业大学 2001 一、3 (2分)】 11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】 A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 12． 从邻接阵矩⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101 010 A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】 ①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确
第6章习题解答(给学生) 一、填空 1．由4个顶点组成的一个连通图，应该有边4 条。 2．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要条边。 3．在无向图中，若顶点v i和v j之间有一条边（v i，v j）存在，那么则称顶点v i和v j互为点。 4．图中顶点v i的“度”，是指与它的顶点的个数，并记为D(v i)。 5．在有向图中，把从顶点v i到顶点v j的弧记为，而把从顶点v j到顶点v i的弧记为，这是两条不同的弧。 6．对于一个无向图，其邻接矩阵中第i行（或第i列）里非零或非∞元素的个数，正好是第i个顶点v i的。 7．对于一个有向图，其邻接矩阵中第i行里非零或非∞元素的个数，正好是第i个顶点v i的；其邻接矩阵中第i列里非零或非∞元素的个数，正好是第i个顶点v i的。 8．在无向图中，若从顶点v i到顶点v j之间有存在，则称v i与v j是连通的。 9．如果无向图G中一对顶点之间都是连通的，则称该图G为连通图，否则是非连通图。 10．在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个。 11．包含无向连通图G的所有n个顶点在内的极小连通子图，是这个图的。 12．只要在无向连通图的生成树里减少任意一条边，它就成为了一个。 13．对图的广度优先搜索，类似于对树进行遍历。 14．拓扑排序是得到AOV网的一个序列，使得网中所有顶点间的优先关系在序列中得以体现。 15．已知无向图的顶点个数为n，边数为e。那么，在其邻接表表示法中，链表结点数与单链表表头结点数之和是。 二、选择 1．在一个有n个顶点的无向图中，要连通全部顶点，至少需要条边。 A．n B．n+1 C．n-1 D．n/2 2．对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。因此，有n个顶点的无向完全图包含有条边。 A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/2 3．对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。因此，有n个顶点的有向完全图包含有条边。 A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/2 4．在一个无向图中，所有顶点的度数之和，是其所有边数之和的倍。 A．1/2 B．1 C．2 D．4 5．在一个有向图中，所有顶点的入度之和所有顶点的出度之和。 A．二分之一于B．等于C．两倍于D．四倍于6．一个无向连通网图的最小生成树。 A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在7．一个无向图有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组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 ⑵ n个顶点的强连通图至少有（）条边，其形状是（）。 A n B n+1 C n-1 D n×(n-1) E 无回路 F 有回路 G 环状 H 树状 【解答】A，G ⑶ 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。 A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。
数据结构练习题（一） 一、单选题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( )。 A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中( )是非线性结构。 A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( )。 A．2k-1 +1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( )。 A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个。 A．1 B．2 C．3 D．4
9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 二、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为 __________个，树的深度为___________，树的度为_________。 4.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 5.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 6.AOV网是一种___________________的图。 7.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数 的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 9.在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、计算题 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data next 2.
数据结构图练习题 数据结构图练习题 在计算机科学领域中，数据结构是一种用来组织和存储数据的方式。而图是一 种常见的数据结构，它由一组节点和连接这些节点的边组成。图可以用来表示 各种各样的关系，比如社交网络中的用户关系、城市之间的道路网络等等。在 本文中，我们将探讨一些与图相关的练习题，帮助读者更好地理解和应用图的 概念。 1. 最短路径问题 最短路径问题是图论中的经典问题之一。给定一个带权重的有向图，我们需要 找到从一个起始节点到目标节点的最短路径。这里的权重可以表示为距离、时 间或者其他度量。解决这个问题的算法有很多，其中最著名的是Dijkstra算法 和Bellman-Ford算法。读者可以尝试使用这些算法来解决一些具体的实例，比 如计算两个城市之间的最短路径。 2. 拓扑排序 拓扑排序是对有向无环图(Directed Acyclic Graph，简称DAG)进行排序的一种算法。在一个DAG中，节点之间存在一种偏序关系，即某些节点必须在其他节点之前进行处理。拓扑排序可以帮助我们确定这种偏序关系，从而找到一种合理 的处理顺序。比如，在编译器中，拓扑排序可以用来确定源代码中各个函数的 调用顺序。读者可以尝试编写一个拓扑排序算法，并应用到一些具体的场景中。 3. 最小生成树 最小生成树是一个无向连通图中一棵权值最小的生成树。在一个连通图中，最 小生成树可以帮助我们找到一种最优的连接方式，以满足一些约束条件。最常
用的算法是Prim算法和Kruskal算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个城市之间建设光纤网络，以最小的成本实现全覆盖。4. 图的遍历 图的遍历是指按照某种方式访问图中的所有节点。常见的遍历算法有深度优先 搜索(DFS)和广度优先搜索(BFS)。DFS通过递归地访问每个节点的邻居节点，直 到所有节点都被访问完。BFS则通过队列来实现，先访问起始节点的邻居节点，然后依次访问它们的邻居节点，直到所有节点都被访问完。读者可以尝试实现 这两种遍历算法，并观察它们的不同特点。 5. 最大流问题 最大流问题是图论中的一个经典问题，它可以用来解决一些网络流的优化问题。在一个有向图中，每条边都有一个容量，表示通过这条边的最大流量。最大流 问题的目标是找到从源节点到汇节点的最大流量。常用的解决方法是Ford-Fulkerson算法和Edmonds-Karp算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个供水网络中确定最大供水量。 通过以上的练习题，读者可以更好地理解和应用图的概念。图作为一种重要的 数据结构，广泛应用于计算机科学领域的各个方面。掌握图的基本概念和算法，对于解决实际问题和提高编程能力都有很大的帮助。希望读者能够通过练习和 实践，深入理解图的特性，并能够灵活运用它们解决各种问题。
图 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
1、一个无向连通图的生成树是含有该连通图的全部顶点的（）。 A.极大连通子图 B.极大子图 C.极小子图 D.极小连通子图 正确答案：D 2、任何一个非空带权无向连通图（）最小生成树。 A.可能不存在 B.只有一棵 C.一定有多棵 D.有一棵或多棵 正确答案：D 3、用Prim算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的顶点集合 U＝{1，2，3} 已选取的边的集合 TE＝{(1，2)，(2，3)} 要选取下一条权值最小的边，应当从（）组中选取。 A.{(3，4)，(3，5)，(4，5)，(1，4)}
B.{(4，5)，(1，3)，(3，5)} C.{(1，4)，(3，4)，(3，5)，(2，5)} D.{(1，2)，(2，3)，(3，5)} 正确答案：C 解析： C、U={1，2，3}，V-U={4，5，…}，候选边只能是这两个 顶点集之间的边。 4、对某个带权连通图构造最小生成树，以下说法中正确的是（）。Ⅰ.该图的所有最小生成树的总代价一定是唯一的 Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.用普里姆（Prim）算法从不同顶点开始构造的所有最小生成树一 定相同 Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成 树总不相同 A.仅Ⅱ B.仅Ⅱ、Ⅳ C.仅Ⅰ D.仅Ⅰ、Ⅲ 正确答案：C 解析： C、由一个带权连通图构造的最小生成树可能有多棵，但其 代价一定是唯一的；
权值最小的边可能不唯一，这些不唯一的最小权值边不一定都会出现在所有的最小生成树中； 当存在多条权值相同的边时，用普里姆（Prim）算法从不同顶点开始得到的最小生成树不一定相同； 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树不一定总不相同，如图中最小生成树唯一时，无论用哪种算法，得到的最小生成树都是相同的。 5、用Kruskal算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的边集合 TE＝{(1，2)，(2，3)，(3，5)} 要选取下一条权值最小的边，不可能选取的边是（）。 A.(2，4) B.(1，4) C.(3，6) D.(1，3) 正确答案：D 解析： D、选取(1，3)边会构成回路。 6、在用Prim和Kruskal算法构造最小生成树时，前者更适合于（）。 A.有向图
一、选择题 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）。
数据结构(树与图部份)练习题 一、填空题 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．图中有关路径的定义是（）。 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 绪论 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 数据结构图练习试题(总7页) -本页仅作为预览文档封面，使用时请删除本页- 图练习： 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,则该图必是连通图。（） 数据结构(树与图部分)练习题 一、填空题 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数据结构图练习试题
数据结构(树与图部分)练习题
相关主题
文本预览