数据结构考研分类复习真题 第七章 图[28]

数据结构考研分类复习真题 第七章 图[28]  

　　 ．请回答下列关于图(Graph)的一些问题 (每题 分)

　　( )．有n个顶点的有向强连通图最多有多少条边?最少有多少条边?

　　( )．表示有 个顶点 l 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？

　　( )．对于一个有向图 不用拓扑排序 如何判断图中是否存在环？【清华大学 一( 分)】

　　 ．解答问题 设有数据逻辑结构为

　　B = (K R)   K = {k k … k }

　　R={<k k > <k k > <k k > <k k > <k k > <k k > <k k > <k k > <k k > <k k > <k k >}

　　( )．画出这个逻辑结构的图示 ( 分)

　　( )．相对于关系r 指出所有的开始接点和终端结点 ( 分)

　　( )．分别对关系r中的开始结点 举出一个拓扑序列的例子 ( 分)

　　( )．分别画出该逻辑结构的正向邻接表和逆向邻接表 ( 分)【山东工业大学 三 ( 分)】