2023年7月19日发(作者：)

6，7章自测题（只有小题）

（第六 七章 图论部分）

1、设G是一个哈密尔顿图，则G一定是( )。

(1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图

2、下面给出的集合中，哪一个是前缀码？( )

(1) {0，10，110，101111} (2) {01，001，000，1}

(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

3、一个图的哈密尔顿路是一条通过图中(所有结点一次且恰好经过一次 )的路。

4、在有向图中，结点v的出度deg+(v)表示(

以v为起始点的所有边

)，入度deg-(v)表示(

以v为终点的所有边 )。

5、一棵无向树的顶点数n与边数m关系是(n=m+1 )。

6、一个图的欧拉回路是一条通过图中(所有的边一次且恰好一次 )的回路。

7、有n个结点的树，其结点度数之和是( 2(n-1) )。

8、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}

(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}

9、n个结点的有向完全图边数是(n（n-1） )，每个结点的度数是(2（n-1） )。

10、一个无向图有生成树的充分必要条件是( 图是连通的 )。

11、设G是一棵树，n,m分别表示顶点数和边数，则

(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

12、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( 2 )片树叶。

13、任何连通无向图G至少有( 1 )棵生成树，当且仅当G 是( 树 )，G的生成树只有一棵。

14、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:m-n+2 (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

15、设T是一棵树，则T是一个连通且(没有回路的无向图 )图。

16、设无向图G有16条边且每个顶点的度数都是2，则图G有(16 )个顶点。

(1) 10 (2) 4 (3) 8 (4) 16

17、任一有向图中，度数为奇数的结点有(偶数个 )个。

18、在有n个顶点的连通图中，其边数（ ）。

(1) 最多有n-1条 (2) 至少有n-1 条

(3) 最多有n条 (4) 至少有n 条

19、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（(1) 5 (2) 7 (3) 8 (4) 9

）。 9