第五章 图历年试题.doc

6
数据结构自考 第五章 图历年试题
第五章 图
一、 单项选择题
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的_______。
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条边，则该图的顶点个数为________________。

6

三、 应用题
201010--32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优先搜索顶点序列。
题32图
200910--32.写出题32图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。
题32图

200901--31.已知某图的邻接表存储结构如题31图所示：

（1）画出该图。
（2）根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。

200810--31.对于题31图，试给出：
（1）邻接矩阵；
（2）邻接表。
题31图
200801--33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。

题33图
200710--32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。

四、 算法设计题

200610--35.下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。
Void deledge（ALGraph *G，int i，int j）
{ 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）；}
}
}