第七章 图
一、选择题
1.图中有关路径的定义是( )。【北方交通大学 2001 一、24 (2分)】
A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列
C.由不同边所形成的序列 D.上述定义都不是
2.设无向图的顶点个数为n,则该图最多有( )条边。
A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n2
【清华大学 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 B.n(n+1) 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网
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. B. C. D.+
14.用相邻矩阵A表示图,判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连,则只要检查( )的第i行第j列的元素是否为零即可。【武汉大学 2000、7】
A.mA B.A C.Am 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个
第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 算法的时间复杂度为( )。
A. O(n) B. O(n+e) C. O(n2) D. O(n3)
【合肥工业大学 2001 一、2 (2分)】
21. 下面是求连通网的最小生成树的prim算法:集合VT,ET分别放顶点和边,初始为( 1 ),下面步骤重复n-1次: a:( 2 );b:( 3 );最后:( 4 )。【南京理工大学 1997 一、11_14 (8分)】
(1).A.VT,ET为空 B.VT为所有顶点,ET为空
C.VT为网中任意一点,ET为空 D.VT为空,ET为网中所有边
(2).A. 选i属于VT,j不属于VT,且(i,j)上的权最小
B.选i属于VT,j不属于VT,且(i,j)上的权最大
C.选i不属于VT,j不属于VT,且(i,j)上的权最小
D.选i不属于VT,j不属于VT,且(i,j)上的权最大
(3).A.顶点i加入VT,(i,j)加入ET B. 顶点j加入数据结构与算法题库VT,(i,j)加入ET
C. 顶点j加入VT,(i,j)从ET中删去 D.顶点i,j加入VT,(i,j)加入ET
(4).A.ET 中为最小生成树 B.不在ET中的边构成最小生成树
C.ET中有n-1条边时为生成树,否则无解 D.ET中无回路时,为生成树,否则无解
22. (1). 求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无意义;
(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3 ) ;(图用邻接矩阵表
示)
(3). Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
上面不正确的是( )。【南京理工大学 2000 一、21 (1.5分)】
A.(1),(2),(3) B.(1) C.(1),(3) D.(2),(3)
23.当各边上的权值( )时,BFS算法可用来解决单源最短路径问题。【中科院计算所2000一、3 (2分)】
A.均相等 B.均互不相等 C.不一定相等
24. 求解最短路径的Floyd算法的时间复杂度为( )。【合肥工业大学 1999 一、2 (2分)】
A.O(n) B. O(n+c) C. O(n*n) D. O(n*n*n)
25.已知有向图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
【北京航空航天大学 2000 一、7 (2分)】
26.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列( )。
A.存在 B.不存在【中科院计算所1998 二、6 (2分)】【中国科技大学 1998二、6(2分)】
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论