资源描述：
《数据结构 习题 第七章 图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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个顶点的有向图，至少需
2、要（）条边。【北京航空航天大学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)*（（
3、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．从邻接阵矩可以看出，该图共有（①）个顶点
4、；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。【中科院软件所1999六、2（3分）】①．A．9B．3C．6D．1E．以上答案均不正确②．A．5B．4C．3D．2E．以上答案均不正确③．A．5B．4C．3D．2E．以上答案均不正确13．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。【南京理工大学1998一、4(2分）】A．B．C．D．+14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查（）的第i行第j列的元素是否为零即可。【武汉大学2000二、7】A．mAB．AC．AmD．Am-115.下列说法不正确的是（）。【青岛
5、大学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个序列中，符合深度优先遍
6、历的序列有多少？（）【南京理工大学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．下面哪一方法可以判断出一个有向图是否有环
7、（回路）：【东北大学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）。【南
