离散数学试题与答案试卷一

成树。

5a5f1b27h6648e6d3c

四、证明题（共20分）

1.前提：??x(F(x)?H(x)),?x(G(x)?H(x)) 结论:?x(G(x)??F(x))

2.已知?Mn(Z),??(即整数集上2阶方阵构成的集合关于矩阵的加法)构成

????a0????a?Z群,H=??? ?0a??????(1) ?Mn(Z),??的单位元是什么? ??(2)证明: H是?Mn(Z),??的子群. 3.叙述并证明关于连通平面图的欧拉公式。

《离散数学》试题七

一、选择题（每小题 2 分，共 20 分）

1、使命题公式p→(p∧q)为假的赋值是 ( )

A.10 B.01 C. 00 D.11 2、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）

A. p∧┐q B．p∨┐q C.p∧q D．p→┐q

3、设B不含有x，下列一阶逻辑等值式不正确的是 ( ) ．．．

A.?x(A(x)?B)??xA(x)?B B.?x(A(x)?B)??xA(x)?B C. ?x(A(x)?B(x))??xA(x)??xB(x)

?1?2??的逆元是什么? ??34? D. ?x(A(x)?B(x))??xA(x)??xB(x) 4、 设X，Y，Z是集合，下列结论不正确的是（ ） ．．．

A．若X?Y,则X?Y=X B．(X-Y)-Z=X-(Y∩Z) C．X?X?? D．X?Y?X?(~Y)

5、设R是集合A上的二元关系，IA是上的恒等关系，IA?R下面四个命题为真的是 ( )

A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的 6、设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( ) A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射 7、集合A={1，2，3，4}，则对 A 的元素进行分类正确的是（ ）

A. {?,{1,2},{3,4}} B. {{1,2,3},{3,4}} C. {{1},{3,4}} D. {{1,2,3,4}} 8、无向完全图Kn有 ( )条边

A. n B. n C. n(n-1) D. n(n-1)/2 9、 设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）

A．2 B．3 C．4 D．5

10、一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则 根结点的右子树有（ ）结点。

A．1 B．2 C．3 D．4 二、填空题（每题2分，共10分）

1、量词否定等值式??xA(x)? ___________________。

2、设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的对称闭包是 。

3、A={1，2}，?P(A),??是群，?是集合的对称差运算。该群的单位元是 ，{1}的逆元是 。

4、图G是平面图的充分必要条件是没有收缩到___或 的子图。

5、无向图G=,V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,c)},则它的邻接矩阵为 ，该图的补图有 条边。 三、计算题（每题8分，共 48分）

1、求公式(p?q)?r的主和取范式(化成M1?M2?M3的形式)。

2

2、R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}, (1) 求 R1 (2) 求R2?R1 (3)R1是函数吗？ 3、(1)叙述等价关系的定义；

(2)设A={1，2，3，4},R={<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2>}是A上的等价关系吗？如果是,给出R确定的对A的分类；如果不是,请说明理由。

4、已知?M2(R),?,??(即实数集上2阶方阵构成的集合关于矩阵的加法和乘法)构成的环。 (1)?M2(R),?,??的零位元是什么?单位元是什么? (2)说明 ?M2(R),?,??不是无零因子环； (3)举例说明?不满足消去律。 5、求A到其余顶点的最短路径。

-1

B8A1C24226D5F1E

6、求下PERT图中各顶点的最早完成时间TE(vi)和最迟完成时间TL(vi)，并求出关键路径。

c9a3b124d28g4j3f

1h6221e得分 阅卷人 四、证明题（ 22分）

1、前提： ?x(F(x)?G(x)?H(x)),?x(F(x)?R(x))

结论: ?x(F(x)?R(x)?G(x))

2、设是可交换群，H={a∈G｜?k∈N(正整数集)，使a=e}，

k

证明H是G的子群。

3、用数学归纳法证明，含有n片树叶的最优二叉树有n-1个分支点.

《离散数学》试卷 八

得分 阅卷人 题号 答案 1 2 3 4 5 6 7 8 9 10 一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）

1、从集合分类的角度看,命题公式可分为( )

A.永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 2、设B不含有x，?x(A(x)?B)等值于 ( )

A.?xA(x)?B B.?x(A(x)?B) C.?xA(x)?B D.?x(A(x)?B) 3、设S,T,M是集合，下列结论正确的是（ ）

A．如果S∪T=S∪M，则T=M B．如果S-T=Φ，则S=T C．S?S?S D．S?T?S?(~T) 4、设R是集合A上的偏序关系，则R不一定是( )

A.自反的 B. 对称的 C. 反对称的 D. 传递的 5 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。 A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy D. f4(x,y)=max{x,y} 6、设是一个格，则它不满足( )

A.交换律 B. 结合律 C. 吸收律 D. 消去律 7、设A={1,2},则群?P(A),??的单位元和零元是( )

A. ?与A B. A 与? C. {1}与? D. {1}与A 8、下列编码是前缀码的是( ).

A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000} 9、下图中既是欧拉图又是哈密顿图的是（ ）

A． K9 B．K10 C．K2,3 D．K3,3 10、下图所示的二叉树中序遍历的结果是（ ）