哈尔滨工程大学考研-数据结构-7

11V0V1V2V3一、判断题1．求最小生成树的Prim算法在边较少、结点较多时效率较高。2．图的最小生成树的形状可能不唯一。3．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。4．邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。5．任何有向网络（AOV-网络）拓扑排序的结果是唯一的。6．有回路的图不能进行拓扑排序。7．存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。8．用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可。9．AOE网中一定只有一条关键路径。10．关键路径上活动的工期一定能够缩短整个工程的工期。二、选择题1．N条边的无向图的邻接表的存储中，边表的个数有（）。A）NB）2NC）N/2D）N*N2．最短路径的生成算法可用（）。A）普里姆算法B）克鲁斯卡尔算法C）迪杰斯特拉算法D）哈夫曼算法3．有拓扑排序的图一定是（）。A）有环图B）无向图C）强连通图D）有向无环图4．图的邻接表如下图所示：vertexfirstedge13∧023∧01∧（选择题5图）5．点V0出发进行深度优先搜索，经历的结点顺序为（）。A）V0,V3,V2,V1B）V0,V1,V2,V3C）V0,V2,V1,V3D）V0,V1,V3,V226．设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（）。A）O(nlog2e)B）O(en)C）O(elog2n)D）O(n+e)7．对于含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小代价生成树其时间复杂度为（）。A）O(elog2e)B）O(en)C）O(elog2n)D）O(nlog2n)8．关键路径是事件结点网络中（）。A）从源点到汇点的最长路径B）从源点到汇点的最短路径C）最长的回路D）最短的回路9．N个顶点的强连通图至少有（（1））条边。（1）A）nB）n＋1C）n－1D）n（n－1）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)三、填空题1．具有n个顶点的无向完全图，边的总数为_______条；而在n个顶点的有向完全图中，边的总数为_______条。2．一个图的生成树的顶点是图的___________顶点。3．写出下图所示的所有拓扑序列__________________________________。(填空题5图)4．在如下图所示的网络计划图中关键路径是____________，全部计划完成的时间是_____________。5308207.2244.56.5812151114171316V0v1V5V2V6V3V413（填空题9图）5．设G有n个顶点和e条边，进行广度优先搜索的时间复杂度至多为_______。当G是非孤立顶点的连通图时有2e≥n,故可推得广度优先搜索的时间复杂度为_______。6．一个连通图的生成树是一个_______连通子图，n个顶点的生成树有_______条边。7．对于含有n个顶点e条边的无向连通图，利用prim算法生成最小代价生成树其时间复杂度为_________。四、简答题1．对于如图所示的有向图，试给出（1）每个顶点的入度和出度；①④（2）邻接矩阵；⑤（3）邻接表；（4）逆邻接表；⑥（5）强连通分量。②③2．设无向图G如图所示（简答题1图）試给出（1）该图的邻接矩阵；（2）该图的邻接表；（3）该图的多重邻接表；（4）从A出发的“深度优先”遍历序列；（5）从A出发的“广度优先”遍历序列。3．设有向图G如图所示（简答题2图）试画出图G的十字链表结构，并写出图G的两个拓扑序列。8352（简答题3图）（简答题4图）4．试利用弗洛伊德（R.W.Floyed）算法，求图所示有向图的各对顶点之间的最短路径，并写出在执行算法过程中，所得的最短路径长度矩阵序列和最短路径矩阵序列。5．下表列出了某工序之间的优先关系和各工序所需时间，求：工序代号所需时间前序工序工序代号所需时间前序工序ABCDEFG15105081540300无无ABC,DBEHIJKLM1512060153020G,IEIF,IH,J,KLV1V0V2V4V3V6V5V2v1V3V6V5V41CBA4（简答题5表）(1)画出AOE网；(2)列出各事件中的最早、最迟发生时间；(3)找出该AOE网中的关键路径，并回答完成该工程需要的最短时间。