离散数学模拟考试习题

离散数学模拟试题1一．单项选择题（每小题2分，共48分）。

1．设R 是集合A={1，2，3，4}上的二元关系，R={〈1，4〉，〈4，1〉〈1，3〉，〈3，1〉， 〈2，4〉，〈4，2〉}，下面（ ）命题为真。

Ⅰ．R R是对称的 Ⅱ．R R 是自反的 Ⅲ．R R 不是传递的（A ）仅Ⅰ （B ）仅Ⅱ （C ）仅Ⅰ和Ⅱ （D ）全真2．设N 为自然数集合，+、－、×分别为普通的加法、减法和乘法。

〈N ，*〉在下面四种情况下不构成代数系统的为（ ）。

（A ）x*y=x+y －2×x ×y (B)x*y=x+y (C)x*y=x ×y (D)x*y=│x │+│y │ 3.设图G 的顶点为五边形P 的顶点，其边为P 的边加上另一条连接P 的两个不相邻顶点的边。

下列命题中，（ ）命题是真命题。

Ⅰ．G 中存在欧拉回路 Ⅱ．G 中存在哈密尔顿回路（A ）均不是 （B ）只有Ⅰ （C ）只有Ⅱ （D ）Ⅰ和Ⅱ 4．设T 为n （n ≥3）阶无向树，T 有（ ）条割边。

（A ）n 条 （B ）n-2条 （C ）n-1条 （D ）没有 5．设A={1，2，3，4，5，6}，R 是集合A 上的整除关系，下面命题中，（ ）是假的。

（A ）4，5，6全是A 的极大元 （B ）A 没有最大元 （C ）6是A 的上界 （D ）1是A 的最大下界 6．设A={1，2，3，4，5}，则A 有（ ）个子集。

（A ）16 （B ）32 （C ）64 （D ）128 7．设连通图G 有8个顶点和12条边，则任意一棵G 的生成树的总边数为（ ）。

（A ）12 （B ）9 （C ）8 （D ）7 8．设无向图G=〈V ，E 〉，其中V={54321,,,,v v v v v }，E={),(),,(),,(),,(),,(4332214441v v v v v v v v v v }下列命题为真的是（ ）。

（A ）G 是哈密尔顿图 （B ）G 是欧拉图 （C ）G 是二分图 （D ）G 是平面图 9．设R +为正实数集合，〈R +，*〉在下面四种运算下不构成代数系统的是（ ）。

（A ）*代表普通加法 （B ）*代表普通乘法（C ）*代表普通除法 （D ）*代表普通减法 10．对于一个只有4个不同元素的集合A 来说，A 上的不同的二元关系的总数为（ ）。

（A ）42 （B ）24 （C ）162（D ）取决于元素是否为数值11．设无向树T 由3个3度顶点，2个2度顶点。

其余顶点都是树叶，则T 有（ ）片树叶。

（A ）3 （B ）4 （C ）5 （D ）6 12．下面集合之间的包含和属于关系中，（ ）为真。

Ⅰ Φ⊆ΦⅡ {}{}{}{}ΦΦΦ∈Φ,, Ⅲ {}{}{}b a b a b a ,,,,⊆Ⅳ{}{}{}c b a b a b a ,,,,,∈（A ）Ⅰ和Ⅱ （B ）Ⅰ和Ⅲ （C ）Ⅰ和Ⅳ （D ）Ⅱ、Ⅲ和Ⅳ 13．设C B f →:，B A g →:。

若g f 是满射，则下面命题为真的是（ ）。

（A ）f是满射 （B ）f是单射 （C ）f是双射 （D ）g 是满射14．设⋅=,S V ，其中•为矩阵乘法，⎭⎬⎫⎩⎨⎧∈⎪⎪⎭⎫ ⎝⎛=R b a b a S , 00，⎭⎬⎫⎩⎨⎧∈⎪⎪⎭⎫ ⎝⎛=R a a T 000 则下面命题为真的是（ ）。

Ⅰ V 是一个半群Ⅱ 〈T ，• 〉是V 的子独异点 Ⅲ 〈T ，• 〉是V 的子半群（A ）只有Ⅰ （B ）只有Ⅱ （C ）Ⅰ和Ⅱ （D ）全为真 15．设R 是非空集合A 上的等价关系，A x ∈，[]R x 为x 关于R 的等价类，则下面命题为真的是（）。

Ⅰ 存在A x ∈，并且[]Φ=R xⅡ 对任意的A y x ∈,，若R y x ∉,，则[][]Φ=⋂R R y xⅢ[]{}A A x x R =∈（A ）只有Ⅰ （B ）Ⅰ和Ⅲ （C ）只有Ⅱ （D ）Ⅱ和Ⅲ 16．设R ，S 是非空集合A 上的等价关系，则下面是A 上的等价关系的是（ ）。

（A ）（A ×A ）－R （B ）S ∪R （C ）S －R （D ）S ∩R 17．设集合E={0，1，2，3}，则下面集合与E 相等的是（ ）。

（A ）{}03 =-∈x R x （B ）{}9 2-=∈x R x（C ）{}65 2=++∈x xR x （D ）{}30 ≤≤∈x N x18．对100名技术人员的调查结果表明，有32人学过日语，20人学过法语，45人学过英语。

又其中有15人既学过日语又学过英语，7人既学过日语又学过法语，10人既学过法语又学过英语，30人没学过这3门语言中的任何一种。

则下面说法中正确的是（ ）。

（A ）3种语言都学过的人数为6。

（B ）只学过日语的人数为32。

（C ）至少学习以上3种语言中的2种语言的人数为22。

