09软件外包 离散数学 模拟试题

09软件外包 离散数学 模拟试题

共 3 页，第 1 页

一、选择题（10题×2分=20分）

1. 下列哪个联结词运算不可交换？（）

A.∧

B.→

C.∨

D. ?

2. 谓词公式(()())()x P x yR y Q x ?∨?→中变元x 是（） A.自由变量 B.约束变量 C.既非自由变量也非约束变量 D.既是自由变量也是约束变量

3. 设{,{}}A a a =，下列选项错误的是（）

A.

{}()a P A ∈ B. {}()a P A ?

C.{{}}()a P A ?

D. {{}}()a P A ∈

4. 设{,,}A a b c =上的关系如下，有传递性的是（） A. 1{,,,,,,,}R a c c a a b b a =<><><><>

B.

2{,,,}R a c c a =<><>

C. 3{,,,,,,,}R a b c c b a b c =<><><><>

D. 4{,}R a a =<>

5. 设{,,}A a b c =，{1,2}B =，令:f A B →，则不同的函数的个数为（）

A. 2+3

B. 3

2

C. 23?

D. 2

3

6. 集合{1,2,3,...,10}A =，下面定义的哪种运算关于A 不封闭（） A. *{,},x y LCM x y =即x,y 的最小公倍数 B. *{,},x y GCD x y =即x,y 的最大公约数 C. *max{,}x y x y = D. *min{,}x y x y =

7. Q 是有理集，,*Q <>(其中*是普通乘法)不能构成（）。

A.群

B.独异点

C.半群 D 交换半群 8. 设G 为有n 个结点的简单图，则有（） A. G n ?> B.G n ?≤ C. G n ?<

D.G n ?≥ 9.有向图,D V

E

=<>，其中{,,

V a b c d e f

=，{,,,,,,,,,}E a b b c a d d e f e =<><><><><>，则D 是（）

A.强连通图

B.单向连通图

C.弱连通图

D.不连通图 10. 欧拉回路是（）

A.路径

B.简单回路

C.既是初级回路又是简单回路

D.既非初级回路也非简单回路 二、填空题（10题×2分=20分）

1. 令p ：小丽拿一个苹果，q ：小丽拿一个梨，命题“小丽只能拿一个苹果或一个梨。”的符号化形式为_______。

2. 令()F x ：x 是人，()G x ：x 喜欢吃馒头，()H x ：x 喜欢吃米饭，命题“虽然有人不喜欢吃馒

头，但也不是所有的人都喜欢吃米饭。”的符号化形式为_______。 3. 若含n 个命题变项的公式

A 是重言式，则A 的主合取范式为________。

4. 集合{,{}}??的幂集为________。

5. 集合{1,2,4,6}A =上的关系用列元素法为________。{,|,}R x y x y A y =<>∈∧为素数

6. 在群,Z <

+>中有53-=________。

7.

G a =<>为24阶循环群，则G 的所有生成元为________。

8. 简单无向图中，圈的长度至少为________。 9. 完全图(1)n K n ≥的点连通度为________。

10. 在完全图2(2)k K k

≥上至少加________条边，才能使所得图为欧拉图。

三、判断题（20题×1分=20分）

1. 公式A 是矛盾式当且仅当A 的主析取范式不含任何极小项。

2. 空简单析取式是不可满足的。

3. 设公式(),()F x G x 含自由出现的个体变项

x

，则下列等值式成立：

(()())()(x F x G x x F x x G x ?∨??∨? 。

4. ,A B 为集合，则A B A B -=???。

5. 一阶逻辑中的任何公式都存在等值并且唯一的前束范式。

6. 有穷集A 上的关系R 的幂序列0

12,,,...R R R 是一个周期性变化的序列。

7. 小于或等于关系是相应集合上的传递关系。

8. 设R 是非空集合

A 上的关系，则R 是对称的当且仅当()s R R =。

9. 等价关系是具有自反性、反对称性和传递性的关系。 10. 函数

:,()ln ,f Z R f x x Z ++→=（为正整数集）

是双射函数 11. 群G 中的运算一定满足交换律、结合律和消去律。 12. 设H 是群G 的子群，则,a G a Ha ?∈∈有。

13. H 是群G 的子群，则||||[:]G H G H =

。 14. 任何n 元置换都可以表示成不交的轮换之积。

15. 集合{21|}A z z Z =+∈关于实数加法和乘法构成环。

16. 非连通图的点连通度为0。 17. 设有向图D 是单向连通图，但不是强连通图。在D 中至少加1条边所得图'

D 就能成为强连通图。

18. 彼得松图是哈密顿图。

19. 无向图G 有生成树当且仅当G 是连通图。 20.

(2)n n ≥阶有向完全图是欧拉图。

四、证明题（2题×8分=16分）

1. 在自然推理系统F 中，构造下列推理的证明。

每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合） 2. 设H 是群G 的子群，G x ∈，令}|{11

H h xhx xHx ∈=--，证明1-xHx 是G 的子群。

五、解答题（4题×6分=24分）

09软件外包 离散数学 模拟试题

共 3 页，第 2 页

1.{,,,,,,,,,,,,,,,}A R a b a c a d a e b e c e d e e f I =<><><><><><><><>?为集合{,,,,,}A a b c d e f =上的偏序

关系。

(1)请画出此偏序集的哈斯图，并找出

A 的极大元、极小元、最大元和最小元。

(2) 集合{,,}B b c e =，求B 的上界、下界、最小上界和最大下界。

2. 设某城市的街道布置如下图所示。每条边代表一个特定街道的一段街区，每个结点代表街区间的交点。扫雪车车库位于结点d 。证明存在一条路线使得扫雪车清扫每个街区恰好一次且清扫完最后一个街区正好返回车库。并且为这个扫雪车找出完成该任务的路线。

3. 有向图D 如下图所示。 (1) D 中有几种非同构的圈？

(2) D 是哪类连通图?

(3) D 中1v 到 4v 长度为1,2,3,4的通路各多少条？其中几条是非初级的简单通路？

(4)

D 中1v 到1v 长度为1,2,3,4的回路各多少条？ (5) D 中长度为4的通路（不含回路）有多少条？ (6) D 中长度为4

的回路有多少条？

(7) D 中长度小于等于4的通路有多少条？其中有几条是回路？ (8) 写出

D 的可达矩阵。

4.用避圈法求下列带权图的最小生成树。

09软件外包 离散数学 模拟试题

共 3 页，第 3 页

2009级软件外包专业2010-2011学年第二学期

《离散数学》模拟试题答案及评分标准

一、选择题（10题×2分=20分）

1-5 BDBDB 6-10 AACCB 二、填空题（10题×2分=20分）

1.

()()p q p q ∧?∨?∧ 2. (()())(()())x F x G x x F x H x ?∧?∧??→ 3. 1 4. {,{},{{}},{,{}}}?????

5. {1,2,2,2,4,2,6,2}R =<><><><>

6. -15

7.

2478111314,,,,,,,a a a a a a a a 8. 3 9. 1n - 10. k

三、判断题（20题×1分=20分）

1-5 √ √ × √ × 6-10 √ √ √ × × 11-15 × √ √ √ × 16-20 √ √ × √ √ 四、证明题（2题×8分=16分） 1. 先将简单命题符号化：

()F x :x 是科研工作者 ()G x : x 刻苦钻研

()H x : x 聪明 …… 此处隐藏：2847字，全部文档内容请下载后查看。喜欢就下载吧 ……