对于连通无向图 G,以下叙述中,错误的是【 】。
A、G 中任意两个顶点之间存在路径
B、G 中任意两个顶点之间都有边
C、从G中任意顶点出发可遍历图中所有项点
D、G 的邻接矩阵是对称的
对于连通无向图 G,以下叙述中,错误的是【 】。
A、G 中任意两个顶点之间存在路径
B、G 中任意两个顶点之间都有边
C、从G中任意顶点出发可遍历图中所有项点
D、G 的邻接矩阵是对称的
B
【解析】
若无向图 G 是连通的,表示任意两个顶点间都存在路径,那么从任意一个顶点出发都能到达其他顶点,所以可遍历图中所有顶点。无向图采用邻接矩阵存储时,对于任意一条边(v, u),从v和u两个顶点各自的角度来表示的邻接关系都是同一条边,因此是对称的矩阵。任意两个顶点之间都有边的图是完全图。完全图是连通图,反之则不一定。
设 S 是一个长度为n的非空字符串,其中的字符各不相同,则其互异的非平凡子串(非空且不同于S本身)的个数为【 】。
在C程序中有一个二维数组 A[7][8],每个数组元素用相邻的 8 个字节存储,那么存储该数组需要的字节数为【 】。
对于一个初始为空的栈,其入栈序列为 1,2,3,...,n(n>3),若出栈序列的第一个元素是1则出栈序列的第n个元素【 】
某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG,则该二叉树根结点的左孩子结点和右孩子结点分别是【 】
采用【 】算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后,其元素的排列变为{12,10,11,18,2,7,23}。
表达式可采用后缀形式表示。例如,“a+b”的后缀式为“ab+”。那么,表达式“a*(b-c)+d”的后缀表示为【 】
有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。
用DFS遍历一个无环有向图,并DFS算法退栈返回时打印出相应的顶点,则输出的顶点序列是【 】。
图的遍历方式有__________和__________两种。
表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否稀疏矩阵?
若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑有序序列必定存在。
Kruskal算法的时间复杂度为__________,它对__________图比较合适。
在下列两种求图的最小生成树的算法中,【 】算法适合于求边稀疏的网的最小生成树。
在一个有n个顶点的无向网中,有O(n1.5*log2n)条边,则应该选用【 】算法来求这个网的最小生成树,从而使计算时间较少。