第七章  图

一、选择题

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．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】

[1] [2] [3] [4] [5] [6] [7] [8] [9] [下一页] [尾页]

交流计算机等级考试经验请进计算机等级论坛>>