离散数学AB卷3套期末考试卷带答案 模拟试卷 测试卷 期末考试题

1、一、单选题（20小题，每小题 2分，共40 分）得分设 A，2，3上的关系如下，有传递性的有（A，C，D下列语句是命题的是（） y 0A明年中秋节的晚上是晴天xC 请保持安静我正在说谎下列哪个命题是假命题（A如果 ，则太阳从东方升起；如果 2+2=4，则太阳从西方升起；C如果 2+24，则太阳从东方升起；D如果 2+24，则太阳从西方升起设R 是正实数集，是实数集，：R R,xR ,( ) ln ，则是（、xxA是入射不是满射是满射不是入射是双射C既非入射也非满射下列等价式不成立的是（ ACyF(x,y) yxF x y( , )xyF(x,y) yxF(x,y)xyF(x,y) yxF x

2、y( , ) ( ( ) x F x G xF x G)( )n 阶完全图的边数为（An(n-1)/2； Bn-1；设 G=ECn+1；2n(n-1)、A； B；C； 设 为整数集， ：、 Z f， ( ) (mod3) ，则 是（f i iZ ZfA是入射不是满射是满射不是入射1 A第 1 页 共 20 页是一个复合映射。下列哪个命题是假命题（若g f f C若g f f 和g 若 f 和gg f ）S。设 1，则有（、A1,2 ；B1,2 ；C1 ；2ABCD(PQ) (PQ)A(P Q) (P Q)(Q P)设 , , ，下列二元关系 为 到 的函数的是(B a b A B)RA , 2

