算法与数据结构（山东联盟）第五章测试_智慧树知到答案2021年

第五章 图：图(Graph)是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树型结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中的多个元素相关，但只能和上一层中的一个元素相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。因此，图的应用相当广泛，在自然科学、社会科学和人文科学等许多领域都有着非常广泛的应用。5.1图的基本概念:图由非空的顶点(Vertex)集合和描述顶点之间的关系——边(Edge)或弧(Arc)的集合组成。本节学习图的术语。
5.2图的存储结构:图是一种复杂的数据结构，顶点之间是多对多的关系，即任意两个顶点之间都可能存在联系。所以无法用顶点在存储区的位置关系来表示顶点之间的联系，即顺序存储结构不能完全存储图的信息，但可以用数组来存储图的顶点信息。要存储顶点之间的关系可以使用链式存储结构或者二维数组。在实际应用中，应根据具体的图和需要进行操作设计恰当的结点结构和表结构。图的存储结构有多种，常用的有邻接矩阵、邻接表和十字链表等。
5.3图的遍历:图的遍历是指从图中的某个顶点出发，按照某种顺序访问图中的每个顶点，使每个顶点被访问一次且仅被访问一次。图的遍历与树的遍历操作功能相似。图的遍历有深度优先遍历和广度优先遍历两种方式，它们对图和网都适用。
5.4图的应用:许多应用问题都是一个求无向连通网的最小生成树问题。构造最小生成树的方法有许多种，典型的方法有两种，一种是普里姆(Prim)算法，一种是克鲁斯卡尔(Kruskal)算法。
5.5实验编程---图的深度优先遍历:采用邻接矩阵，对图进行深度优先遍历和广度优先遍历
5.1图的基本概念:图由非空的顶点(Vertex)集合和描述顶点之间的关系——边(Edge)或弧(Arc)的集合组成。本节学习图的术语。
5.2图的存储结构:图是一种复杂的数据结构，顶点之间是多对多的关系，即任意两个顶点之间都可能存在联系。所以无法用顶点在存储区的位置关系来表示顶点之间的联系，即顺序存储结构不能完全存储图的信息，但可以用数组来存储图的顶点信息。要存储顶点之间的关系可以使用链式存储结构或者二维数组。在实际应用中，应根据具体的图和需要进行操作设计恰当的结点结构和表结构。图的存储结构有多种，常用的有邻接矩阵、邻接表和十字链表等。
5.3图的遍历:图的遍历是指从图中的某个顶点出发，按照某种顺序访问图中的每个顶点，使每个顶点被访问一次且仅被访问一次。图的遍历与树的遍历操作功能相似。图的遍历有深度优先遍历和广度优先遍历两种方式，它们对图和网都适用。
5.4图的应用:许多应用问题都是一个求无向连通网的最小生成树问题。构造最小生成树的方法有许多种，典型的方法有两种，一种是普里姆(Prim)算法，一种是克鲁斯卡尔(Kruskal)算法。
5.5实验编程---图的深度优先遍历:采用邻接矩阵，对图进行深度优先遍历和广度优先遍历

[单选题]设某无向图有n个顶点，则该无向图的邻接表中有（  ）个表头结点。      
n 
 n(n-1)
n/2 
2n 
答案：n
[单选题]设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（  ）。
 第i列0元素的个数之和
第i行非0或非∞元素的个数之和 
第i列非0或非∞元素的个数之和
第i行0元素的个数之和  [单选题]设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边
n(n-1)/2
n的2次幂-1
n的2次幂
n(n-1)[判断题]  子串“ABC”在主串“AABCABCD”中的位置为2。(  )
错
对[判断题]     对链表进行插入和删除操作时不必移动链表中结点。(  )
对
错[单选题]深度为k的完全二叉树中最少有（  ）个结点。           
  2k-1+1
  2k-1
  2k-1-1      [单选题]设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（  ）。          
N0=Nl+N2 
N0=N1+1 
N0=N2+1  
N0=2N1+l[判断题]简单回路就是回路。
错
对[判断题]图中任两点有路径相通，该图称为连通图（）
错
对