第五章 图历年试题.doc

第五章 图 一、 单项选择题 201101--3.已知有向图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,V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7 201101--4.有关图中路径的定义，表述正确的是( ) A.路径是顶点和相邻顶点偶对构成的边所形成的序列 B.路径是不同顶点所形成的序列 C.路径是不同边所形成的序列 D.路径是不同顶点和不同边所形成的集合 201010--9.图的广度优先有哪些信誉好的足球投注网站使用的数据结构是( ) A．队列 B.树 C.栈 D.集合 201001--4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 200910--3.由顶点V1，V2，V3构成的图的邻接矩阵为，则该图中顶点V1的出度为（ ） A.0 B.1 C.2 D.3 200910--14.设无向图的邻接表如题14图所示，则该图的边数为（ ） 题14图 A.4 B.5 C.10 D.20 200901--11.有n个结点的无向图的边数最多为（ ） A.n+1 B. C.n（n+1） D.2n（n+1） 200901--12.设图的邻接矩阵为 则该图为（ ） A.有向图 B.无向图 C.强连通图 D.完全图 200810--10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（ ） A.0 B.1 C.n D.不确定 200810--11.下列说法中不正确的是（ ） A.无向图的极大连通子图称为连通分量 B.连通图的广度优先有哪些信誉好的足球投注网站中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先有哪些信誉好的足球投注网站中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先有哪些信誉好的足球投注网站算法 200801--10.邻接矩阵为对称矩阵的图是( ) A. 有向图 B. 带权有向图 C. 有向图或无向图 D. 无向图 200801--11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( ) A.n-1 B.n C.n+1 D. 200710--10.有4个顶点的无向完全图的边数为( ) A.6 B.12 C.16 D.20 200710--11.设图的邻接矩阵为则该图为( ) A.有向图 B.无向图 C.强连通图 D.完全图 200701--12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（ ） A．n B.n-1 C.n+1 D.2(n-1) 200701--13．关于无向图的邻接矩阵的说法中正确的是（ ） A．矩阵中非全零元素的行数等于图中的顶点数 B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数 D.第i行上非零元素个数和第i列上非零元素个数一定相等 200610--11.有n个结点的有向完全图的弧数是（ ） A.n B.2n C.n(n-1) D.2n(n+1) 200610--12.设图的邻接链表如题12图所示，则该图的边的数目是（ ） 题12图 A.4 B.5 C.10 D.20 200601--10.具有n个顶点的无向图，若要连通全部顶点，至少需要（ ） A.（n-1）条边 B. n条边 C. n(n-1)条边 D. n(n-1)/2条边 二、 填空题 201101--25.在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是___________。 201101--26.无向完全图G采用___________存储结构较省空间。 201010--26．一个具有n个顶点的有向完全图的弧数是_______。 201010--27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的_______。 20100