Java__数据结构_图.docVIP

Java 数据结构 图 习 题 及答案 一 、判断题 1．求最小生成树的Prim算法在边较少、结点较多时效率较高。（ 对 ） 2．图的最小生成树的形状可能不唯一。（ 错 ） 3．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( 错 ) 邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( 错 )有向图和无向图既可以用邻接矩阵表示又可以用邻接表表示。 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。( 错 ) 有回路的图不能进行拓扑排序。( 对 )含有向环的找不到拓扑排序。 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。( 对 ) 8. 用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可。( 错 ) 在AOE网中一定只有一条关键路径。( 对 ) 缩短关键路径上活动的工期一定能够缩短整个工程的工期。( ) 连通分量是无向图中的极小连通子图。( ) 强连通分量是有向图中的极大强连通子图。( ) 二、选择题 N条边的无向图的邻接表的存储中，边表的个数有（ B ）。 A）N B）2N C）N/2 D）N*N N条边的无向图的邻接多重表的存储中，边表的个数有（ D ）。 A）N B）2N C）N/2 D）N*N 最短 路径的生成算法可用（ C ）。 A）普里姆算法 B）克鲁斯卡尔算法 C）迪杰斯特拉算法 D）哈夫曼算法 有拓扑排序的图一定是（ D ）。 A）有环图 B）无向图 C）强连通图 D）有向无环图 图的邻接表如下图所示： vertex firstedge 1 3 ∧ 0 2 3 ∧ 0 1 ∧ （选择题5图） 从顶点V0出发进行深度优先有哪些信誉好的足球投注网站，经历的结点顺序为（ B ）。 A）V0,V3,V2,V1 B）V0,V1,V2,V3 C）V0,V2,V1,V3 D）V0,V1,V3,V2 从顶点V0出发进行广度优先有哪些信誉好的足球投注网站，经历的结点顺序为（ D）。 A）V0,V3,V2,V1 B）V0,V1,V2,V3 C）V0,V2,V1,V3 D）V0,V1,V3,V2 设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（ D ）。 A）O (nlog2e) B）O (en ) C）O ( elog2n) D）O (n+e) 对于含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小代价生成树其时间复杂度为（ A ）。 A）O (elog2e) B）O (en ) C）O ( elog2n) D）O (nlog2n) 关键路径是事件结点网络中（ ）。 A）从源点到汇点的最长路径 B）从源点到汇点的最短路径 C）最长的回路 D）最短的回路 N个顶点的强连通图至少有（（1））条边，这样的有向图的形状是（（2））。 （1）A）n B）n＋1 C）n－1 D）n（n－1） （2）A）无回路 B）有回路 C）环状 D）树状 10．设G有n个顶点和e条边，进行深度优先有哪些信誉好的足球投注网站的时间复杂度至多为（（1））。当G是非孤立顶点的连通图时有2e≥n,故可推得深度优先有哪些信誉好的足球投注网站的时间复杂度为（（2））。 （1）A）O (ne) B）O (n＋e ) C）O ( elog2n) D）O (e) （2）A）O (ne) B）O (n＋e ) C）O ( elog2n) D）O (e) 三、填空题