离散数学(专升本)阶段性作业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分) 正确错误 参考答案:错误 解题思路:
填空题
则从G中删去_＿_＿(１)___ _条边可以得到树、（419、 设Ｇ就是5个顶点得完全图，分)
(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
离散数学(专升本)阶段性作业3
