数据结构图练习试题(总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,则该图必是连通图。（）
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列非零元素个数 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 算法，求它的最小生成树
3
67
58
9
4
2
1
3
10
57
8
4
2
1
6
9
答案：
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．深度优先遍历序列：4
宽度优先遍历序列：9
注：（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．图中有关路径的定义是（）。 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. 最短路径问题 最短路径问题是图论中的经典问题之一。给定一个带权重的有向图，我们需要 找到从一个起始节点到目标节点的最短路径。这里的权重可以表示为距离、时 间或者其他度量。解决这个问题的算法有很多，其中最著名的是Dijkstra算法 和Bellman-Ford算法。读者可以尝试使用这些算法来解决一些具体的实例，比 如计算两个城市之间的最短路径。 2. 拓扑排序 拓扑排序是对有向无环图(Directed Acyclic Graph，简称DAG)进行排序的一种算法。在一个DAG中，节点之间存在一种偏序关系，即某些节点必须在其他节点之前进行处理。拓扑排序可以帮助我们确定这种偏序关系，从而找到一种合理 的处理顺序。比如，在编译器中，拓扑排序可以用来确定源代码中各个函数的 调用顺序。读者可以尝试编写一个拓扑排序算法，并应用到一些具体的场景中。 3. 最小生成树 最小生成树是一个无向连通图中一棵权值最小的生成树。在一个连通图中，最 小生成树可以帮助我们找到一种最优的连接方式，以满足一些约束条件。最常
用的算法是Prim算法和Kruskal算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个城市之间建设光纤网络，以最小的成本实现全覆盖。4. 图的遍历 图的遍历是指按照某种方式访问图中的所有节点。常见的遍历算法有深度优先 搜索(DFS)和广度优先搜索(BFS)。DFS通过递归地访问每个节点的邻居节点，直 到所有节点都被访问完。BFS则通过队列来实现，先访问起始节点的邻居节点，然后依次访问它们的邻居节点，直到所有节点都被访问完。读者可以尝试实现 这两种遍历算法，并观察它们的不同特点。 5. 最大流问题 最大流问题是图论中的一个经典问题，它可以用来解决一些网络流的优化问题。在一个有向图中，每条边都有一个容量，表示通过这条边的最大流量。最大流 问题的目标是找到从源节点到汇节点的最大流量。常用的解决方法是Ford-Fulkerson算法和Edmonds-Karp算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个供水网络中确定最大供水量。 通过以上的练习题，读者可以更好地理解和应用图的概念。图作为一种重要的 数据结构，广泛应用于计算机科学领域的各个方面。掌握图的基本概念和算法，对于解决实际问题和提高编程能力都有很大的帮助。希望读者能够通过练习和 实践，深入理解图的特性，并能够灵活运用它们解决各种问题。
习题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. 在数组中插入和删除元素最慢的时间复杂度是： 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章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的内容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机内实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个方面的内容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（ nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构 B．存储和抽象 C．联系和抽象 D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构。 3.数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点． B．无直接后继结点． 数据结构试题及答案(十套)数据结构试题及答案(十套) 一、选择题 1. 数据结构是指（）。 A. 存储数据的方式 B. 数据的逻辑结构和物理结构 C. 数据的存储结构和存储方式 D. 数据的逻辑结构、存储结构和存储方式 答案：D 2. 在数据结构中，线性表的存储方式包括（）。 A. 顺序存储和链式存储 B. 数组存储和链表存储 C. 顺序存储、链表存储和索引存储 D. 顺序存储、链表存储和树形存储 答案：A 3. 栈是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：C 4. 队列是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：A 5. 二叉树中，度为0的节点称为（）。 A. 叶子节点 B. 根节点 C. 中间节点 D. 子节点 答案：A 6. 以下哪个排序算法是稳定的？ A. 快速排序 B. 选择排序 C. 插入排序 D. 希尔排序 答案：C 7. 图中表示顶点之间关系的边的数量称为（）。 A. 顶点度数 B. 边数 C. 路径数 D. 网络 答案：B 8. 哈希表通过（）来实现高效的查找操作。 A. 散列函数 B. 排序算法 C. 遍历操作 D. 顺序存储 答案：A 9. 平衡二叉树是一种具有左右子树高度差不超过（）的二叉树。 A. 0 B. 1 C. 2 D. 3 答案：B 10. 在链表中，删除节点的操作时间复杂度是（）。 A. O(1) B. O(logn) C. O(n) D. O(nlogn) 答案：A 二、填空题 1. 在顺序存储结构中，元素之间的逻辑关系由（）表示。 答案：下标 2. 二叉查找树的中序遍历结果是一个（）序列。 答案：递增 3. 哈希表通过散列函数将关键字映射到（）上。 习题1 一、单项选择题 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; (1) (2n) (n) (3n) 5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（）年。 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（）。 A.数据 B.数据元素 C.数据项 D.数据库 二、填空题 1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。 2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。 3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。 4. 一个算法的效率可分为__________________效率和__________________效率。 5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有 数据结构练习题 第一部分绪论 一、单选题 1. 一个数组元素a[i]与________的表示等价。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。 A、参数类型 B、参数个数 C、函数类型 3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数 A、指针 B、引用 C、值 4. 下面程序段的时间复杂度为____________。 for(int i=0; i 习题七图 一、单项选择题 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之前，则图中必有一条弧 第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 D．2 ．4 C2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 D．4 C．2 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 D ．n(n-1)/2 C．n-1 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) D．n(n-l)/2 C．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) D．C．n(n-l)/2 n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。nnB．×．An (n-l) ×(n-l)．D n-1 C． ．无向图的邻接矩阵是一个______。7 ．零矩阵B ．对称矩阵A．C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e D．2e C．2n 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e DC．2n ．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。A．入边B．出边 D．不是入边也不是出边C．入边和出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。A．入边B．出边 D ．不是人边也不是出边C．入边和出边 数据结构练习题（含答案） ①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构DS(DataStruct)可以被形式地定义为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.算法的五个重要特性是____,____,____,____,____。 数据结构试题及答案 一、选择题(共10题，每题1分，共10分) 1( 下面关于线性表的叙述中，错误的是哪一个,( ) A(线性表采用顺序存储，必须占用一片连续的存储单元 B(线性表采用顺序存储，便于进行插入和删除操作 C(线性表采用链接存储，不必占用一片连续的存储单元 D(线性表采用链接存储，便于插入和删除操作 2( 在一个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插入s所指结 点，则执行的操作是( )。 A. s->next=p->next;p->next=s; B. q->next=s;s->next=p; C. p->next=s->next;s->next=p; D. p->next=s;s->next=q; 3( 设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。 A(XYZ B. YZX C. ZXY D. ZYX 4( 若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3， 则从队列中删除一个元素，再增加两个元素后，rear和front的值分别是( )。 A(1和5 B(2和4 C(4和2 D. 5和1 5( 下列说法中正确的是( )。 A(二叉树就是度为2的树 B(二叉树中不存在度大于2的结点 C(二叉树中至少有一个结点的度为2 D(二叉树中任何一个结点的度都为2 6( 在具有n个结点的二叉链表中，共有( )个空指针。 A. n B. n-1 C. n+1 D. 不确定 7( 根据二叉树与树的转换关系可知，深度为h的满二叉树对应的森林由( )棵树构成。 A(1 B(logn C. h/2 D. h 2 8( 在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A(1/2 B(1 C. 2 D. 4 9( 对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是( )。 A(8,17 ,(5,10,12 C(9,16 D(9,17 10(关于排序，下列说法中正确的是( )。 A. 稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高 B. 在顺序表上实现的排序方法在链表上也可以实现 C. 在链表上可以实现简单选择排序，但是难以实现堆排序 D. 就平均性能而言，堆排序最佳 二、填空题(共10空，每空2分，共20分) 1( 计算机执行下面的语句时，语句s的执行次数为 _______ 。 for(i=l;i 数据结构自测题1 一、单项选择题 1.线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D ）。 A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以2.在单链表中，增加头结点的目的是为了（ C ） A．使单链表至少有一个结点B．表示表结点中首结点的位置 C．方便运算的实现D．说明单链表是线性表的链式存储实现 3.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应是（ B ）A．2 B．3 C．4 D．5 4.树结构中，前驱结点与后继结点之间存在（ B ）关系。 A．一对一B．一对多C．多对一D．多对多 5.堆栈的特性描述是（ B ）。A．FIFO B．FILO C．FIFO和FILO D．FIFO或FILO 6.队列的特性描述是（ A ）。A．FIFO B．FILO C．FIFO和FILO D．FIFO或FILO 7.下列数据结构中，是非线性结构的是（ A ）A．树B．堆栈C．队列D．循环队列 8.设某个初始为空的容纳int型数据的堆栈进行了如下操作（每一步均未发生溢出）： push(1)、push(3)、pop()、push(6)、push(1)、pop()、push(3)、push(8) 后，该堆栈中从栈顶到栈底的元素依次为（ D ）A．8 1 8 3 B．1 3 1 8 C．1 6 3 8 D．8 3 6 1 二、判断题 1.二叉树可以为空树。（√） 2.顺序表和链表都是线性表。（√） 3.线性表的长度是线性表占用的存储空间的大小。（√） 4.队列只能采用链式存储方式。（×） 5.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。（√） 6.存在有偶数个结点的满二叉树。（×） 三、填空题 1.数据结构是数据在计算机内的组成形式和相互关系。 2.二叉树的三种遍历方式分别为中序遍历、先序遍历和后序遍历。 3.深度为K的满二叉树共有2k－1 个结点。 4.N个顶点的无向图是完全图的条件是其边数为n ( n－1 ) / 2 。 四、名词解释 1.ADT ADT是抽象数据类型的简称，指一个数学模型以及定义在该模型上的一组操作。 2.栈栈是限定仅在表尾进行插入或删除操作的线性表，具有先进后出（FILO）的特性。 3.队列队列是只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表，具有先进先出（FIFO）的特性。 五.简答题 1.分别写出下图所示二叉树的先序遍历、中序遍历和后序遍历序列 《数据结构》练习题 一、选择题 1.先序序列为a，b，c，d的不同二叉树的个数是 A.13 B.14 C.15 D.16 ［解析］二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd为右子树；②b为左子树，cd为右子树； ③bc为左子树，d为右子树；④bcd为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd）可能有： a．左子树为空，右子树为cd；b．左子树为c，右子树为d；c．左子树为cd，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二叉树。 2.用S表示进栈操作，X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S和X的操作序列为 A.SXSXSSXX B.SSSXXSXX C.SXSSXXSX D.SXSSXSXX ［解析］采用排除法：选项A、B、C得到的出栈序列为1243、3241、1324。由1234得到1342的进栈序列为：1进，1出，2进，3进，3出，4进，4出，2出。 3.对于下列关键字序列，不可能构成某二叉序列树中一条查找路径的序列是 A.95,22,91,24,94,71 B.92,20,91,34,88,35 C.21,89,77,29,36,38 D.12,25,71,68,33,34 ［解析］在二叉树中，左子树结点值小于根结点，右子树结点值大于根结点。在选项A中，当查找到91后再向24查找，说明这一条路径（左子树）之后查找的数都要比91小，而后面却查找到了94，因此错误。 4.有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，下列算法不会出现此种情况的是 A.堆排序 B.希尔排序 C.冒泡排序 D.快速排序 ［解析］由于希尔排序是基于插入排序算法而提出的，它不一定在每趟排序排序过程后使某一元素放置到最终位置上。 5.若以1、2、3、4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是 A.1,2,3,4 B.4,1,3,2 C.4,2,3,1 D.4,2,1,3 ［解析］使用排除法。先看可由输入受限的双端队列产生的序列：设右端输入受限，1234依次左入，则依次左出可得到4321，排除A；右出、左出、右出、右出可得到4132，排除B；再看可由输出受限的双端队列产生的序列：设右端输出受限，1234依次左入、左入、右入、左入，依次左出可得到4213，排除D。 6.设二叉树只有度为0和2的结点，其结点个数为15，则该二叉树的最大深度为 A.5 B.8 C.9 D.10 ［解析］第一层有一个结点，其余h-1层上各有两个结点，总结点数=1+2（h-1）=15，h=8。建议画出草图。 7.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是 A．24,10,5和24,10,7 B．24,10,5和24,12,7 C．24,10,10和24,14,11 D．24,10,5和24,14,6 ［解析］哈夫曼树是带权路径长度最短的二叉树。由根结点出发到两个叶子结点路径中，第二个被访问的两个结点的权值要么相等，要么和为根结点的权值，故B项错误。同理，通过第三个被访问的结点排除A项。C项，由两条路径可推出三个叶子结点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的结点应该和权值为10的结点结合，故C项错误。D项，反推出有四个叶子结点，权值分别为：5、5、6和8，满足哈夫曼树的条件。 8.现在有一颗无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是 A．根节点的度一定为2 B．树中最小元素一定是叶节点 C．最后插入的元素一定是叶节点 D．树中最大元素一定是无左子树 ［解析］二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B项错误，树中最小元素是中序遍历时最后访问的节结点，当没有右子树时，最后访问的结点是根结点；C项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间结点；D项正确，由中序遍历的特点可知，左子树的值大于根结点，所以最大元素一定没有左子树。 数据结构习题及答案 习题八查找 一、单项挑选题 1．挨次查找法适合于存储结构为（）的线性表。 A．散列存储B. 挨次存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的延续挨次文件中采纳挨次查找法查找一个记录，其平均查找长度ASL为( )。 A．(n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素罗列要求为( ) A．链接方式存储，元素无序B．链接方式存储，元素有序 C．挨次方式存储，元素无序D．挨次方式存储，元素有序 4．当在一个有序的挨次存储表上查找一个数据时，即可用折半查找，也可用挨次查找，但前者比后者的查找速度( ) A．必然快B.不一定C. 在大部分状况下要快D. 取决于表递增还是递减5．当采纳分块查找时，数据的组织方式为( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必需有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分须要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确B. 错误 7. 二叉查找树的查找效率与二叉树的(（1）)有关, 在(（2）)时其查找效率最低。 (1): A. 高度B. 结点的多少C. 树型D. 结点的位置 (2): A. 结点太多B. 彻低二叉树C. 呈单枝树D. 结点太复杂。 8．假如要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采纳( )查找法。 A. 分快查找 B. 挨次查找 C. 折半查找 D. 基于属性 9．分离以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。数据结构练习试题和答案解析
数据结构试题及答案(十套)
数据结构习题及参考答案
(完整版)数据结构练习题及参考答案
第七章图习题_数据结构
数据结构图习题分解
数据结构练习题（含答案）
数据结构试题及答案
数据结构自测试题及答案
数据结构练习题
数据结构习题及答案
相关主题
文本预览