第五章图历年试题

数据结构自考第五章图历年试题11第五章图一、单项选择题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,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V7201101--4.有关图中路径的定义，表述正确的是()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.4B.5C.10D.20200901--11.有n个结点的无向图的边数最多为（）A.n+1B.2)1(nnC.n（n+1）D.2n（n+1）数据结构自考第五章图历年试题22200901--12.设图的邻接矩阵为则该图为（）A.有向图B.无向图C.强连通图D.完全图200810--10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（）A.0B.1C.nD.不确定200810--11.下列说法中不正确．．．的是（）A.无向图的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索算法200801--10.邻接矩阵为对称矩阵的图是()A.有向图B.带权有向图C.有向图或无向图D.无向图200801--11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为()A.n-1B.nC.n+1D.2n200710--10.有4个顶点的无向完全图的边数为()A.6B.12C.16D.20200710--11.设图的邻接矩阵为则该图为()A.有向图B.无向图C.强连通图D.完全图200701--12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A．nB.n-1C.n+1D.2(n-1)200701--13．关于无向图的邻接矩阵的说法中正确的是（）A．矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vi的度数C.矩阵中的非零元素个数等于图的边数D.第i行上非零元素个数和第i列上非零元素个数一定相等200610--11.有n个结点的有向完全图的弧数是（）A.n2B.2nC.n(n-1)D.2n(n+1)200610--12.设图的邻接链表如题12图所示，则该图的边的数目是（）数据结构自考第五章图历年试题33题12图A.4B.5C.10D.20200601--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的_______。201001--25.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。201001--26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。200910--25.在一个具有n个顶点的无向图中，顶点的度最大可达________。200910--26.有向图G的邻接矩阵为A，如果图中存在弧Vi，Vj，则A［i］［j］的值为________。200901--23.设有一稠密图G，则G采用_________存储结构较省空间。设有一稀疏图G，则G采用_________存储结构较省空间。200810--23.在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于________。200810--27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。200801--22.一个具有4个顶点的无向完全图有____________条边。200801--23.一个有向图G中若有孤Vi，Vj、Vj，Vk和Vi，Vk，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为____________。200710--22.具有n个顶点的连通图至少需有__________条边。200710--23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。200701--23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。200701--24．一个具有10个顶点的完全无向图中有_______条边。200610--23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的________。200601--24.若一个完全无向图具有n条边，则该图的顶点个数为________________。数据结构自考第五章图历年试题44三、应用题201010--32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优先搜索顶点序列。题32图200910--32.写出题32图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。题32图200901--31.已知某图的邻接表存储结构如题31图所示：（1）画出该图。（2）根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。数据结构自考第五章图历年试题55200810--31.对于题31图，试给出：（1）邻接矩阵；（2）邻接表。题31图200801--33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。题33图200710--32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。数据结构自考第五章图历年试题66四、算法设计题200610--35.下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。Voiddeledge（ALGraph*G，inti，intj）{EdgeNode*p，*q；p=G→adjlist［i］.firstedge；if（p→adjvex==j）{G→adjlist［i］.firstedge=p→next；free（p）；}else{while（p→next→adjvex!=j&&p→next）（1）________；if（p→next!=NULL）{q=p→next；（2）________；free（q）；}}p=G→adjlist［j］.firstedge；if（p→adjvex==i）{G→adlist［j］.firstedge=p→next；free（q）；}else{while（p→next→adjvex!=i&&p→next）（3）________；if（p→next!=NULL）{q=p→next；（4）________；free（q）；}}}