第五章 图历年试题

《第五章 图历年试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6数据结构自考第五章图历年试题第五章图一、单项选择题201101--3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={，，，，,，，,，}，则图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,V7201101--4.有关图中路径的定义，表述

2、正确的是()A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合201010--9.图的广度优先搜索使用的数据结构是()A．队列B.树C.栈D.集合201001--4.在一个图中，所有顶点的度数之和与图的边数的比是()A.1∶2B.1∶1C.2∶1D.4∶1200910--3.由顶点V1，V2，V3构成的图的邻接矩阵为，则该图中顶点V1的出度为（）A.0B.1C.2D.3200910--14.设无向图的邻接表如题14图所示，则该图的边数为（）题14图A

3、.4B.5C.10D.20200901--11.有n个结点的无向图的边数最多为（）A.n+1B.C.n（n+1）D.2n（n+1）66数据结构自考第五章图历年试题200901--12.设图的邻接矩阵为则该图为（）A.有向图B.无向图C.强连通图D.完全图200810--10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（）A.0B.1C.nD.不确定200810--11.下列说法中不正确的是（）A.无向图的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.连通图的深度优先搜索中一般要采用栈来暂存刚

4、访问过的顶点D.有向图的遍历不可采用广度优先搜索算法200801--10.邻接矩阵为对称矩阵的图是()A.有向图B.带权有向图C.有向图或无向图D.无向图200801--11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为()A.n-1B.nC.n+1D.200710--10.有4个顶点的无向完全图的边数为()A.6B.12C.16D.20200710--11.设图的邻接矩阵为则该图为()A.有向图B.无向图C.强连通图D.完全图200701--12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A．nB.n-1C.n+

5、1D.2(n-1)200701--13．关于无向图的邻接矩阵的说法中正确的是（）A．矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vi的度数C.矩阵中的非零元素个数等于图的边数D.第i行上非零元素个数和第i列上非零元素个数一定相等200610--11.有n个结点的有向完全图的弧数是（）A.nB.2nC.n(n-1)D.2n(n+1)200610--12.设图的邻接链表如题12图所示，则该图的边的数目是（）题12图A.4B.566数据结构自考第五章图历年试题C.10D.20200601--10.具有n个顶点的无

6、向图，若要连通全部顶点，至少需要（）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的_______。201001--25.含有n个顶点和n-1条边的连通

7、图G采用____________存储结构较省空间。201001--26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。200910--25.在一个具有n个顶点的无向图中，顶点的度最大可达________。200910--26.有向图G的邻接矩阵为A，如果图中存在弧，则A［i］［j］的值为________。200901--23.设有一稠密图G，则G采用_________存储结构较省空间。设有一稀疏图G，则G采用_________存储结构较省空间。200810--23.在无向图G的邻接矩阵A中，若A［i］［

8、j］等于0，则A［j］［i］等于________。200810--27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为_______