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

1、一、单选题（20小题，每小题2分，共40分）得分1设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（ ）个三角形。A100； B200； C300； D6002设，则有（ ）。A1,2 ； B1,2 ； C1 ； D23下列关系中能构成函数的是（ ）。A； B；C； D452张扑克牌分配给4个桥牌比赛者进行比赛，那么扑克牌集合A到桥牌比赛者集合B的函数是（ ）。A.入射 B.满射 C.双射 D.映射5下列符号串是合式公式的是（ ）A、 ；B、 ；C、 ；D、 。6关系R所具有的关系矩阵，则关系R所具有的性质是（ ）A自反的，对称的，可传递的 B自反的，反对称的，可传递的C自反的，对称

2、的 D都不是7下列等价式不成立的是（）A BC D8设，以下哪一个关系是从到的满射 ( )。ABC D 9下列各图不是欧拉图的是（）10设图G有5个结点，若各结点的度数分别为：3 ,4, 6, 2, 3, 则G有（ ）条边。A10；B20；C9；D1811下列句子是命题的是( ) A再过5000年，地球上就没水了 BC水开了吗? D我正在说谎12下列等价公式正确的是（ ）A； B；C； D13给定公式：($x) (A（x）®B），与之等价的公式是 （ ）A($x) A（x）®B B ("x) A（x）®B C ØB ®($x) A（x

3、） D ØB ®($x) Ø A（x）14下面哪个图是强连通的（ ）15下图中是哈密尔顿图的是（ ）。16命题公式 中极小项的个数为（ ）A0 B1C2 D3 17下列等价式不成立的是（ ）.A; BC D 18设，下列二元关系为到的函数的是( )A BC D 19下面哪一种图不一定是树（）A无圈的连通图；B有个结点条边的连通图；C每对结点间都有路的图；D连通但删去一条边就不连通的图20设为无向图，=7，=23，则G一定是（ ）。A完全图； B树； C简单图； D多重图二、填空题（20小题，每空1分，共20分）得分1设命题公式的真值表为00001111001100

4、110101010100101100则命题公式的主析取范式为 。 2设表示“是马”，表示“是动物”则命题“马是动物，动物不一定是马”符号化为 3设A为任一集合，则 4设是到的函数，如果，则称为 5设集合，上的关系，（） 6完全图K5 的连通分支数是 。7设图G=V，E，V,的邻接矩阵A(G) = ，则的出度为 。8对谓词公式（"x）P（x）Ú（$y）Q（y）®（"x）R（x）中约束变元应用变换规则所得到的前束范式是 9设的函数，且，则 。 10设表示“天下雨”， 表示“我骑自行车上班”，则命题“除非下雨，否则我骑自行车上班”符号化为 。11写出下表中所定

5、义的命题联结词 0 00 11 01 1 0 1 1 1 12命题公式（ØP ®Q）®（Ø QÚ P）的主析取范式为 。13设是集合上的二元关系，则= 。14命题公式的逆反式是 。15在偏序集中，其中=2,3,6,12,24,36，是中的整除关系，则集合=2,3,6的极大元是 16设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则的关系矩阵是 。17设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。18设R是实数集合， ，且，则 19在任何有向图中，= 。20在偏序集中，其中=1,2,3,4,6,8,12,14，是中

6、的整除关系，则集合=2,3,4,6的极小元是 三、简答题（4小题，每小题6分，共24分）得分1以给定权2， 4， 5， 8， 13， 15， 18， 25构造一棵最优二叉树2今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示要求设计一个最经济的煤气管道路线，并求所需的总费用ABCDEFGHIJKS2222223.554526345313.对有向图求解下列问题： 1）写出邻接矩阵； 2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。 v1v4v2v34设 =1,2,3,4,5,6，集合上的关系=1,3,1,5,

7、2,5,4,4,4,5,5,4,6,3,6,6。（1）画出的关系图，并求它的关系矩阵；（2）求及 。四、证明题（2小题，每小题8分，共16分）得分1设为 ，证明：是双射。2符号化下列命题并推证其结论所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数）一、单选题（20小题，每小题2分，共40分）12345678910BABBCBBBDC11121314151617181920ADBABDBACD二、填空题（20小题，每空1分，共20分）12或34满射5，或R61718（$x）（" y）（"z）（P（x）ÚQ（y）®R（

8、z）9101112或（PÙQ）Ú（PÙØ Q）Ú（ØPÙØQ）13；1415616或单位矩阵1781819E202,3 三、简答题（4小题，每小题6分，共24分）1（根据树的完整程度酌情减分）2解：该问题相当于求图的最小生成树问题，此图的最小生成树为： （4分）因此如图铺设煤气管道所需费用最小，最小费用为：2222222+33+4+125（万元） （2分）3解：1） 邻接矩阵为：（2分）2） （2分）由到长度为2的路有1条，由到长度为4的路有3条。(1分）3）的可达性矩阵为 （1分）4答：（1）的关系图为的关系矩阵

9、为 （2分）（2）， （1分） （1分） （2分）四、证明题（2小题，每小题8分，共16分）1证明：1）先证明是入射（3分）对任意的则有，从而有，故是入射。2) 再证明是满射（3分）对任意的从而是满射。综合（1）、（2）知是双射。（2分）2该命题符号化为：（2分）证: (1) P (6) T(2) I （1分） (2) ES (1) （1分） (7) T(4),(5) I （1分） (3) P (8) T(6),(7) I （1分） (4) US (3) （1分）(9) EG(8) （1分） (5) T(2) I 一、单选题（20小题，每小题2分，共40分）得分1下列关系中能构成函数的是（ ）

10、。A； B；C； D252张扑克牌分配给4个桥牌比赛者进行比赛，那么扑克牌集合A到桥牌比赛者集合B的函数是（ ）。A.入射 B.满射 C.双射 D.映射3设图G有5个结点，若各结点的度数分别为：3 ,4, 6, 2, 3, 则G有（ ）条边。A10；B20；C9；D184下列句子是命题的是( ) A再过5000年，地球上就没水了 BC水开了吗? D我正在说谎5下图中是哈密尔顿图的是（ ）。6给定公式：($x) (A（x）®B），与之等价的公式是 （ ）A($x) A（x）®B B ("x) A（x）®B C ØB ®($x) A（x）

11、 D ØB ®($x) Ø A（x）7下面哪个图是强连通的（ ）。8下列等价式不成立的是（）A BC D9设为无向图，=7，=23，则G一定是（ ）。A完全图； B树； C简单图； D多重图10下列等价公式正确的是（ ）A； B；C； D11下列等价式不成立的是（ ）.A; BC D 12设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（ ）个三角形。A100； B200； C300； D60013下面哪一种图不一定是树（）A无圈的连通图；B有个结点条边的连通图；C每对结点间都有路的图；D连通但删去一条边就不连通的图14设，以下哪一个关系是从到的满射 (

12、 )。ABC D 15设，下列二元关系为到的函数的是( )A BC D 16设，则有（ ）。A1,2 ； B1,2 ； C1 ； D217下列各图不是欧拉图的是( )18命题公式 中极小项的个数为（ ）A0 B1C2 D3 19关系R所具有的关系矩阵，则关系R所具有的性质是（ ）A自反的，对称的，可传递的 B自反的，反对称的，可传递的C自反的，对称的 D都不是20下列符号串是合式公式的是（ ）A、 ；B、 ；C、 ；D、 。二、填空题（20小题，每空1分，共20分）得分1设是到的函数，如果，则称为 2设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。3设集合，上的关系，（） 4

13、设的函数，且，则 。 5命题公式（ØP ®Q）®（Ø QÚ P）的主析取范式为 。6设是集合上的二元关系，则= 。7设图G=V，E，V,的邻接矩阵A(G) = ，则的出度为 。8设表示“天下雨”， 表示“我骑自行车上班”，则命题“除非下雨，否则我骑自行车上班”符号化为 。9在偏序集中，其中=2,3,6,12,24,36，是中的整除关系，则集合=2,3,6的极大元是 10设表示“是马”，表示“是动物”则命题“马是动物，动物不一定是马”符号化为 11设A为任一集合，则 12在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合

14、=2,3,4,6的极小元是 13写出下表中所定义的命题联结词 0 00 11 01 1 0 1 1 1 14对谓词公式（"x）P（x）Ú（$y）Q（y）®（"x）R（x）中约束变元应用变换规则所得到的前束范式是 15设R是实数集合， ，且，则 16设命题公式的真值表为00001111001100110101010100101100则命题公式的主析取范式为 。 17完全图K5 的连通分支数是 。18设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则的关系矩阵是 。19在任何有向图中，= 。20命题公式的逆反式是 。三、简答题（4小题，每小题6分

15、，共24分）得分1以给定权2， 4， 5， 8， 13， 15， 18， 25构造一棵最优二叉树2设 =1,2,3,4,5,6，集合上的关系=1,3,1,5,2,5,4,4,4,5,5,4,6,3,6,6。（1）画出的关系图，并求它的关系矩阵；（2）求及 。3今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示要求设计一个最经济的煤气管道路线，并求所需的总费用ABCDEFGHIJKS2222223.554526345314对有向图求解下列问题： 1）写出邻接矩阵； 2）中由到长度为2和4的路有几条？3）求出的可达性矩

16、阵。 v1v4v2v3四、证明题（2小题，每小题8分，共16分）得分1符号化下列命题并推证其结论所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数）2设为 ，证明：是双射。一、单选题（20小题，每小题2分，共40分）12345678910BB CABBABDD11121314151617181920BBCBAADDBC二、填空题（20小题，每空1分，共20分）1满射283，或R45或（PÙQ）Ú（PÙØ Q）Ú（ØPÙØQ）6；7189610或11122,3 1314（$x）（" y）（"z）（P（x）ÚQ（y）®R（z）151617118或单位矩阵19E20三、简答题（4小题，每小题6分，共24分）1（根据树的完整程度酌情减分）2答：（1）的关系图为的关系矩阵为 （2分）（2）， （1分） （1分） （2分）3解：该问题相当于求图的最小生成树问题，此图的最小生成树为： （4分）因此如图铺设煤气管道所需费用最小，最小费用为：2222222+33+4+125（万元） （2分）4解：3） 邻接矩阵为：（2分）4） （2分）由到长度为2的路有1条，由到长度为4的路有3条。(1分）