数据结构与算法-考研试题(北京大学 1996年图的应用)

问答题（1996年北京大学）

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

拓扑序列

答案解析

1 5 2 3 6 4

1 5 2 6 3 4

1 5 6 2 3 4

5 6 1 2 3 4

5 1 6 2 3 4

5 1 2 6 3 4

5 1 2 3 6 4

讨论

数据结构与算法

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

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

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

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

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

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

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

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

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

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

图

已知有向图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个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。

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

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

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

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

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

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

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

图的应用

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

顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 listarray [ 0 ... n-1] ，队列头指针为front ，队列尾指针为 rear ，则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

已知结点指针p、q分别表示双向链表中任意两个相邻结点（即p->rlink=q且q->llink=p），请写出删除q所指结点的程序段。

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

二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。

若散列表的负载因子α<1，则可避免碰撞的产生。

最佳二叉树是AVL树（平衡二叉树）。

在分块检索中，对256个元素的线性表分成__________块最好，每块的最佳长度是__________；若每块的长度为8，其平均检索长度为__________。

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

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