离散数学第七章检测题一、单项选择题（每小题2分，共20分）
1．下图中是哈密尔顿图的是( 2 )
1．下面给出的四个图中，哪个不是汉密尔顿图（（4））．
1．下列是欧拉图的是( 2 )
1．下列各图不是欧拉图的是（ 2 ）
1. 下列各图不是欧拉图的是（ 4 ）
2．设()A G 是有向图,G V E =的邻接矩阵，其第i 列中“1”的数目为（ ）。 (C)
A ．结点i v 的度数；
B ．结点i v 的出度；
C ．结点i v 的入度；
D ．结点j v 的度数。
2．设()A G 是有向图,G V E =的邻接矩阵，其第i 行中“1”的数目为（ ）。 (B)
A ．结点i v 的度数；
B ．结点i v 的出度；
C ．结点i v 的入度；
D ．结点j v 的度数。]
3．无向图G 中有16条边，且每个结点的度数均为2，则结点数是( B )
A.8
B.16
C.4
D.32
3．一个无向树中有6条边，则它结点数为（ C ）.
A 5；
B 6；
C 7；
D 8．
3．设完全二叉树T 有t 片叶子，e 条边，则有（ （3） ）．
(1)．2(1)e t >-； (2)．2(1)e t <-； (3)．2(1)e t =-； (4)．2(1)e t =+．]
4．若具有n 个结点的完全图是欧拉图，则n 为( B ).
A 偶数；
B 奇数；
C 9；
D 10．
4．无向图G 是欧拉图，当且仅当（ ）． (1)
(1)．G 连通且所有结点的度数为偶数； (2)．G 的所有结点的度数为偶数；
(3)．G 连通且所有结点的度数为奇数； (4)．G 的所有结点的度数为奇数．
5．若图G 有一条路经过图中每个结点恰好一次，则G ( C )。
A.有一条欧拉路
B.是欧拉图
C.有一条汉密尔顿路
D.是汉密尔顿图
6．无向图节点间的连通关系是一个（ ）
A 偏序关系；
B 相容关系；
C 等价关系；
D 拟序关系．]
7．下面哪一种图不一定是树（ ）． (3)
(1)．无圈连通图； (2)．有n 个结点1n -条边的连通图；
(3)．每对结点间都有路的图； (4)．连通但删去一条边就不连通的图．]
8．设Ｇ＝为无向图??E V ,，23,7==E V ，则Ｇ一定是（ （4） ）．
(1)．完全图； (2)．零图； (3)．简单图； (4)．多重图．
二、 填空题（每空1分，共20分）
1．在下图中，结点v 2的度数是
，结点v 5的度数是 。
2．在一棵根树中，有且只有一个结点的入度为__0___，其余所有结点的入度均为_1__。
2．在一棵根树中，入度为__0___的结点称为树根，出度为__0___的结点称为树叶。
3．设图111,G V E =，22221,,G E E E =?且，如果 ，则称2G 是1G 的子图，如果 ，则称2G 是1G 的生成子图。(2121,V V V V ?=)
4．在任何图,G V E =中，∑∈V
v v )deg(= 2 │E │ ，其奇数度结点的个数必为
偶数 。
5．一棵有9个叶结点的完全三叉树，有___4__个内点。 5．一棵有6个叶结点的完全二叉树，有___5__个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有__9___个叶结点。
6．设图,G V E =，{V =1v ,2v ,3v ,4}v 的邻接矩阵()A G = ?????
???????0001001111011010， 则 1v 的入度)(1v ＝ 3 ，从2v 到4v 长度为２的路共有 1 条。
三、 答题（每小题6分，共30分）
1．设图,G V E =，{V =1v ,2v ,3v ,4}v 的邻接矩阵()A G = ?????
???????0001001111011010 求 1v 的入度)(deg 1v ，4v 的出度)(deg 4v ，及从2v 到4v 长度为2的路径的条数 。 解：)(1v =3；（2分）)(4v =1；（2分）从2v 到4v 长度为2的路径有1条（2分）。
1．对有向图,G V E =，通过邻接矩阵A 解下列问题：
（1）从4v 到5v 长度为4的路有几条？