2024年3月11日发(作者：比亚迪l3论坛)
第七章 图
一、选择题
1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
2．设无向图的顶点个数为n，则该图最多有（ ）条边。
2
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n
【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】
【北京航空航天大学 1999 一、7 （2分）】
3．一个n个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4
分)】
A．n-1 B．n C．n+1 D．nlogn；
4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、
6(2分）】
A．n-l B．n C．n+l D．2n
5．n个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2分）】
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
6．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A．0 B．1 C．n-1 D．n
【北京邮电大学 2000 二、5 （20/8分）】
7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所
有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2
分）】
A．1/2 B．2 C．1 D．4
8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。【中山大学
1999一、14】
A．5 B．6 C．8 D．9
9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点
序列是( )。
A．逆拓扑有序 B．拓扑有序 C．无序的 【中科院软件所
1998】
10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。
A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接
表
【北京工业大学 2001 一、3 (2分)】
11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】
A．有向图 B．无向图 C．AOV网 D．AOE网
?
0
A?
?
?
1
?
?
0
1
0
1
0
?
1
?
?
0
?
?
可以看出，该图共有（①）个顶点；如果是有向图该图共有12． 从邻接阵矩
（②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】
①．A．9 B．3 C．6 D．1 E．以上答案均不正确
②．A．5 B．4 C．3 D．2 E．以上答案均不正确
③．A．5 B．4 C．3 D．2 E．以上答案均不正确
13．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。【南京理工大学1998
一、4(2分）】
A．
?
A[i,j]
i?1
n
B．
?
A
?
i,j
?
j?1
n
C．
?
A[j,i]
i?1
n
D．
?
A[i,j]
?
A
?
j,i
?
i?1
n
n
+
j?1
14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连，
则只要检查（ ）的第i行第j列的元素是否为零即可。【武汉大学 2000 二、7】
m
A．mA B．A C．A D．Am-1
15. 下列说法不正确的是（ ）。【青岛大学 2002 二、9 （2分）】
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用
于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个
递归过程
16．无向图G=(V,E),其中：V={a,b,c,d,e,f},
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶
点序列正确的是（ ）。【南京理工大学 2001 一、14 （1.5分）】
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
17. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）
【南京理工大学 2000 一、20 （1.5分）】
a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
A．5个 B．4个 C．3个 D．2个
a
bec
df
第17题图 第18题图
18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序
列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。【中科院软件所 1999 六、2-
（1）（2分）】
①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均
不正确
②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案
均不正确
19．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
20. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
23
A. O(n) B. O(n+e) C. O(n) D. O(n)
【合肥工业大学 2001 一、2 （2分）】
21. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），
更多推荐
顶点,遍历,深度,是否,表示
发布评论