离散数学(本)复习题

离散数学(本) 试题


一、单项选择题(每小题3分&＃xff0c;本题共15分)
1&＃xff0e;若集合A&＃xff1d;{a&＃xff0c;b}&＃xff0c;B&＃xff1d; {a&＃xff0c;b&＃xff0c;{a&＃xff0c;b}}&＃xff0c;则( )&＃xff0e;

2&＃xff0e;集合A&＃xff1d;{1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8}上的关系R&＃xff1d;{∣x&＃43;y&＃61;10且x&＃xff0c;yA}&＃xff0c;则R的性质为( )&＃xff0e;
A&＃xff0e;自反的 B&＃xff0e;对称的
C&＃xff0e;传递且对称的 D&＃xff0e;反自反且传递的

A&＃xff0e;0 B&＃xff0e;2
C&＃xff0e;1 D. 3

4&＃xff0e;如图一所示&＃xff0c;以下说法正确的是( )&＃xff0e;
A&＃xff0e;{(a&＃xff0c;e)}是割边
B&＃xff0e;{(a&＃xff0c;e))是边割集
C. {(a&＃xff0c;e)&＃xff0c;(b&＃xff0c;c)}是边割集
D. {(d&＃xff0c;e)}是边割集

5&＃xff0e;设A(x)&＃xff1a;x是人&＃xff0c;B(x)&＃xff1a;x是学生&＃xff0c;则命题“不是所有人都是学生”可符号化为( )&＃xff0e;

二、填空题(每小题3分&＃xff0c;本题共15分)
6&＃xff0e;若集合A的元素个数为10&＃xff0c;则其幂集的元素个数&＃xff08; &＃xff09;。

9&＃xff0e;结点数v与边数e满足 关系的无向连通图就是树&＃xff0e;

三、逻辑公式翻译(每小题6分&＃xff0c;本题共12分)
11.将语句“尽管他接受了这个任务&＃xff0c;但他没有完成好&＃xff0e;”翻译成命题公式&＃xff0e;
12&＃xff0e;将语句“今天没有下雨&＃xff0e;”翻译成命题公式&＃xff0e;
四、判断说明题(每小题7分&＃xff0c;本题共14分)
判断下列各题正误&＃xff0c;并说明理由&＃xff0e;
13&＃xff0e;下面的推理是否正确&＃xff0c;试予以说明&＃xff0e;

14&＃xff0e;若偏序集的哈斯图如图二所示&＃xff0c;则集合A的最大元为a&＃xff0c;最小元不存在&＃xff0e;

五、计算题(每小题12分&＃xff0c;本题共36分)

17&＃xff0e;画一棵带权为1&＃xff0c;2&＃xff0c;2&＃xff0c;3&＃xff0c;4的最优二叉树&＃xff0c;计算它们的权&＃xff0e;在这里插入图片描述


六、证明题(本题共8分)

答案
一、单项选择题(每小题3分&＃xff0c;本题共15分)
1&＃xff0e;A 2&＃xff0e;B 3&＃xff0e;B 4&＃xff0e;D 5&＃xff0e;C
二、填空题(每小题3分&＃xff0c;本题共15分)

三、逻辑公式翻译(每小题6分&＃xff0c;本题共12分)
11&＃xff0e;设户&＃xff1a;他接受了这个任务&＃xff0c;Q&＃xff1a;他完成好了这个任务&＃xff0c;

12&＃xff0e;设户&＃xff1a;今天下雨&＃xff0c;

四、判断说明题(每小题7分&＃xff0c;本题共14分)

13&＃xff0e;错误&＃xff0e;
(2)应为F(y)一G(x)&＃xff0c;换名时&＃xff0c;约束变元与自由变元不能混淆&＃xff0e;
14&＃xff0e;错误&＃xff0e;
集合A的最大元不存在&＃xff0c;a是极大元&＃xff0e;

权为1×3&＃43;2×3&＃43;2×2&＃43;3×2&＃43;4×2&＃xff1d;27
六、证明题(本题共8分)
18&＃xff0e;证明&＃xff1a;因为n是奇数&＃xff0c;所以&＃xff0c;n阶完全图每个顶点度数为偶数&＃xff0c;
因此&＃xff0c;若G中顶点v的度数为奇数&＃xff0c;则在 中v的度数一定也是奇数&＃xff0c;所以G与 中的奇数度顶点个数相等&＃xff0e;