《月全国自考离散数学试题试卷真题及答案》由会员分享，可在线阅读，更多相关《月全国自考离散数学试题试卷真题及答案（5页珍藏版）》请在金锄头文库上搜索。
1、1全国 2002 年 4 月高等教育自学考试 离散数学试题一、单项选择题(本大题共 15 小题，每小题 1 分，共 15 分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图 G，如果它的所有结点的度数都是偶数，那么它具有一条( B ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设 G 是连通简单平面图，G 中有 11 个顶点 5 个面，则 G 中的边是( D ) A.10 B.12 C.16 D.14 3.在布尔代数 L 中，表达式(ab)(abc)(bc)的等价式是( A )A.b(ac) B.(
2、ab)(ab) C.(ab)(abc)(bc) D.(bc)(ac) 4.设 i 是虚数，是复数乘法运算，则 G=是群，下列是 G 的子群是( A )A. B.-1, C.i, D.-i, 5.设 Z 为整数集，A 为集合，A 的幂集为 P(A),+、-、/为数的加、减、除运算，为集合的 交运算，下列系统中是代数系统的有( D )A.Z，+，/ B.Z，/ C.Z，-，/ D.P(A)， 6.下列各代数系统中不含有零元素的是( D )A.Q，*Q 是全体有理数集，*是数的乘法运算 B.Mn(R),*,Mn(R)是全体 n 阶实矩阵集合，*是矩阵乘法运算 C.Z， ，Z 是整数集， 定义为 x
3、xy=xy,x,yZooo D.Z，+ ，Z 是整数集，+是数的加法运算 7.设 A=1,2,3，A 上二元关系 R 的关系图如下： R 具有的性质是( D ) A.自反性 B.对称性 C.传递性 D.反自反性8.设 A=a,b,c，A 上二元关系 R=a,a ， b,b,a,c，则关系 R 的对称闭包 S(R)是( C )A.RIA B.R C.Rc,a D.RIA 9.设 X=a,b,c,Ix 是 X 上恒等关系，要使 Ixa,b ， b,c ， c,a ， b,aR 为 X 上的 等价关系，R 应取( D ) A.c,a ， a,c B.c,b ， b,a C.c,a ， b,a D.a
4、,c ， c,b 10.下列式子正确的是( B )A. B. C. D.11.设解释 R 如下：论域 D 为实数集，a=0,f(x,y)=x-y,A(x,y):x是群。设 n 是正 整数，求(a-1ba)na-nbnan 答：当 n 是偶数时，xP(A),xn=当 n 是奇数时，xP(A),xn=x于是：当 n 是偶数，(a-1b a)na-nbnan=(a-1)nbnan= 当 n 是奇数时，(a-1b a)na-nbnan=a-1b a(a-1)nbnan=a-1b aa-1b a= 28.(6 分)设 A=1,2,3,4,5,A 上偏序关系R=1，2 ， 3，2 ， 4，1 ， 4，2
5、， 4，3 ， 3，5 ， 4，5IA; (1)作出偏序关系 R 的哈斯图 (2)令 B=1,2,3,5，求 B 的最大，最小元，极大、极小元，上界，下确界，下界，下确界。 答：(1)偏序关系 R 的哈斯图为(2)B 的最大元：无，最小元：无；极大元：2，5，极小元：1，3下界：4， 下确界 4；上界：无，上确界：无 29.(6 分)求(PQ)(PQ)的主合取范式并给出所有使命题为真的赋值。 答：原式(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQPQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)P(QQ)P(QQ)(PQ)(PQ)命题为真的赋值是 P=1,Q=0 和
6、 P=1,Q=1 30.(5 分)设带权无向图 G 如下，求 G 的最小生成树 T 及 T 的权总和，要求写出解的过程。4答：令 e1=(v1,v3), e2=(v4,v6)e3=(v2,v5), e4=(v3,v6)e5=(v2,v3), e6=(v1,v2)e7=(v1,v4), e8=(v4,v3)e9=(v3,v5), e10=(v5,v6)令 ai为 ei上的权，则a1,其中 V=v1,v2,，V20是以 20 个人为顶点的集合，E 中的边是若任两个人 vi和 vj相互认识则在 vi与 vj之间连一条边。6ViV,d(vi)是与 vi相互认识的人的数目，由题意知vi,vjV 有 d(vi)+d(vj)20,于是 G 中存在汉密尔顿回路。设 C=Vi1Vi2Vi20Vi1是 G 中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合 要求。
