30．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）
16
第五章 图 真题
4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1
25.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。 26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。 32.下述题32图矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。
3.由顶点V1，V2，V3构成的图的邻接矩阵为，则该图中顶点V1的出度为（ ）
A.0 B.1 C.2 D.3
14.设无向图的邻接表如题14图所示，则该图的边数为（ ）
题14图
A.4 B.5 C.10 D.20
25.在一个具有n个顶点的无向图中，顶点的度最大可达_____。
26.有向图G的邻接矩阵为A，如果图中存在弧
题32图
32.写出题32图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。
11.有n个结点的无向图的边数最多为（ ）
A.n+1 B.n(n-1)/2 C.n(n+1) D.2n(n+1)
12.设图的邻接矩阵为，则该图为（ ）
A.有向图 B.无向图 C.强连通图 D.完全图
23.设有一稠密图G，则G采用__存储结构较省空间。设有一稀疏图G，则G采用__存储结构较省空间。31.已知某图的邻接表存储结构如题31图所示： (1)画出该图。
(2)根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。
17
10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（ ） A.0 B.1 C.n D.不确定 11.下列说法中不正确的是（ ）
A.无向图的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索算法
23.在无向图G的邻接矩阵A中，若A[i][j]等于0，则A[j][i]等于________。
27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。 31.对于题31图，试给出： 1）邻接矩阵； 2）邻接表。
10.邻接矩阵为对称矩阵的图是( ) A.有向图 B.带权有向图 C.有向图或无向图 D.无向图 11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( ) A.n-1 B.n C.n+1 D.n/2 22.一个具有4个顶点的无向完全图有_________条边。
23.一个有向图G中若有孤
33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。
10.有4个顶点的无向完全图的边数为( ) A.6 B.12 C.16 D.20
11.设图的邻接矩阵为，则该图为( ) A.有向图 B.无向图 C.强连通图 D.完全图
22.具有n个顶点的连通图至少需有__________条边。
23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。
32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。
18
12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（ ）A．n B.n-1 C.n+1 D.2(n-1) 13．关于无向图的邻接矩阵的说法中正确的是（ ） A．矩阵中非全零元素的行数等于图中的顶点数
B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数 D.第i行上非零元素个数和第i列上非零元素个数一定相等
23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。
24．一个具有10个顶点的完全无向图中有_______条边。
33．已知连通网的邻接矩阵A如33题图 ， 试画出它所表示的连通网并画出该连通网的最小生成树。
11.有n个结点的有向完全图的弧数是（ ） A.n2 B.2n C.n(n-1) D.2n(n+1) 12.设图的邻接链表如题12图所示，则该图的边的数目是（ ）
题12图
A.4 B.5 C.10 D.20 23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的______。
30.已知如题30图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。
35.下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。 Void deledge（ALGraph *G，int i，int j）
19
{ 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）；} } }
9.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（ ） A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历
10.具有n个顶点的无向图，若要连通全部顶点，至少需要（ ） A.（n-1）条边 B. n条边 C. n(n-1)条边 D. n(n-1)/2条边 24.若一个完全无向图具有n条边，则该图的顶点个数为________________。 30.试用Prim算法构造题30图的最小生成树，要求分步给出构造过程。
9.具有10个顶点的有向完全图应具有( ) A.20条弧 B.50条弧C.90条弧 D.100条弧 10.从V1出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为( ) A.V1V2V3V5V4V6 B.V1V2V3V5V6V4 C.V1V5V2V3V6V4 D.V1V3V6V4V5V2 24.对于n个顶点的生成树，其边的个数为__________ 。 31．试给出题31图的邻接矩阵和邻接表表示。
8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )
20