离散数学AB卷7套期末考试卷带答案-模拟试卷-测试卷-期末考试题.doc
一、单选题（20小题，每小题2分，共40分）得分1、下列蕴含式不成立的是（ ）.ABC D. 2、集合上的关系为一个偏序关系，当且仅当具有（ ）。A自反性、对称性和传递性 B自反性、反对称性和传递性C反自反性、对称性和传递性 D反自反性、反对称性和传递3、设是一个复合映射。下列哪个命题是假命题（）A若是满射，则是满射 B若是入射，则是入射C若是双射，则和都是双射 D若和都是双射，则是双射4、设=1，2，3，上的二元关系=，则的对称闭包是（ ） A B C D5、下列各图是欧拉图的是（ ）6、设G=V，E为（，）连通图，则要确定的一棵生成树，必删去的边数是（）A；B；C；D7、前提条件：P®（Q ®S），Q, PÚØR, 则它的有效推论为（ ）AS B R ® S CP DR ® Q8、命题公式 中极小项的个数为（ ）A0 B1C2 D3 9、谓词演算中，是的有效结论，其理论依据是（）A全称指定规则（US） C全称推广规则（UG）B存在指定规则（ES） D存在推广规则（EG）10、设，集合上的等价关系所确定的的划分的是a, b, c ，则=( )A < a, a>,<b, b >,<c, b>,<b, c>,<c, c> B< a ,b>,<b, a >,<c, b>,<b, c>C< a ,b>,<b, a >,<c, b> D< a, a>,< a ,b>,<b, a >,<c, b>,<b, c>,<c, c> 11、设N为自然数集，：N N，则是( )A是入射不是满射 B既非入射也非满射 C是满射不是入射 D是双射12、下面给出的四个图中，哪个不是汉密尔顿图（ ）13、下列哪个命题是假命题（）A如果2+2=4，则太阳从东方升起；B如果2+2=4，则太阳从西方升起；C如果2+24，则太阳从东方升起；D如果2+24，则太阳从西方升起14、具有个结点的完全图是欧拉图，则为( )。A偶数； B奇数； C9； D1015、命题“所有的马都比某些牛跑得快”的符号化公式为（ ）假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。A("x) (H（x）Ù ( $y)( (C（y）Ù F(x,y) B("x) (H（x）® ( $y)( (C（y）® F(x,y)C("x) (H（x）® ( $y)( (C（y）Ù F(x,y)D( $y) ("x) (H（x）® ( (C（y）Ù F(x,y)16、n阶完全图结点v的度数为（ ）。An； Bn-1； Cn+1； D2(n-1)17、下面哪个图是强连通的（ ）18、设是图的邻接矩阵，则为（）A结点的度数； B结点的度数； C结点的入度； D图中由到长度为的路径的条数19、设有向图，其中，则G是（ ）。A强连通图 B单向连通图 C弱连通图 D非连通图20、，其中，为集合的对称差运算，则方程的解为（ ）。A； B； C； D二、填空题（20小题，每空1分，共20分）得分1、在任何图中，其奇数度结点的个数必为 。2、完全图K5 的边数是 。3、无向图中有10条边，且每个结点的度数均为4，则结点数是 4、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树根。5、设，上的二元关系=，则具有 性。6、在下图所给的偏序集中，集合的下确界是 。7、设是A到B的函数，若使是B到A的函数，必须满足 8、设P，Q 的真值为0，R，S的真值为1，则的真值= 。9、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的极小元是 10、以为子集的最少元素的集合为 11、设R是集合A上的二元关系，则r(R) = 12、设R是实数集合， ，且，则 13、给定命题公式：P Ú（ØP®（QÚ(Ø Q®R)）则它的成假值为 。14、集合上的关系，则= 。15、由前提（"x）（F（x）® H（x）, （"x）ØH（x）可得出的有效结论是 16、写出下表中各列所定义的命题联结词 0 00 11 01 1 0 0 0 1 17、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。18、设, 则= 其中 表示集合的幂集19、谓词公式Ø（F（x,y）ÚR（x,y）Ù R（x,y）是 （重言式，矛盾式，可满足式）20、设是到的函数，若 ，则称为双射。三、简答题（4小题，每小题6分，共24分）得分1、对有向图求解下列问题： 1）写出邻接矩阵； 2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。 2、以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。3、下图给出的赋权图表示五个城市A、B、C、D、E及架起城市间直接通讯线路的预测造价（以千万RMB计）。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。4、设=1,2,3,5,6,10,15,30 ， “” 为集合上的整除关系。，是否为偏序集? 若是，画出其哈斯图。四、证明题（2小题，每小题8分，共16分）得分1、符号化下列命题并推证其结论任何人如果他喜欢音乐,他就不喜欢体育每个人或者喜欢体育，或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐（设M(x)：x喜欢音乐，S(x)：x喜欢体育，(x)：喜欢美术个体域是人类集合）2、设函数，证明是双射的。一、单选题（20小题，每小题2分，共40分）12345678910ABCCBCBDAA11121314151617181920BDBBCBADCA二、填空题（20小题，每空1分，共20分）1、偶数2、103、54、入度为0的结点5、对称6、7、f是双射8、19、2,3 10、11、12、13、00014、15、（"x）ØF（x） 16、17、818、819、矛盾式20、既是单射又是满射三、简答题（4小题，每小题6分，共24分）1、解：1） 邻接矩阵为：（2分）2） （2分）由到长度为2的路有1条，由到长度为4的路有2条。(1分）3）的可达性矩阵为 （1分）2、（根据树的完整程度酌情减分）3、解：根据克鲁斯科尔算法，最小生成树如图所示，即包含如下四条边：（4分）C ( A , B ) , C ( B , C ) , C ( D , E ) , C ( B , E )C ( T ) = 3+6+2+4 = 15 ( 千万RMB ) （2分）4、答：（1），是偏序集。（2分）（2）其哈斯图为：（4分）四、证明题（2小题，每小题8分，共16分）1、（1）该命题符号化为：（）（M（x）S（x）（）（S（x）A（x）（x） A（x）（x） M（x）（2分）（2）（6分）证：（1）（x） A（x） P （2） A（a） ES（1） （3）（）（S（x）A（x） P（4）S（a）A（a） US（3）（5）S（a） T（2）（4）I（6）（）（M（x）S（x） P（7）M（a）S（a） US（6）（8）S（a） M（a） T（7）E（9） M（a） T（5）（8）I（10）（x） M（x） EG（9）2、证明：假设存在，使得，则且，那么且，由此得，即f是入射。（3分）任取，均有，使得，从而是满射。（3分）综合知是双射。 （2分）一、单选题（20小题，每小题2分，共40分）得分1、设，集合上的等价关系所确定的的划分的是a, b, c ，则=( )A < a, a>,<b, b >,<c, b>,<b, c>,<c, c> B< a ,b>,<b, a >,<c, b>,<b, c>C< a ,b>,<b, a >,<c, b> D< a, a>,< a ,b>,<b, a >,<c, b>,<b, c>,<c, c> 2、设是一个复合映射。下列哪个命题是假命题（）A若是满射，则是满射 B若是入射，则是入射C若是双射，则和都是双射 D若和都是双射，则是双射3、下面给出的四个图中，哪个不是汉密尔顿图（ ）4、下列蕴含式不成立的是（ ）.ABC D. 5、下面哪个图是强连通的（ ）6、具有个结点的完全图是欧拉图，则为( )。A偶数； B奇数； C9； D107、下列各图是欧拉图的是（ ）8、，其中，为集合的对称差运算，则方程的解为（ ）。A； B； C； D9、前提条件：P®（Q ®S），Q, PÚØR, 则它的有效推论为（ ）AS B R ® S CP DR ® Q10、设有向图，其中，则G是（ ）。A强连通图 B单向连通图 C弱连通图 D非连通图11、下列哪个命题是假命题（）A如果2+2=4，则太阳从东方升起；B如果2+2=4，则太阳从西方升起；C如果2+24，则太阳从东方升起；D如果2+24，则太阳从西方升起12、设=1，2，3，上的二元关系=，则的对称闭包是（ ） A B C D13、设是图的邻接矩阵，则为（）A结点的度数； B结点的度数； C结点的入度； D图中由到长度为的路径的条数14、命题公式 中极小项的个数为（ ）A0 B1C2 D3 15、集合上的关系为一个偏序关系，当且仅当具有（ ）。A自反性、对称性和传递性 B自反性、反对称性和传递性C反自反性、对称性和传递性 D反自反性、反对称性和传递16、设N为自然数集，：N N，则是( )A是入射不是满射 B既非入射也非满射 C是满射不是入射 D是双射17、命题“所有的马都比某些牛跑得快”的符号化公式为（ ）假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。A("x) (H（x）Ù ( $y)( (C（y）Ù F(x,y) B("x) (H（x）® ( $y)( (C（y）® F(x,y)C("x) (H（x）® ( $y)( (C（y）Ù F(x,y)D( $y) ("x) (H（x）® ( (C（y）Ù F(x,y)18、设G=V，E为（，）连通图，则要确定的一棵生成树，必删去的边数是（）A；B；C；D19、谓词演算中，是的有效结论，其理论依据是（）A全称指定规则（US） C全称推广规则（UG）B存在指定规则（ES） D存在推广规则（EG）20、n阶完全图结点v的度数为（ ）。An； Bn-1； Cn+1； D2(n-1)二、填空题（20小题，每空1分，共20分）得分1、设是到的函数，若 ，则称为双射。2、谓词公式Ø（F（x,y）ÚR（x,y）Ù R（x,y）是 （重言式，矛盾式，可满足式）3、设, 则= 其中 表示集合的幂集4、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。5、写出下表中各列所定义的命题联结词 0 00 11 01 1 0 0 0 1 6、在下图所给的偏序集中，集合的下确界是 。7、设是A到B的函数，若使是B到A的函数，必须满足 8、设P，Q 的真值为0，R，S的真值为1，则的真值= 。9、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的极小元是 10、以为子集的最少元素的集合为 11、设R是集合A上的二元关系，则r(R) = 12、设R是实数集合， ，且，则 13、给定命题公式：P Ú（ØP®（QÚ(Ø Q®R)）则它的成假值为 。14、集合上的关系，则= 。15、由前提（"x）（F（x）® H（x）, （"x）ØH（x）可得出的有效结论是 16、设，上的二元关系=，则具有 性。17、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树根。18、无向图中有10条边，且每个结点的度数均为4，则结点数是 19、完全图K5 的边数是 。20、在任何图中，其奇数度结点的个数必为 。三、简答题（4小题，每小题6分，共24分）得分1、对有向图求解下列问题： 1）写出邻接矩阵； 2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。 2、以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。3、设=1,2,3,5,6,10,15,30 ， “” 为集合上的整除关系。，是否为偏序集? 若是，画出其哈斯图。4、下图给出的赋权图表示五个城市A、B、C、D、E及架起城市间直接通讯线路的预测造价（以千万RMB计）。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。四、证明题（2小题，每小题8分，共16分）得分1、设函数，证明是双射的。2、符号化下列命题并推证其结论任何人如果他喜欢音乐,他就不喜欢体育每个人或者喜欢体育，或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐（设M(x)：x喜欢音乐，S(x)：x喜欢体育，(x)：喜欢美术个体域是人类集合）一、单选题（20小题，每小题2分，共40分）12345678910ACDAABBABC11121314151617181920BCDDBBCCAB二、填空题（20小题，每空1分，共20分）1、既是单射又是满射2、矛盾式3、84、85、6、7、f是双射8、19、2,3 10、11、12、13、00014、15、（"x）ØF（x） 16、对称17、入度为0的结点18、519、1020、偶数三、简答题（4小题，每小题6分，共24分）1、解：3） 邻接矩阵为：（2分）4） （2分）由到长度为2的路有1条，由到长度为4的路有2条。(1分）3）的可达性矩阵为 （1分）2、（根据树的完整程度酌情减分）3、答：（1），是偏序集。（2分）（2）其哈斯图为：（4分）4、解：根据克鲁斯科尔算法，最小生成树如图所示，即包含如下四条边：（4分）C ( A , B ) , C ( B , C ) , C ( D , E ) , C ( B , E )C ( T ) = 3+6+2+4 = 15 ( 千万RMB ) （2分）四、证明题（2小题，每小题8分，共16分）1、证明：假设存在，使得，则且，那么且，由此得，即f是入射。（3分）任取，均有，使得，从而是满射。（3分）综合知是双射。 （2分）2、（1）该命题符号化为：（）（M（x）S（x）（）（S（x）A（x）（x） A（x）（x） M（x）（2分）（2）（6分）证：（1）（x） A（x） P （2） A（a） ES（1） （3）（）（S（x）A（x） P（4）S（a）A（a） US（3）（5）S（a） T（2）（4）I（6）（）（M（x）S（x） P（7）M（a）S（a） US（6）（8）S（a） M（a） T（7）E（9） M（a） T（5）（8）I（10）（x） M（x） EG（9） 1 A 第 21 页 共 21 页
