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

1A第1页共8页一、单选题（20小题，每小题2分，共40分）得分1、下列蕴含式不成立的是（）.A． B．C． D．.2、集合上的关系为一个偏序关系，当且仅当具有（）。A．自反性、对称性和传递性 B．自反性、反对称性和传递性C．反自反性、对称性和传递性 D．反自反性、反对称性和传递3、设是一个复合映射。下列哪个命题是假命题（）．A．若是满射，则是满射 B．若是入射，则是入射C．若是双射，则和都是双射 D．若和都是双射，则是双射4、设={1，2，3}，上的二元关系=，则的对称闭包是（）．A． B． C． D．5、下列各图是欧拉图的是（）．6、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（）．A．ｎ－ｍ－１；B．ｎ－ｍ＋１；C．ｍ－ｎ＋１；D．ｍ－ｎ－１．7、前提条件：P（QS），Q,PR,则它的有效推论为（）A．S B．RS C．P D．RQ8、命题公式中极小项的个数为（ ）A．0 B．1 C．2 D．39、谓词演算中，是的有效结论，其理论依据是（）．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为自然数集，：NN，则是()．A．是入射不是满射 B．既非入射也非满射C．是满射不是入射 D．是双射12、下面给出的四个图中，哪个不是汉密尔顿图（）．13、下列哪个命题是假命题（）．A．如果2+2=4，则太阳从东方升起；B．如果2+2=4，则太阳从西方升起；C．如果2+24，则太阳从东方升起；D．如果2+24，则太阳从西方升起．14、具有个结点的完全图是欧拉图，则为()。A．偶数；B．奇数；C．9；D．10．15、命题“所有的马都比某些牛跑得快”的符号化公式为（）假设：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的度数为（）。A．n；B．n-1；C．n+1；D．2(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(QR)）则它的成假值为。14、集合上的关系，则=。15、由前提（x）（F（x）H（x））,（x）H（x）可得出的有效结论是16、写出下表中各列所定义的命题联结词00011011000117、设有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,310、11、12、13、00014、15、（x）F（x）16、∧17、818、819、矛盾式20、既是单射又是满射三、简答题（4小题，每小题6分，共24分）1、解：邻接矩阵为：（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、下列蕴含式不成立的是（）.A． B．C． D．.5、下面哪个图是强连通的（）．6、具有个结点的完全图是欧拉图，则为()。A．偶数；B．奇数；C．9；D．10．7、下列各图是欧拉图的是（）．8、，其中，为集合的对称差运算，则方程的解为（）。A．；B．；C．；D．9、前提条件：P（QS），Q,PR,则它的有效推论为（）A．S B．RS C．P D．RQ10、设有向图，其中，，则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． D．13、设是图的邻接矩阵，，则为（）．A．结点的度数；B．结点的度数；C．结点的入度；D．图中由到长度为的路径的条数．14、命题公式中极小项的个数为（ ）A．0 B．1 C．2 D．315、集合上的关系为一个偏序关系，当且仅当具有（）。A．自反性、对称性和传递性 B．自反性、反对称性和传递性C．反自反性、对称性和传递性 D．反自反性、反对称性和传递16、设N为自然数集，：NN，则是()．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．ｍ－ｎ＋１；D．ｍ－ｎ－１．19、谓词演算中，是的有效结论，其理论依据是（）．A．全称指定规则（US）C．全称推广规则（UG）B．存在指定规则（ES）D．存在推广规则（EG）．20、n阶完全图结点v的度数为（）。A．n；B．n-1；C．n+1；D．2(n-1)二、填空题（20小题，每空1分，共20分）得分1、设是到的函数，若，则称为双射。2、谓词公式（F（x,y）R（x,y））R（x,y）是（重言式，矛盾式，可满足式）3、设,则=．其中表示集合的幂集．4、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为。5、写出下表中各列所定义的命题联结词0001101100016、在下图所给的偏序集中，集合的下确界是。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(QR)）则它的成假值为。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,310、11、12、13、00014、15、（x）F（x）16、对称17、入度为0的结点18、519、1020、偶数三、简答题（4小题，每小