目前最完整的数据结构1800题包括完整答案-第七章-图

1第七章图一、选择题1．图中有关路径的定义是（）。【北方交通大学2001一、24（2分）】A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2【清华大学1998一、5（2分）】【西安电子科技大1998一、6（2分）】【北京航空航天大学1999一、7（2分）】3．一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学1999四、4(4分)】A．n-1B．nC．n+1D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。【北京航空航天大学2000一、6(2分）】A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（）。【中山大学1998二、9（2分）】A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。A．0B．1C．n-1D．n【北京邮电大学2000二、5（20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学2001二、3（2分）】A．1/2B．2C．1D．48．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为()。【中山大学1999一、14】A．5B．6C．8D．99．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。A．逆拓扑有序B．拓扑有序C．无序的【中科院软件所1998】10．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表【北京工业大学2001一、3(2分)】11．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学2001一、11（2分）】A．有向图B．无向图C．AOV网D．AOE网12．从邻接矩阵010101010A可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。【中科院软件所1999六、2（3分）】①．A．9B．3C．6D．1E．以上答案均不正确②．A．5B．4C．3D．2E．以上答案均不正确③．A．5B．4C．3D．2E．以上答案均不正确2abedcf13．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。【南京理工大学1998一、4(2分）】A．nijiA1],[B．n1jj,iAC．niijA1],[D．nijiA1],[+n1ji,jA14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查（）的第i行第j列的元素是否为零即可。【武汉大学2000二、7】A．mAB．AC．AmD．Am-115.下列说法不正确的是（）。【青岛大学2002二、9（2分）】A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。【南京理工大学2001一、14（1.5分）】A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b17.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）【南京理工大学2000一、20（1.5分）】aebdfcacfdebaedfcbaefdcbaefdbcA．5个B．4个C．3个D．2个第17题图第18题图18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(①)，而进行广度优先遍历得到的顶点序列是（②）。【中科院软件所1999六、2-（1）（2分）】①．A．1354267B．1347652C．1534276D．1247653E．以上答案均不正确②．A．1534267B．1726453C．l354276D．1247653E．以上答案均不正确19．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学20004、2（4分）】A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径20.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)【合肥工业大学2001一、2（2分）】21.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（1），下面步骤重复n-1次:a：（2）；b：（3）；最后：（4）。【南京理工大学1997一、11_143（8分）】（1）．A．VT，ET为空B．VT为所有顶点，ET为空C．VT为网中任意一点，ET为空D．VT为空，ET为网中所有边（2）．A.选i属于VT，j不属于VT，且（i，j）上的权最小B．选i属于VT，j不属于VT，且（i，j）上的权最大C．选i不属于VT，j不属于VT，且（i，j）上的权最小D．选i不属于VT，j不属于VT，且（i，j）上的权最大（3）．A．顶点i加入VT，（i,j）加入ETB.顶点j加入VT，（i,j）加入ETC.顶点j加入VT，（i,j）从ET中删去D．顶点i,j加入VT，（i,j）加入ET（4）．A．ET中为最小生成树B．不在ET中的边构成最小生成树C．ET中有n-1条边时为生成树，否则无解D．ET中无回路时，为生成树，否则无解22.(1).求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是（）。【南京理工大学2000一、21（1.5分）】A．(1),(2),(3)B．(1)C．(1),(3)D．(2),(3)23．当各边上的权值()时，BFS算法可用来解决单源最短路径问题。【中科院计算所2000一、3(2分）】A．均相等B．均互不相等C．不一定相等24.求解最短路径的Floyd算法的时间复杂度为()。【合肥工业大学1999一、2（2分）】A．O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）25．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7【北京航空航天大学2000一、7（2分）】26．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。A．存在B．不存在【中科院计算所1998二、6(2分）】【中国科技大学1998二、6（2分）】27．一个有向无环图的拓扑排序序列（）是唯一的。【北京邮电大学2001一、3（2分）】A．一定B．不一定28.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径【南京理工大学2000一、9（1.5分）】429.在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)【合肥工业大学2000一、2（2分）】【南京理工大学2001一、9（1.5分）】【青岛大学2002二、3（2分）】30.关键路径是事件结点网络中（）。【西安电子科技大学2001应用一、4（2分）】A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路31.下面关于求关键路径的说法不正确的是（）。【南京理工大学1998一、12（2分）】A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上32．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成【北方交通大学1999一、7（3分）】【北京工业大学1999一、1(2分)】二、判断题1.树中的结点和图中的顶点就是指数据结构中的数据元素。（）【青岛大学2001四、1（1分）】2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）【中科院软件所1997一、4(1分）】3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=niViTD1)(。（）【南京航空航天大学1996六、4（1分）】4.有e条边的无向图，在邻接表中有e个结点。（）【南京理工大学1998二、5（2分）】5.有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）【合肥工业大学2001二、7(1分）】6．强连通图的各顶点间均可达。（）【北京邮电大学2000一、3（1分）】7．强连通分量是无向图的极大强连通子图。（）【北京邮电大学2002一、7（1分）】8．连通分量指的是有向图中的极大连通子图。（）【燕山大学1998二、4（2分）】9．邻接多重表是无向图和有向图的链式存储结构。（）【南京航空航天大学1995五、5（1分）】10.十字链表是无向图的一种存储结构。（）【青岛大学2001四、7（1分）】11.无向图的邻接矩阵可用一维数组存储。（）【青岛大学2000四、5（1分）】12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）【东南大学2001一、4（1分）】【中山大学1994一、3（2分）】13．有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。（）5【北京邮电大学1998一、5（2分）】14.有向图的邻接矩阵是对称的。（）【青岛大学2001四、6（1分）】15．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）【东南大学2001一、3（1分）】【哈尔滨工业大学1999三、4】16.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）【上海海运学院1995一、9（1分）1997一、8（1分）1998一、9（1分）】17.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）【上海海运学院1996一、8（1分）1999一、9（1分）】18．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）【上海交通大学1998一、12】19．需要借助于一个队列来实现DFS算法。（）【南京航空航天大学1996六、8（1分）】20.广度遍历生成树描述了从起点到各顶点的最短路径。（）【合肥工业大学2001二、8（1分）】21．任何无向图都存在生成树。（）【北京邮电大学2000一、1（1分）】22.不同的求最小生成树的方法最后得到的生成树是相同的.（）【南京理工大学1998二、3（2分）】23．带权无向图的最小生成树必是唯一的。（）【南京航空航天大学199