（D ）只学习日语和法语的人数为7。

19．设G 是一个连通的无基本回路的图，G 中包含：3个3度顶点，2个2度顶点，r 个1度顶点，且G 中不再包含其它顶点，则G 的顶点个数为（ ）。

（A ）6 （B ）9 （C ）15－r （D ）5+5 r 20．设G 是4阶群，则其子群的阶不能是下面的（ ）。

（A ）1 （B ）2 （C ）3 （D ）421．设命题P ，Q 的真值为T ，命题R ，S 的真值为F ，则下列哪个命题的真值为F （ ）。

（A ）（P ∧（Q ∧R ））∨┒（（P ∨Q ）∧（R ∨S ）） （B ）（┑（P ∧Q ）∨┐R ）∨（（（┐P ∧Q ）∨┐R ）∧S ）（C ）（P ↔R ）∧（┐Q ∧S ） （D ）（P ↔Q ）∨（R ↔S ）22．设P ：天下雨，Q ：我将去街上，R ：我有时间，则下列命题中哪个符号化不正确（ ）。

（A ）P ∧R →Q ：如果天不下雨和我有时间，那么我将去街上。

（B ）┓P ：天不下雨。

（C ）P →┓Q ：天下雨，那么我不去街上。

（D ）P ∧Q ：天下雨，我也将去街上。

23．设N 是正整数集合，对下列哪一个运算*，〈N ，*〉不能构成半群（ ）。

（A ）a*b=max （a ，b ） （B ）a*b=min （a ，b ）（C ）a*b=a （D ）a*b=a/b ，此处“/”是数的除法运算。

24．设I ，Q ，R ，C 分别是整数集合、有理数集合、实数集合、复数集合，+，·是普通的数的加法和乘法运算，则下列代数系统不能构成域的是（ ）。

（A ）〈I ，+，·〉 （B ）〈Q ，+，·〉 （C ）〈R ，+，·〉 （D ）〈C ，+，·〉 二．简答题（每小题7分，共42分）。

1．设有5个城市521,,,v v v ，任意两城市之间铁路造价如下（以百万元计算）：()4,21=v v w ，()10,51=v v w ，()7,31=v v w ，()16,41=v v w ，()13,32=v v w ，()8,42=v v w ，()17,52=v v w ，()3,43=v v w ，()10,53=v v w ，()12,54=v v w ，试求出连接5个城市的且造价最低的铁路网。

2．试构造一棵带权为1，2，3，4，5，6，7，8，9，10的最优二叉树。

3．试求公式()()q p q p ⌝↔→⌝∨⌝的主析取范式和主合取范式。

4．试用推理规则证明：()()N M G H J G H N M J ∨⇒∨→∨∨→ , , 。

5．设集合A={1，2，3，4，5，6}，R 是集合A 上的二元关系，其中R={〈x ，y 〉∣A y x ∈,且x 整除y}，试求R 的关系矩阵R M ，关系图以及R 的三个关系闭包，即r （R ），s （R ），t （R ）。

6．设DS n ,是格，其中nS 是n 的所有正因数的集合，D 是nS 上的整除关系，当n =75时，试求每个元素的余元素。

三．证明题（10分）：设〈G ，*〉是一个独异点，并且对于G 中的每一个元素x ，都有x*x=e ，其中e 是幺元，证明〈G ，*〉是一个阿贝尔群。

参考答案模拟试题1答案一. 单项选择题（每小题2分，共48分）。

1. C2. A3. C4. C5. C6. B7. D8. D9. D 10. C 11. C 12. B 13. A 14. D 15. D 16. D 17. D 18. C 19. C 20. C 21. C 22. A 23. D 24. A二．简答题（每小题7分，共42分）。

1.2.3.4.①②③①②④⑤③④5. 关系矩阵：关系图：6. 1与75互为余元素，3与25互为余元素，5与15不存在余元素。

三．证明题（10分）证明：由可知，中的每一个元素都以自身为逆元，所以是群。

对任意的，有所以运算*是可交换的，因此，是一个阿贝尔群。

离散数学模拟试题2一. 单项选择题。

(每题2分，共24分)1.一个格的哈斯图如下，下述子集中为子格的是（）。

2.如下的哈斯图所示偏序集为格的是（）。

3.设A是有界格，若它也是有余格，只要（）。

(A) 每一个元素都有一个余元(B) 每一个元素至少有两个余元(C) 每一个元素都无余元(D) 每一个元素仅有一个余元4．设X={1, 2, 3, 4}，Y={a, b, c, d}，则下列关系中为函数的是（）。

(A) {<1, a>，<1, b>，<2, c>}(B) {<1, a>，<2, d>，<3, c>，<4, b>}(C) {<1, a>，<2, a>，<3, b>}(D) {<1, a>，<1, b>，<2, b>，<4, b>}5．下列语句中为命题的是（）。

(A) 今天是阴天。

(B) 你身体好吗？(C) 我真快乐。

(D) 请不要走。

6．设N为自然数集合，+、－、×分别为普通的加法、减法和乘法。

〈N，*〉在下面四种情况下不构成代数系统的为（）。

（A）x*y=x+y－2×x×y (B)x*y=x+y(C)x*y=x×y (D)x*y=│x│+│y│7．设集合，上的两个二元运算分别为模n加法运算和模n法运算，则代数系统为（）。

（A）域（B）格（C）环，但不一定是域（D）布尔代数8．设P：天下雨，Q：我将去街上，R：我有时间，则下列命题中哪个符号化不正确（）。

（A）P∧R→Q：如果天不下雨和我有时间，那么我将去街上。

(B）┓P：天不下雨。