第七章 
一、选择题
1.图中有关路径的定义是(    )。【北方交通大学 2001 一、24 2分)】
A.由顶点和相邻顶点序偶构成的边所形成的序列      B.由不同顶点所形成的序列
C.由不同边所形成的序列                          D.上述定义都不是
2.设无向图的顶点个数为n,则该图最多有(  )条边。
An-1        Bn(n-1)/2      C n(n+1)/2        D0      En2
【清华大学 1998 一、5 2分)】【西安电子科技大 1998 一、6 2分)】
【北京航空航天大学 1999 一、7 2分)】
3.一个n个顶点的连通无向图,其边的个数至少为(    )。【浙江大学 1999 四、4 (4)
An-1          Bn            Cn+1            Dnlogn
4.要连通具有n个顶点的有向图,至少需要(    )条边。【北京航空航天大学 2000 一、6(2分)】
An-l          Bn            Cn+l            D2n
5n个结点的完全有向图含有边的数目(   )。【中山大学 19989 2分)】
An*n        B.nn+1)    Cn2            Dn*nl
6.一个有n个结点的图,最少有(    )个连通分量,最多有(    )个连通分量。
A0                B1                Cn-1            Dn
【北京邮电大学 2000 二、5 20/8分)】
7.在一个无向图中,所有顶点的度数之和等于所有边数(    )倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的(    )倍。【哈尔滨工业大学 2001 二、3 2分)】
A1/2          B2            C1              D4
8.用有向无环图描述表达式(A+B)*((A+B/A),至少需要顶点的数目为(  )。【中山大学199914
A5          B6              C8              D9   
9.用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是(  )
A.逆拓扑有序        B.拓扑有序            C.无序的      【中科院软件所 1998
10.下面结构中最适于表示稀疏无向图的是(    ),适于表示稀疏有向图的是(    )。
A.邻接矩阵      B.逆邻接表    C.邻接多重表      D.十字链表    E.邻接表         
【北京工业大学 2001 一、3 (2)
11.下列哪一种图的邻接矩阵是对称矩阵?(    )【北方交通大学 2001 一、11 2分)】
A.有向图            B.无向图          CAOV          DAOE
12  从邻接阵矩 可以看出,该图共有()个顶点;如果是有向图该图共有( 条弧;如果是无向图,则共有()条边。【中科院软件所 1999 六、23分)】
A9    B3      C6    D1    E.以上答案均不正确
A5    B4      C3    D2    E.以上答案均不正确
A5    B4      C3    D2    E.以上答案均不正确
13.当一个有N个顶点的图用邻接矩阵A表示时,顶点Vi的度是( )。【南京理工大学1998一、4(2分)】
A      B      C      D+
14.用相邻矩阵A表示图,判定任意两个顶点ViVj之间是否有长度为m 的路径相连,则只要检查(    )的第i行第j列的元素是否为零即可。【武汉大学 20007
AmA        BA            CAm             DAm-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分)】
Aa,b,e,c,d,f    Ba,c,f,e,b,d      Ca,e,b,c,f,d      Da,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
A5            B4          C3          D2 
            17题图                                  18题图
18.下图中给出由7个顶点组成的无向图。从顶点1出发,对它进行深度优先遍历得到的序列是(),而进行广度优先遍历得到的顶点序列是( )。【中科院软件所 1999 六、2-1)(2分)】
A1354267    B1347652    C1534276    D1247653    E.以上答案均不正确
A1534267    B1726453    Cl354276    D1247653    E.以上答案均不正确 
19.下面哪一方法可以判断出一个有向图是否有环(回路):【东北大学 2000 424分)】
A.深度优先遍历  B. 拓扑排序  C. 求最短路径  D. 求关键路径
20. 在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为(    )
A. O(n)            B. O(n+e)        C. O(n2)      D. O(n3)
【合肥工业大学 2001 一、2 2分)】
21. 下面是求连通网的最小生成树的prim算法:集合VTET分别放顶点和边,初始为( 1 ),下面步骤重复n-1: a:( 2 );b:( 3 );最后:( 4 )。【南京理工大学 1997 一、11_14 8分)】
1).AVTET为空                      BVT为所有顶点,ET为空
          CVT为网中任意一点,ET为空        DVT为空,ET为网中所有边
2).A. i属于VTj不属于VT,且(ij)上的权最小
          B.选i属于VTj不属于VT,且(ij)上的权最大
          C.选i不属于VTj不属于VT,且(ij)上的权最小
          D.选i不属于VTj不属于VT,且(ij)上的权最大
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).AET 中为最小生成树                    B.不在ET中的边构成最小生成树
          CET中有n-1条边时为生成树,否则无解  DET中无回路时,为生成树,否则无解
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分)】
AOn        B. On+c    C. On*n    D. On*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
的拓扑序列是(  )。
AV1,V3,V4,V6,V2,V5,V7            BV1,V3,V2,V6,V4,V5,V7
CV1,V3,V4,V5,V2,V6,V7            DV1,V2,V5,V3,V4,V6,V7
【北京航空航天大学 2000 一、7 2分)】
26.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列(    )。 
A.存在  B.不存在【中科院计算所1998 二、6 (2分)】【中国科技大学 1998二、62分)】

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。