第七章图 选择题 1.图中有关路径的定义是()。【北方交通大学2001一、24(2分)】 A.由顶点和相邻顶点序偶构成的边所形成的序列 由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是 设无向图的顶点个数为n,则该图最多有()条边 B.n(n-1)/2 C.n(n+1)/2 【清华大学1998、5(2分)】【西安电子科技大1998一、6(2分)】 【北京航空航天大学1999、7(2分)】 3.一个n个顶点的连通无向图,其边的个数至少为()。【浙江大学1999四、4(4 分)】 4.要连通具有n个顶点的有向图,至少需要()条边。【北京航空航天大学2000一 6(2分)】 A.n-1 C.n+1 5.n个结点的完全有向图含有边的数目 )。【中山大学1998二、9(2分)】 A. n*kn B.n(n+1) C.n/2 D.n*(n-1) 6.一个有n个结点的图,最少有()个连通分量,最多有()个连通分量。 A.0 B.1 C.n-1 【北京邮电大学2000二、5(20/8分)】 7.在一个无向图中,所有顶点的度数之和等于所有边数()倍,在一个有向图中,所 有顶点的入度之和等于所有顶点出度之和的()倍。【哈尔滨工业大学2001二、3(2 分)】 A.1/2 8.用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为()。【中山大学 1999 14】 A.5 9.用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点 序列是() 逆拓扑有序 B.拓扑有序 无序的 【中科院软件所 1998】 10.下面结构中最适于表示稀疏无向图的是(),适于表示稀疏有向图的是()。 A.邻接矩阵 B.逆邻接表C.邻接多重表 D.十字链表E.邻接 【北京工业大学2001一、3(2分)】 11.下列哪一种图的邻接矩阵是对称矩阵?()【北方交通大学2001一、11(2分)】 A.有向图 B.无向图 C.AOV网 D.AOE网 12.从邻接阵矩Lo 以看出,该图共有(①)个顶点:如果是有向图该图共有 (②)条弧:如果是无向图,则共有(③)条边。【中科院软件所1999六、2(3分)】 ①.A.9B.3 C.6D.1E.以上答案均不正确 ②.A.5B.4C.3D.2E.以上答案均不正确 ③.A.5B.4C.3D.2E.以上答案均不正确第七章 图 一、选择题 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 2 【清华大学 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 网 12． 从邻接阵矩           = 0 1 0 1 0 1 0 1 0 A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 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．以上答案均不正确