2024年离散数学专升本阶段性作业.doc

离散数学(专升本)阶段性作业3
总分: 100分 考试时间:分钟
单项选择题
1. 集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,yA}，则R 的性质为_____。(5分)
(A) 自反的
(B) 对称的
(C) 传递的，对称的
(D) 传递
参考答案：B
2. 设G是一个哈密尔顿图，则G一定是_____。(5分)
(A) 欧拉图
(B) 树
(C) 平面图
(D) 连通图
参考答案：D
3. 设G是一棵树，则G 的生成树有_____棵。(5分)
(A) 0
(B) 1
(C) 2
(D) 不能确定
参考答案：B
4. 设无向图G有16条边且每个顶点的度数都是2，则图G有_____个顶点。(5分)
(A) 10
(B) 4
(C) 8
(D) 16
参考答案：D
5. 连通图G是一棵树当且仅当G中_____。(5分)
(A) 有些边是割边
(B) 每条边都是割边
(C) 所有边都不是割边
(D) 图中存在一条欧拉途径
参考答案：B
6. 下列哪一个图不一定是树_____。(5分)
(A) 无简单回路的连通图
(B) 有n个顶点n-1条边的连通图
(C) 每对顶点间都有通路的图
(D) 连通但删去一条边便不连通的图
参考答案：C
多项选择题
7. 下面给出的集合中，哪一个是前缀码_____。(5分)
(A) {a，ab，110，a1b11}
(B) {01，001，000，1}
(C) {1，2，00，01，0210}
(D) {12，11，101，002，0011}
参考答案：B,C,D
8. 集合A上的等价关系有性质 _____(5分)
(A) 自反性
(B) 对称性
(C) 传递性
(D) 反自反性
参考答案：A,B,C
9. 若一棵完全二元（叉）树有2n-1个顶点，则它的树叶片数不为_____。(4分)
(A) n
(B) 2n
(C) n-1
(D) 2
参考答案：B,C,D
10. 设图G的相邻矩阵为，则G的顶点数与边数不为下列成果的是_____.(4分)
(A) 4,5
(B) 5, 6
(C) 4, 10
(D) 5, 8.
参考答案：B,C,D
判断题
11. 有n个顶点n-1条边的连通图是树。(5分)
正确错误
参考答案：正确
解题思绪：
12. 在有n个顶点的连通图中，其边数最多有n-1条。(5分)
正确错误
参考答案：错误
解题思绪：
13. 任一无向图中，度数为奇数的结点有偶数个。(4分)
正确错误
参考答案：正确
解题思绪：
14. 任何连通无向图G最少有一棵生成树。(4分)
正确错误
参考答案：正确
解题思绪：
15. 集合A上的偏序关系的逆是偏序。(4分)
正确错误
参考答案：正确
解题思绪：
16. 不存在集合A上的既是等价关系又是偏序关系的例子。(4分)
正确错误
参考答案：错误
解题思绪：
17. 集合A上的关系的传递闭包是包括有传递性的最小关系。(3分)
正确错误
参考答案：正确
解题思绪：
18. 设集合A={1,2,3},A上的关系{(1,1),(2,2),(2,3),(3,2),(3,3)}则R不具备对称性.(3分)
正确错误
参考答案：错误
解题思绪：
填空题
19. 设G是5个顶点的完全图，则从G中删去____(1)___ _条边能够得到树.(4分)
(1).
参考答案:
6
20. 一个图的哈密尔顿路是一条通过图中____(2)___ _的路。(4分)
(1).
参考答案:
所有结点一次且恰好一次
21. 一棵无向树的顶点数n与边数m关系是____(3)___ _。(4分)
(1).
参考答案:
m=n-1
22. 有n个结点的树，其结点度数之和是____(4)___ _。(4分)
(1).
参考答案:
2n-2
23. 设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为____(5)___ _，分枝点数为____(6)___ _(4分)
(1).
参考答案:
12
(2).
参考答案:
3