数据结构与算法-考研试题(中国科学院计算机研究所 1999年图的概念)

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

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

答案解析

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

讨论

数据结构与算法

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

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

二叉树在线索化后，仍不能有效求解的问题是【】。

线索二叉树是一种【】结构。

求具有最小带权路径长度的二叉树的算法称为__________算法。对于给出的一组权W={10，12，16，21，30}，通过该算法示出的二叉树的带权路径长度为__________。

如果一棵huffman树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。

在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法【】。

什么是啥夫曼（Huffman）树？

啥夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n），其中带权路径长度最小的二叉树称为__________。

图的概念

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

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

对于一个具有n个结点的连通无向图，如果它有且只有一个简单回路，那么此图有__________条边。

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

G是一个非连通无向图，共有28条边，则该图至少有【】个顶点。

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

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

最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度wihi最小的树，其中对最优二叉树，n表示__________，对最优查找树，n表示__________，构造这两种树均__________。（1）结点数（2）叶结点数（3）非叶结点数（4）度为2的结点数（5）需要一张n个关键字的有序表（6）需要对n个关键字进行动态插入（7）需要n个关键字的查找概率表（8）不需要任何前提

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

对于给定的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为终态)可识别字符串【】。