haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中数学初中数学

离散期末练习试卷

发布时间:2014-02-04 17:08:13  

上海应用技术学院2008—2009学年第一学期

《 离散数学 》期末试卷(A)

课程代码: B204216 学分: 4 考试时间: 100 分钟 课程序号: 3404 班级: 学号: 姓名: 我已阅读了有关的考试规定和纪律要求,愿意在考试中遵守《考场规则》,如有违反将愿接受相应的处理。

试卷共 6 页,请先查看试卷有无缺页,然后答题。

一.选择题(10 x 2 =20)

1. 下列命题中命题( )为假。

A. “如果2是偶数,则一个公式的主析取范式唯一。”

B. “如果2是偶数,则一个公式的析取范式唯一。”

C. “如果2是奇数,则一个公式的析取范式唯一。”

D. “如果2是奇数,则一个公式的主析取范式唯一。”

2. 命题公式(p1?p2)?p3的成真赋值为( )。

A. 001 B. 110

C. 100 D. 010

3. 集合A={x| x是单词“command”中的字母},B={x,a,b,c,d},则|A∩B|=( )。

A. 7 B. 8 C. 4 D. 3

4. .若个体域为{0,1,2,3},下列公式中值为真的是( )。

A.?x?y(x+y=0) B.?y?x(x+y=0)

C.?x?y(x+y=0) D. ?x?y(x+y=0)

5. 设集合 S={{0,1},{1,2,3},{2,3,4,5}},集合( )是S中所有元素的交集。

A. {0,1,2,3,4,5} B. {1}

C. Ф D. {0,1}

第 1 页

6. 若A?B且B?C则 ( )。

A. A∩C =B B. A∪B= A

C. A∩C =A D. A∪C =B

7. 在自然数集合N上,下列运算中( )满足结合律。

A. a * b = | a-b | B. a * b = a+2b

C. a * b = max( a,b ) D. a * b = a

8. 以下关系中( )不具有传递性。

A.S= { <1, 2>, <2, 1>, <1, 1>,<8, 5> }

B. S={ <1, 1>,<2,2>,<1, 2>, <2, 1> }

C. S={<2, 2>,<8, 5>}

D. S={<1, 1>, <2, 1>}

9. 以下命题中( )是假命题。

A.“群满足结合律”

B.“群中只有一个幺元”

C.“群中无零元”

D.“群满足交换律”

10设无向图中有6条边,有一个3度顶点和一个5度顶点,其余顶点度为2,则该图的顶点数是( )。

A.3

C.5

二.填空题(2 x 10 = 20)

1. 设A={1,2,3,4},R?A×A,R={<1,2>,<3,4>,<2,2>},则R的自反闭包r(R)=_____ _____,对称闭包t(R)=___ _______。

2. A={-1,0,1},则<A, × >独异点,它的幺元为-1的逆元为。

3. 设F(x)表示“x是奇数”,H(x)表示“x是偶数”,G(x) 表示“x是整数”,用谓词公式表示命题“所有整数要么是奇数要么是偶数。” 。

第 2 页 bB.4 D.6

4. 有向图中任意两点间均相互可达 ,此图为连通图。若任二顶点间至少从一个顶点到另一个顶点是可达的,则称此图为 连通图

5.设A={a,b},B={0,1},则A与B的笛卡尔积A╳。

6.设命题P:天下雨,Q:我进城,R:我有空。用自然语言写出下列命题。 (┐P→Q)∧(R→Q): 。

7.具有n个元素的集合A的子集个数是 。

三.设A={1,2,3,4},它的一个划分π={{1,3},{2},{4}}。

1.写出对应的等价关系R;(3)

2.画出R的关系图;(3)

3.写出A中元素关于R的等价类。(4)

第 3 页 10) (

四.写出命题公式( p →( p ∧ q )) ∨ r的真值表,并按真值表写出主析取范式和主合取范式。(10)

五.有带权图G如下(12)

1.写出图G的邻接矩阵(3)

2.求最小生成树和树权T(w)。(写出每一步生成过程)(7)

3.找出图中的“割点”(2)

18 d c

第 4 页

六.给定权 1,4, 6 , 7, 8,11,22,36,构造一棵最优二元树,并计算该二元树的权(写出构造的过程)。(10)

七.设有集合Z4 ={0,1,2,3},+4 为定义在Z4 上的模4加法(两数相加后除以

4的余数)(10)

1.构造< Z4 ,+4 >的运算表;(4)

2.证明< Z4 ,+4 >是一个群;(6)

第 5 页

八.构造推理证明(8)

前提:p∨q , p→﹁r , s→t , ﹁s→r,﹁t 结论:q

第 6 页

上海应用技术学院2008—2009学年第一学期 《离散数学 》期末考试(A)试卷标准答案

一. 选择题(20)

BADDC CCADB

二. 填空题(20)

1. {<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<3,4>} {<1,2>,<2,1>,<3,4>,<4,3>, <2,2>}

2. 1,-1

3. ?X(G(X)?(F(X)??H(X))?(?F(X)?H(X)))

4. 强, 单向

5. { <a,0>,<a,1>,<b,0>,<b,1>}

6. 若天不下雨并且我有空,那么我进城。

7. 2n

三.(10分)

(1)R={<1,1>,<3,3>,<1,3>,<3,1>,<2,2>,<4,4>}

(2)图略

(3)[1]=[3]={1,3} , [2]={2}, [4]={4}

四 (10分)

主析取范式 m0 ∨m1 ∨m2∨m3 ∨m5∨m6 ∨m7 主合取范式 M0

五.有带权图G如下(12分) 最小生成树如下:

第 7 页

a

f

w(t)=11+15+16+18+21=81

?0?1??1A(G)=??0

?0??0?11000?01000??10100?? 01011?00101??00110??

六.给定权 1,4, 6 , 7, 8,11,22,36,构造一棵最优二元树,并计算二

叉树的权(写出构造的过程)。(10分)

95

22

11

1 4 11 7 22 8

权=(1+4)*5+6*4+(7+8+11)*3+(36+22)*2 = 243

七.设有集合Z4 ={0,1,2,3},+4 为定义在Z4 上的模4加法(两数相加后除4

的余数)(10分) 证明略

八、(8分)证明略

第 8 页

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com