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

一、单选题（20小题，每小题2分，共40分）得分1、有理数集和上定义的下列运算不能构成代数系统的是( )。A B C D2、设是集合上的任意函数，下列哪个命题是真命题（）。A B C D 3、任何无向图G中结点间的连通关系是（ ）。A良序关系 B偏序关系C全序关系 D等价关系4、设是一条链，且，则( )。A是布尔代数 B是有补格 C是分配格 D都不是5、集合上的等价关系，其等价类的集合称为（）A与的并集，记为B与的交集，记为C与的商集，记为D与的差集，记为6、给定命题公式如下：（P Q）（ P Q）该命题公式的成真赋值个数（ ）A0 B1 C2 D3 7、设，*为普通乘法，则是（ ）。A代数系统； B半群； C群； D都不是8、下列公式中，（ ）是矛盾式。A(x) F（x）( $y)F（y） B(x) ( $y) F(x,y) ($x) (y) F(x,y)C (P（x） (y) G(x,y) P（x）)D (x) (P（x） P（a）)9、下列各图是欧拉图的是（ ）10、下面哪一种图不一定是树（）A无圈的连通图；B有个结点条边的连通图；C每对结点间都有路的图；D连通但删去一条边就不连通的图11、设有向图，其中，则G是（ ）。A强连通图 B单向连通图 C弱连通图 D非连通图12、设有向图，其中，则G是（ ）。A强连通图 B单向连通图 C弱连通图 D非连通图13、具有个结点的完全图是欧拉图，则为( )。A偶数； B奇数； C9； D1014、在自然数N上，下列哪种运算可使构成可交换半群( )。A BC D15、谓词演算中，是的有效结论，其理论依据是（）。A全称指定规则（US） C全称推广规则（UG）B存在指定规则（ES） D存在推广规则（EG）16、设为整数集，：，则是（）。A是入射不是满射B是满射不是入射C既非入射也非满射D是双射17、下列关系中能构成函数的是（ ）。A B C D18、下面哪个哈斯图构成分配格（ ）。19、下列等价公式正确的是（ ）。A； B；C； D20、设，则有（ ）个元素。A3； B6； C7； D8二、填空题（20小题，每空1分，共20分）得分1、代数系统Z，+（Z为整数集，+为普通加法）中，Z关于“+”的幺元为 。2、无向图G具有生成树，当且仅当_。3、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的最大元是 4、设=，则= 。其中表示集合的幂集5、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的极小元是 6、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。7、设表示“我去学校”， 表示“明天上午8点下雨”，则命题“只有当明天上午8点不下雨时我才去学校”符号化为 。8、设集合，上的关系，（） 。9、设图G=V，E，V,的邻接矩阵A(G) = ，则从到长度为的路共有 条。10、谓词公式 。11、无向图中有10条边，且每个结点的度数均为4，则结点数是 。12、命题公式的逆反式是 。13、代数系统Z，+（Z为整数集，+为普通加法）中，Z关于“+”的零元为 。14、在格中，对，当且仅当 。15、在格中，对，当且仅当 。16、设，则A的幂集是 17、为实数集合，运算*的定义为：对任意的有，则代数系统最强是 。18、命题公式（P Q）（ Q P）的主合取范式为 。19、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的最小元是 20、在偏序集中，是上的整除关系，则的极大元是 。 三、简答题（4小题，每小题6分，共24分）得分1、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。子 集上确界下确界2、为简单有向图，写出的邻接矩阵，算出，且确定到有多少条长度为3的路? 到有多少条长度为2的路? 到自身长度为3和长度为4的回路各多少条?3、下图给出的赋权图表示八个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。4、设=1,2,3,5,6,10,15,30 ， “” 为集合上的整除关系。(1)，是否为偏序集? 若是，画出其哈斯图；(2)，是否构成格？为什么？(3)，是否构成布尔代数？为什么？四、证明题（2小题，每小题8分，共16分）得分1、设 定义为 ，证明：是双射，并求出其逆映射。2、指出下面推理证明过程中的错误, 并给出正确的证明。用谓词演算的推理规则证明:证: (1) P (6) T(4) I (2) US(1) (7) T(2),(5) I (3) P (8) T(6),(7) I(4) ES(3) (9) EG(8)(5) T(4) I一、单选题（20小题，每小题2分，共40分）1、B2、C3、D4、C5、C6、C7、D8、C9、B10、C11、C12、C13、B14、B15、A16、C17、B18、D19、B20、D二、填空题（20小题，每空1分，共20分）1、02、图G连通3、无4、5、2,3 6、87、8、，9、110、11、512、13、不存在14、b15、16、17、半群18、或P Q 19、无 20、4，5，6三、简答题（4小题，每小题6分，共24分）1、答：子 集上 确 界下 确 界无无2、解：邻接矩阵及，如下：（2分） =2，所以到长度为3的路有2条，它们分别是：和。（1分）=1，所以到长度为2的路有1条：。（1分）=0，到自身无长度为3的回路。（1分）=4，到自身有4条长度为4的回路，它们分别是：、和。（1分）3、解：该问题相当于求上图的最小生成树。按下图架起八个城市间直接通讯线路的造价最小最小造价为：W（T）=180+240+200+280+120+90+220=1330 （2分） （4分）4、解：(1)，是偏序集。 其哈斯图为： （3分）(2)，构成格。因为其任意两个元素都有上确界和下确界。 （1分）(3)，构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。（2分）四、证明题（2小题，每小题8分，共16分）1、证明： 且是入射根据知f是双射。 2、（1）该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2分）（2）正确的证明是：（6分）(1) P (6) T(2) I (2) ES (1) (7) T(4),(5) I (3) P (8) T(6),(7) I (4) US (3) (9) EG(8) (5) T(2) I 一、单选题（20小题，每小题2分，共40分）得分1、给定命题公式如下：（P Q）（ P Q）该命题公式的成真赋值个数（ ）。A0 B1 C2 D3 2、设，*为普通乘法，则是（ ）。A代数系统 B半群 C群 D都不是3、设为整数集，：，则是（）。A是入射不是满射B是满射不是入射C既非入射也非满射D是双射4、下列各图是欧拉图的是（ ）。5、下面哪一种图不一定是树（ ）。A无圈的连通图 B有个结点条边的连通图C每对结点间都有路的图 D连通但删去一条边就不连通的图6、谓词演算中，是的有效结论，其理论依据是（）。A全称指定规则（US） C全称推广规则（UG）B存在指定规则（ES） D存在推广规则（EG）7、集合上的等价关系，其等价类的集合称为（）。A与的并集，记为B与的交集，记为C与的商集，记为D与的差集，记为8、下列公式中，（ ）是矛盾式。A(x) F（x）( $y)F（y） B(x) ( $y) F(x,y) ($x) (y) F(x,y)C (P（x） (y) G(x,y) P（x）)D (x) (P（x） P（a）)9、下面哪个哈斯图构成分配格（ ）。10、设，则有（ ）个元素。A3 B6 C7 D811、设有向图，其中，则G是（ ）。A强连通图 B单向连通图 C弱连通图 D非连通图12、有理数集和上定义的下列运算不能构成代数系统的是( )。A B C D13、设有向图，其中，则G是（ ）。A强连通图 B单向连通图 C弱连通图 D非连通图14、在自然数N上，下列哪种运算可使构成可交换半群( )。A BC D15、设是集合上的任意函数，下列哪个命题是真命题（）。A B C D 16、任何无向图G中结点间的连通关系是（ ）。A良序关系 B偏序关系C全序关系 D等价关系17、设是一条链，且，则( )。A是布尔代数 B是有补格 C是分配格 D都不是18、下列等价公式正确的是（ ）。A； B；C； D19、具有个结点的完全图是欧拉图，则为( )。A偶数； B奇数； C9； D1020、下列关系中能构成函数的是（ ）。A BC D二、填空题（20小题，每空1分，共20分）得分1、在偏序集中，是上的整除关系，则的极大元是 。 2、代数系统Z，+（Z为整数集，+为普通加法）中，Z关于“+”的幺元为 。3、设，则A的幂集是 。4、无向图G具有生成树，当且仅当_。5、设=，则= 。其中表示集合的幂集6、在格中，对，当且仅当 。7、为实数集合，运算*的定义为：对任意的有，则代数系统最强是 。8、设表示“我去学校”， 表示“明天上午8点下雨”，则命题“只有当明天上午8点不下雨时我才去学校”符号化为 。9、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的最小元是 。10、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。11、代数系统Z，+（Z为整数集，+为普通加法）中，Z关于“+”的零元为 。12、设集合，上的关系，（） 。13、在格中，对，当且仅当 。14、命题公式（P Q）（ Q P）的主合取范式为 。15、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的极小元是 。16、命题公式的逆反式是 。17、谓词公式 。18、设图G=V，E，V,的邻接矩阵A(G) = ，则从到长度为的路共有 条。19、在偏序集中，其中=1,2,3,4,6,8,12,14，是中的整除关系，则集合=2,3,4,6的最大元是 。20、无向图中有10条边，且每个结点的度数均为4，则结点数是 。三、简答题（4小题，每小题6分，共24分）得分1、设=1,2,3,5,6,10,15,30 ， “” 为集合上的整除关系。(1)，是否为偏序集? 若是，画出其哈斯图；(2)，是否构成格？为什么？(3)，是否构成布尔代数？为什么？2、为简单有向图，写出的邻接矩阵，算出，且确定到有多少条长度为3的路? 到有多少条长度为2的路? 到自身长度为3和长度为4的回路各多少条?3、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。子 集上确界下确界4、下图给出的赋权图表示八个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。四、证明题（2小题，每小题8分，共16分）得分1、设 定义为 ，证明：是双射，并求出其逆映射。2、指出下面推理证明过程中的错误, 并给出正确的证明。用谓词演算的推理规则证明：证：(1) P (6) T(4) I (2) US(1) (7) T(2),(5) I (3) P (8) T(6),(7) I(4) ES(3) (9) EG(8)(5) T(4) I一、单选题（20小题，每小题2分，共40分）1、C2、D3、C4、B5、C6、A7、C8、C9、D10、D11、C12、B13、C14、B15、C16、D17、C18、B19、B20、B二、填空题（20小题，每空1分，共20分）1、4，5，62、03、4、图G连通5、6、7、半群8、9、无 10、811、不存在12、，13、b14、或P Q 15、2,3 16、17、18、119、无20、5三、简答题（4小题，每小题6分，共24分）1、解：(1)，是偏序集。 其哈斯图为： （3分）(2)，构成格。因为其任意两个元素都有上确界和下确界。 （1分）(3)，构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。（2分）2、解：邻接矩阵及，如下：（2分） =2，所以到长度为3的路有2条，它们分别是：和。（1分）=1，所以到长度为2的路有1条：。（1分）=0，到自身无长度为3的回路。（1分）=4，到自身有4条长度为4的回路，它们分别是：、和。（1分）3、答：子 集上 确 界下 确 界无无4、解：该问题相当于求上图的最小生成树。按下图架起八个城市间直接通讯线路的造价最小最小造价为：W（T）=180+240+200+280+120+90+220=1330 （2分） （4分）四、证明题（2小题，每小题8分，共16分）1、证明： 且是入射根据知f是双射。 2、（1）该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2分）（2）正确的证明是：（6分）(1) P (6) T(2) I (2) ES (1) (7) T(4),(5) I (3) P (8) T(6),(7) I (4) US (3) (9) EG(8) (5) T(2) I 1 A 第 22 页 共 22 页