填空题(1999年中国科学院计算机研究所)

对于给定的n个元素,可以构造的逻辑结构有__________、__________、__________和__________4种。

答案解析

集全、线性结构、树型结构、图形结构

讨论

已知有向图G采用邻接矩阵存储,其定义如下:typedef struct{//图的定义 int numberVertices,numEgges;//图中实际的顶点数和边数 char verticesList[maxV];//顶点表 int edge[maxV][maxV];//邻接矩阵}MGraph;将图中出度大于入度的顶点称为K顶点,如图,a和b都是K顶点,设计算法 int printVertices(MGraph G)对给定任意非空有向图G,输出G中所有K顶点,并返回K顶点的个数。(1)给出算法的设计思想。(2)根据算法思想,写出C/C++描述,并注释。

已知无向连通图 G 中各边的权值均为 1,下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【 】Ⅰ.普利姆算法;Ⅱ.克鲁斯卡尔算法;Ⅲ.图的广度优先搜索

在一个有n个顶点的无向网中,有O(n1.5*log2n)条边,则应该选用【 】算法来求这个网的最小生成树,从而使计算时间较少。

在下列两种求图的最小生成树的算法中,【 】算法适合于求边稀疏的网的最小生成树。

Kruskal算法的时间复杂度为__________,它对__________图比较合适。

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

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

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

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

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