3、, , 3, , 2, R a bRaaaC , , 2, , 3, , , 2, , 3, RabaaRabab设 , 为无向图，| |，| |=23，则 G一定是（V EVEB树；C简单图；多重图令 ( ): 是金属， ( )： 是液体， ( , )： 可以溶解在 中，则命题“任何金属可xx16、 F xG yyH x yyA ( ( )x F x y G y H x y( ( )( , ) ( ) ( ) ( ( ) ( , )x x F x G y H x yC ( ( )x F x y G y H x y( ( )( , ) ( ( ) ( , )x F x y G y H x y(

4、 ( )第 2 页 共 20 页下面四组数能构成无向图的度数列的有（A2,3,4,5,6,7； B1,2,2,3,4； C2,1,1,1,2；无向图 是欧拉图，当且仅当（ 的所有结点的度数为偶数；3,3,5,6,0、GA 连通且所有结点的度数为偶数；GGC 连通且所有结点的度数为奇数； 的所有结点的度数为奇数GG下列关系中能构成函数的是（ ,y |(,yR)(y x )Ax,y|(x,yN)(xy10)； 2； ,y |(,yR)(y x)2 x y x y I x y , |( , )( C；下列哪个谓词公式与 ( , )等价？（x yP x y、AxyP(x,y)xyP(x,y)CxyP(

5、x,y)yP(x,y)二、填空题（20小题，每空 1分，共20分）得分在偏序集 , 中， ，是 上的整除关系，则 的极大元是、AAAA设 是集合 上的具有自反性、对称性、反对称性和传递性的二元关系，则 =、 RAR命题公式 的逆反式是P Q。、设 , 则 A的幂集是、 A，设 ( )表示“x ( )表示“x 、 G x F x不一定是金子”符号化为写出下表中所定义的命题联结词。PQ001101010001设、 H(x)表示“ x表示“ xN(x)号化为1 A第 3 页 共 20 页在偏序集 , 中，其中 =2,3,6,12,24,36，是 中的整除关系，则集合 =2,3,6的8、AAAB极大元

6、是在下图所给的偏序集 , 中，集合 , 的上确界是b c、A在下图所给的偏序集 , 中，集合 , 的下确界是b cA一棵树 有 2 个度为 2 的结点，1 个度为 3 的结点，4 个度为 4 1 个度为 5 的结TT完全图 K5 的边数是fRR设 、 P Q我努力学习”符号化为。设 是图G V,E 的邻接矩阵，A (a )，则图G V,E 中由 到 长度为 的路径、Akkvvkijij的条数为一棵有向树 T，若T 恰有一个结点的入度为 0，其余所有结点的入度都为1，则称T 为根第 4 页 共 20 页=三、简答题（4小题，每小题6分，共24分）得分vv14有几条？1 A第 5 页 共 20 页

7、对下图所给的偏序集 , ，求下表所列集合的上确界，下确界，并将结果填入表中。、A下确界A今有煤气站 ，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示要求设计一个最经济的煤气管道路线，并求所需的总费用IEA1S54GCD23K342JB62F2H第 6 页 共 20 页四、证明题（2小题，每小题8分，共16分）得分x y x y设函数 : ( , ), 证明 是双射的。f，、f R R R R， f x y22符号化下列命题并推证其结论所有有理数是实数，某些有理数是整数，因此某些实数是整数（设 ( )： 是有理数， ( )：x

8、Q xR x是实数， ( )： xxZ x第 7 页 共 20 页一、单选题（20小题，每小题 2分，共40 分）1、D11、B12、B13、A14、D15、C16、C17、B18、A19、B20、D2、A3、B4、D5、B6、A7、C8、C9、C10、A二、填空题（20小题，每空 1分，共20分）1、4，5，610、2、I11、dA12、3、 QP14、104、, , 5、( )( ( ) ( )( )( ( ) ( )x G x F x x F x G x15、既是单射又是满射16、反自反性、反对称性和传递性或( )( ( ) ( )( )( ( ) ( )x G x F x y F y

9、G y17、 P Q6、7、( )( ( ) ( )( )( ( ) ( )x H x N x x N x H x18、a( )kij19、出度为 0 的结点或( )( ( ) ( )( )( ( ) ( )x H x N x y N y H y20、, , 8、69、a三、简答题（4小题，每小题6分，共24分）1、解：1）邻接矩阵为：第 8 页 共 20 页1 0 1 13 2 3 32 1 2 2,（2 分）,A A2340 0 0 10 0 0 114141 1 1 P0 0 0 2、3、答：dcaA第 9 页 共 20 页因此如图铺设煤气管道所需费用最小，最小费用为：2222222+3

10、25WT)（2 分）四、证明题（2小题，每小题8分，共16分）1、证明：假设存在, , , ，使得 ( , ) ( , )，则 m n u v f m n f u vmn uv mn uv且，那么 且 ，由此得m u n v m n u v f，即 是入射。,2222（3 分） 任 取 , R ， 均 有 , , u v u v R R， 使 得u v Rx yuv)uv) uv)uv)f( x,y ),u,v，从而 3 分）f22综合知 是双射。f（2 分）2、该命题符号化为： ( ( ) ( ) ( ( ) ( ) ( ( ) ( )（2 分）x Q xR xx Q x Z xx R x

11、Z x证: (1) ( ( ) ( )x Q x Z xP(6)( )Z aT(2) I（1 分）(2) ( )( )ES (1) （1 分） (7)(8)( )R aT(4),(5) I （1 分）T(6),(7) I （1 分）Q a Z a(3)(4)(5)P( ) Z(a)R ax(Q(x) R(x)Q(a) R a( )US (3) （1 分）(9)x(R(x)Z(x) EG(8) （1 分）( )Q aT(2) I一、单选题（20小题，每小题 2分，共40 分）得分下列等价式不成立的是（ ACyF(x,y) yxF x y( , )xyF(x,y) yxF(x,y)xyF(x,y)

12、 yxF x y( , ) ( ( ) x F x G xF x G)( )令 ( ): 是金属， ( )： 是液体， ( , )： 可以溶解在 任何金属可以xx F xG yyH x yy1 B第 10 页 共 20 页溶解在某种液体中可符号化为（ A ( ( )x F x y G y H x y( ( )( , ) ( ) ( ) ( ( ) ( , )x x F x G y H x yC ( ( )x F x y G y H x y( ( )( , ) ( ( ) ( , )x F x y G y H x y( ( )设 , , ，下列二元关系 为 到 的函数的是(B a b A B)、

13、 ARA , 2, , 3, , 2, R a bRaaaC , , 2, , 3, , , 2, , 3, R a b a bRabaa设 G=E、A； B；C； 无向图 是欧拉图，当且仅当（G、A 连通且所有结点的度数为偶数； 的所有结点的度数为偶数；GGC 连通且所有结点的度数为奇数； 的所有结点的度数为奇数GG设 1，则有（）S。、A1,2 ；B1,2 ；C1 ；2下列关系中能构成函数的是（ ,y |(,yR)(y x )Ax,y|(x,yN)(xy10)； ；2 ,y |(,yR)(y x)x,y|(x,yI)(x y2C；下面四组数能构成无向图的度数列的有（A2,3,4,5,6,7

14、； B1,2,2,3,4； C2,1,1,1,2；3,3,5,6,0设R 是正实数集，是实数集，：R R,xR ,( ) ln ，则是（、xxA是入射不是满射是满射不是入射是双射C既非入射也非满射下列哪个谓词公式与 ( , )等价？（x yP x y、A( , ) xyP x y( , ) CxyP x yxyP(x,y)yP(x,y)设 为整数集， ：、 Z f， ( ) (mod3) ，则 是（f i iZ ZfA是入射不是满射是满射不是入射C既非入射也非满射1 B第 11 页 共 20 页我正在说谎ABCDC如果 2+24，则太阳从东方升起；D如果 2+24，则太阳从西方升起An(n-1

15、)/2；Bn-1；2n(n-1)(PQ) (PQ)A(P Q) (P Q)(Q P)设、 g f若g f f C若g f f 和g ,为无向图，| |，| |=23，则 G一定是（VEA完全图；B树；C简单图；多重图二、填空题（20小题，每空 1分，共20分）得分设 1、 PQ设表示“ x在下图所给的偏序集 , 中，集合 , 的上确界是b c、A、 RARA则AP(P() A=设 是图G V,E 的邻接矩阵， A (a )，则图G V,E 中由v 到 长度为 的路径6、Akkvkijij的条数为一棵树 有 2 个度为 2 的结点，1 个度为 3 的结点，4 个度为 4 的结点，1 个度为 5

16、的结点，、TTPQ000111完全图 K5 的边数是、在偏序集 , 中， ，是 上的整除关系，则 的极大元是、AAAA设 ( )表示“x ( )表示“x 、 G x F x不一定是金子”符号化为在下图所给的偏序集 , 中，集合 , 的下确界是b c、A命题公式 的逆反式是P Q设 , 则 A 的幂集是，、 XRRf=2,3,6,12,24,36，是 中的整除关系，则集合 =2,3,6的AB极大元是一棵有向树 T，若T 恰有一个结点的入度为 0，其余所有结点的入度都为1，则称T 为根树。其中 称为树叶。三、简答题（4小题，每小题6分，共24分）得分1）写出邻接矩阵 A；vv14有几条？今有煤气站

17、 ，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示要求设计一个最经济的煤气管道路线，并求所需的总费用IEA1S54G23K342JB62F2H以给定权 2， 4， ， 8， 13， 15， 18， 25 构造一棵最优二叉树对下图所给的偏序集 , ，求下表所列集合的上确界，下确界，并将结果填入表中。、A下确界a,b,第 16 页 共 20 页c,d,A四、证明题（2小题，每小题8分，共16分）得分x y x y设函数 : ( , )f R R R R， f x y, 、f22符号化下列命题并推证其结论所有有理数是实数，某些有理

18、数是整数，因此某些实数是整数（设 ( )： 是有理数， ( )：xQ xR x是实数， ( )： xxZ x第 17 页 共 20 页一、单选题（20小题，每小题 2分，共40 分）1、B2、C3、A4、C11、C12、A13、D14、B15、B16、A5、A6、A7、B17、B18、C19、C20、D8、B9、D10、D二、填空题（20小题，每空 1分，共20分）11、12、4，5，613、( )( ( ) ( )( )( ( ) ( )1、 P Q2、( )( ( ) ( )( )( ( ) ( )x H x N x x N x H xx G x F x x F x G x或( )( ( ) ( )( )( ( ) ( )x H xN xy N yH y或( )( ( ) ( )( )( ( ) ( )x G x F x y F y G y3、a14、d15、 P4、IAQ5、, , 16、, , 6、a(k)17、反自反性、反对称性和传递性18、既是单射又是满射19、6ij7、8、9、1020、出度为 0 的结点三、简答题（4小题，每小题6分，共24分）1、解：邻接矩阵为：第 18 页 共 20 页1 0 1 11 1 1 1