数据结构与算法-考研试题(暨南大学 2023年图的存储)

判断题（2023年暨南大学）

无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。

答案解析

对

讨论

数据结构与算法

由树转化为二叉树，该二叉树的右子树不一定为空。

一个图按广度优先遍历的结果是唯一的。

分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

在一棵树中，堂兄弟的双亲是兄弟关系。

已知一颗二叉树的先序序列和后序序列，一定能构造出该树。

顺序表查找指的是在顺序存储结构上进行查找。

在一棵二叉树中，中序遍历的第一个结点，是二叉树的最左下结点。

用邻接表表示图进行广度优先遍历时，通常采用【】来实现算法。

图的存储

设计一数据结构，用来表示图的邻接矩阵存储结构(包括弧的结构和图的结构)。

某图G的邻接表如下所示。以下关于图G的叙述中，正确的是【】。

某有向图G及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中，错误的是【】。

某图G的邻接矩阵如下所示。以下关于该图的叙述中，错误的是【】

设某无向图的顶点个数为n，则该图最多有______条边;若将该图用邻接矩阵存储，则矩阵的行数和列数分别为______。

对于下面的有向图，其邻接矩阵是一个【】的矩阵。

对于下面的有向图，采用邻接链表存储时，顶点 0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为【】。

表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？

已知某带权图G的邻接表如下所示，其中表结点的结构为:以下关于该图的叙述中，正确的是【】。

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

图

任何一个无向连通图的最小生成树【】

深度优先遍历类似于二叉树的【】

如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是【】

在n个结点的无向图中，若边数>n-1，则该图必是连通图。

有 n 个顶点的有向强连通图最多有多少条边？最少有多少条边？

一个具有n个结点的弱连通图至少有__________条边。

如果G是一个具有n个顶点的连通无向图，那么G最多有__________条边，最少有__________条边。

对于连通无向图 G，以下叙述中，错误的是【】。

下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串【】。

设无向图的顶点个数为n，则该无向图最多有【】条边。