离散数学(专升本)阶段性作业3.doc

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