离散数学答案2023秋

第七章测试

1.在下列哈斯图表示的偏序集中，构成格的是( )
A: B: C:
D:
答案:D
2.下列关于格〈L ,≤〉的说法正确的是( )
A:用表示和在偏序关系中的最小上界
B:和两种运算都满足交换律和结合律
C:∀A L ,子集A必有最小上界和最大下界
D:用表示和在偏序关系中的上界
3.假设＜L, ⊕, * ＞是一个格, ＜S, ⊕, * ＞是＜L, ⊕, * ＞的子格。下列说法错误的是( )
A:对于任意的a,b,c∈L,若b≤c ，则a⊕b≤a⊕c
B:＜S, ⊕, * ＞是＜L, ⊕, * ＞的子代数
C:＜S, ⊕, * ＞满足幂等律、交换律、结合律、吸收律，因此也是格
D:S可能为空集，若S不为空，则S唯一
4.格应满足的性质有( )
A:分配律
B:交换律
C:结合律
D:吸收律
5.在格中两个元素可比较当且仅当两个元素的最小上界和最大下界都存在。( )
A:错 B:对 1.设无向图有18条边且每个顶点的度数都为3，则图有（ ）个项点。
A:8
B:4
C:10
D:12
2.在任何图中必定有偶数个（ ）。
A:度数为偶数的结点
B:度数为奇数的结点
C:入度为奇数的结点
D:出度为奇数的结点 。
3.设无向图是连通的且 若（ ）则G是树。
A:n=m+1
B:
C:
D:m=n+1
4.设G=＜V, E＞为无向图，|V|=7, |E|= 23, 则G一定是 ( )
A:树
B:完全图
C:简单图
D:多重图或有环
5.在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。
A:4
B:3
C:2
D:1
6.

设G是一棵树，则G的生成树有（ ）棵

A:1
B:2
C:无数
D:0
7.下列不一定是树的是（ ）
A:每对结点之间都有通路的图
B:有n个结点，n-1条边的连通图
C:连通但删去一条边则不连通的图
D:无回路的连通图
8.无向图G（n, m）是树，则下列说法不正确的是（ ）。
A:删除G中任一条边后，G仍连通
B:G是连通的
C:G中无回路
D:m=n-1
9.一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（ ）片树叶。
A:6
B:4
C:3
D:5
10.下列图中（ ）是根树。
A:
B:
C:
D:
1.

下图的节点着色数 (          ).

A:5 B:3 C:4 D:2
2.

捕获6名间谍会汉语、法语和日语, 会德语、日语和俄语, 会英语和法语, 会汉语和西班牙语, 会英语和德语, 会俄语和西班牙语. 将这6人用两个房间和监禁可以使得在同一房间里的任意两人不能相互直接交谈, 这时(      ).

A:

B:

C:

D:

3.

设是连通平面图，中有7个节点3个面，则的边数是(   ).

A:8 B:6 C:7 D:9 4.

一棵树有3个5度点、1个4度点、3个2度点，其它的点都是1度，那么它的边数是（       ）

A:18 B:19 C:20 D:17 5.

下面边赋权图的最小生成树的权为(     ).

A:41 B:40 C:39 D:38 6.

从6阶完全无向图至少要删除(     )条边可得到其生成树.

A:15 B:10 C:5
D:6 7.

不同构的5阶无向树有(       )棵.

A:3 B:4 C:5 D:2 8.

设是阶简单无向图，则下列说法不正确的是 (     ).

A:

若中任意一对顶点的度数之和大于等于，则中有Hamilton路

B:

若是欧拉图，则中必有桥

C:

若是无向树，则其边数等于

D:

若中有欧拉路，则是连通图且有零个或两个奇度数顶点

9.

下面既是汉密尔顿图又是欧拉图的图形是(    ).

A:

B:

C:

D:

10.

下列图（　　）是欧拉图.

A:

B:

C:

D:

1.

A:

B:

C:

D:

2.

A:

既不是偏序关系也不是等价关系

B:

既是偏序关系又是等价关系

C:

偏序关系

D:

等价关系

3.

A:

B:

C:

D:

4.

下面四组数不能构成无向图的度数列的                                            

A:

B:

C:

D:

5.

A:

B:

C:

D:

6.

A:

4

B:

5

C:

6

D:

8

7.

A:

8

B:

10

C:

12

D:

4

8.

A:

B:

C:

D:

9.

下列哪一种图不一定是树

A:对每对结点间都有通路的图 B:连通但删去任意一条边则不连通的图 C:无回路的连通图 D:

有n个结点，n-1条边的连通图

10.

A:

B:

C:

D:

11.

A:

B:

C:

D:

12.

A:

图(a)是强连通的

B:

图(c)是强连通的

C:

 图(b)是强连通的

D:

图(d)是强连通的

13.

A:

B:

C:

D:

14.

A:

B:

C:

D:

15.

A:

B:

C:

D:

1.任何树T都至少有两片叶子。（ ）
A:对 B:错 2.任何无向树都是二部图。（ ）
A:对 B:错 3.{0000，0010，010，011，111，01，10}是一个前缀码。（ ）
A:对 B:错 4.设 是一棵完全二叉树，则 的每个结点都（ ）。
A:至少有两个子结点 B:可以有任意多个子结点 C:至多有两个子结点 D:恰有两个子结点 5.设 是一棵有 ( 2）个顶点的树，则 有n-1条边.（ ）
A:错 B:对 1.具有2个顶点的非同构无向树有几棵（ ）。
A:3
B:4
C:1
D:2
2.具有4个顶点的非同构无向树有几棵（ ）。
A:4
B:3
C:2
D:1
3.具有6个顶点的非同构无向树有几棵（ ）。
A:6
B:5
C:3
D:4
4.一棵树有7片树叶、3个3度顶点、其余都是4度顶点，则该树有1个4度顶点。（ ）
A:对 B:错 5.一棵树有2个4度顶点、3个3度顶点、其余都是树叶，则该树有10片树叶。（ ）
A:错 B:对