数据结构与算法-考研试题(中国科学技术大学 1995年图的应用)

单项选择（1995年中国科学技术大学）

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

A、PRIM

B、KRUSKAL

答案解析

B

讨论

数据结构与算法

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

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

试列中下列图中全部可能的拓扑排序序列。

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

对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

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

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

图的遍历方式有__________和__________两种。

用DFS遍历一个无环有向图，并DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是【】。

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

图

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

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

已知有向图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是一个具有n个顶点的连通无向图，那么G最多有__________条边，最少有__________条边。

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

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

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

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

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

n个顶点的连通图用邻接矩阵表示时，该矩阵至少有__________个非零元素。

图的应用

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

对于正整数n ，输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ，程序输出为：4 = 44 = 3 + 14 = 2 + 24 = 2 ＋ 1 ＋ 1 4 = 1 ＋ 1 ＋ 1 ＋ 1test 是实现该功能的 C 程序段，请将未完成的部分补足，使之完整。test 函数为一递归函数，参数 n 为被分解和式的数， k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解，将分解出的数（称为和数）存于二数组 a[]中。当其中一个分解己不再需要进一步进行时，即找到一个解，将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时，以要进一部分解的数及分解深度为参数，递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){ int i,j; for (j=__________；j>=1；j--）{ a[k]=j; if (__________）{ printf ( "%d = %d" , a[0]，a[l]); for (i = 2 ; i < = k ; i + + ) printf ( " + % d " , a[i]); printf ( " n " ); }else test(__________，k + l ); } }

如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有【】

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

对于前序遍历和中序遍历结果相同的二叉树为__________；对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

由二叉树的前序和后序遍历序列【】唯一地确定这棵二叉树。

栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若ai=n(1≤i≤n)，则有 ak>ak+1>an。

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【】量级相当。

已知序列17，31，13，11，20，35，25，8，4，11，24，40，27，请画出该序列的二叉排序树，并分别给出下列操作后的二叉排序树：① 插入数据9；② 删除结点17；③ 再删除结点13。