2022年数据结构第96次模拟试卷

Q1:树中的结点和图中的顶点就是指数据结构中的数据元素

Q2:在 n 个结点的无向图中，若边数大于 n-1,则该图必是连通图。

Q3:有 e 条边的无向图，在邻接表中有 e 个结点。

Q4:有向图中顶点 V 的度等于其邻接矩阵中第 V 行中的 1 的个数

Q5:强连通图的各顶点间均可达。

Q6:强连通分量是无向图的极大强连通子图

Q7:连通分量指的是有向图中的极大连通子图

Q8:邻接多重表是无向图和有向图的链式存储结构。

Q9:十字链表是无向图的一种存储结构

Q10:无向图的邻接矩阵可用一维数组存储。

Q11:用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。

Q12:有 n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。

Q13:有向图的邻接矩阵是对称的

Q14:无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。

Q15:邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它

Q16:用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关

Q17:一个有向图的邻接表和逆邻接表中结点的个数可能不等。

Q18:需要借助于一个队列来实现 DFS 算法

Q19:DFS是一个广度优先搜索遍历

Q20:BFS是一个深度优先搜索遍历

Q21:广度遍历生成树描述了从起点到各顶点的最短路径。

Q22:任何无向图都存在生成树

Q23:不同的求最小生成树的方法最后得到的生成树是相同的.

Q24:带权无向图的最小生成树必是唯一的。

Q25:最小代价生成树是唯一的。

Q26:一个网（带权图）都有唯一的最小生成树。

Q27:连通图上各边权值均不相同，则该图的最小生成树是唯一的。

Q28:带权的连通无向图的最小（代价）生成树（支撑树）是唯一的

Q29:求最小生成树的普里姆(Prim)算法中边上的权可正可负。

Q30:带权的连通无向图的最小代价生成树是唯一的

Q31:最小生成树问题是构造连通网的最小代价生成树。

Q32:拓扑排序算法把一个无向图中的顶点排成一个有序序列。

Q33:无环有向图才能进行拓扑排序

Q34:拓扑排序算法仅能适用于有向无环图。

Q35:有环图也能进行拓扑排序。

Q36:拓扑排序的有向图中，最多存在一条环路。

Q37:任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。

Q38:既使有向无环图的拓扑序列唯一，也不能唯一确定该图。

Q39:若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。

Q40:关键路径是 AOE 网中从源点到终点的最长路径。

Q41:AOE 网一定是有向无环图。

Q42:判断一个无向图是一棵树的条件是 n个顶点 n-1条边无向连通图

Q43:一个连通图的_生成树_____是一个极小连通子图。

Q44:在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__n____条弧。

Q45:在有 n 个顶点的有向图中，每个顶点的度最大可达__2(n-1)____。

Q46:如果含 n 个顶点的图形形成一个环，则它有_n_____棵生成树。

Q47:构造 n 个结点的强连通图，至少有_n-1_____条弧。

Q48:在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度____；对于有向图来说等于该顶点的_出度_____

Q49:对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为__n____，邻接表的边结点个数为__e____

Q50:遍历图的过程实质上是查找顶点的邻接点的过程

Q51:构造连通网最小生成树的两个典型算法是 普利姆 和 克鲁斯卡尔算法

Q52:Prim（普里姆）算法适用于求__边稀疏____的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求__边稠密____的网的最小生成树

Q53:克鲁斯卡尔算法的时间复杂度为__O(eloge)____,它对__稀疏图____图较为适合。

Q54:对于含 N 个顶点 E 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂度为____O(n2)__，利用 Kruskal 算法生成最小代价生成树其时间复杂度为___O(eloge)___。

Q55:在 AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为 关键路径_____

Q56:求最短路径的 Dijkstra 算法的时间复杂度为__On2____。