离散数学AB卷3套期末考试卷带答案-模拟试卷-测试卷-期末考试题.doc
一、单选题（20小题，每小题2分，共40分）得分1、设A=1，2，3上的关系如下，有传递性的有（ ）。A<1，2 >，<2，1 >，<1，3>，<3，1>B<1 ,3>，<3 ,1>C<1，2 >，<2, 3 >，<1，1>D<1 ,2 >，<3，2 >2、下列语句是命题的是（ ）A明年中秋节的晚上是晴天 B C 请保持安静 D我正在说谎3、下列哪个命题是假命题（）A如果2+2=4，则太阳从东方升起；B如果2+2=4，则太阳从西方升起；C如果2+24，则太阳从东方升起；D如果2+24，则太阳从西方升起4、设是正实数集，是实数集，：，则是（ ）A是入射不是满射 B是满射不是入射C既非入射也非满射D是双射5、下列等价式不成立的是（）A BC D6、n阶完全图的边数为（ ）。An(n-1)/2； Bn-1； Cn+1； D2n(n-1)7、设G=V，E为（，）连通图，则要确定的一棵生成树，必删去的边数是（）A；B；C；D8、设为整数集，：，则是（）A是入射不是满射B是满射不是入射C既非入射也非满射D是双射9、设是一个复合映射。下列哪个命题是假命题（）A若是满射，则是满射 B若是入射，则是入射C若是双射，则和都是双射 D若和都是双射，则是双射10、设，则有（ ）。A1,2 ； B1,2 ； C1 ； D211、下列各图是欧拉图的是（ ）A B C D12、在下述公式中是重言式为（ ）A¬ B C DØP®（QÙR）13、设，下列二元关系为到的函数的是( )A BC D 14、设为无向图，=7，=23，则G一定是（ ）。A完全图； B树； C简单图； D多重图15、下列各式哪个是错的（ ）？ A.Æ Í Æ ; B.Æ Î Æ ; C.Æ Ì Æ ; D.Æ Î Æ , Æ16、令:是金属，：是液体，：可以溶解在中，则命题“任何金属可以溶解在某种液体中”可符号化为（）A B C D17、下面四组数能构成无向图的度数列的有（ ）。A2,3,4,5,6,7； B1,2,2,3,4； C2,1,1,1,2； D3,3,5,6,018、无向图是欧拉图，当且仅当（ ）A连通且所有结点的度数为偶数；B的所有结点的度数为偶数；C连通且所有结点的度数为奇数； D的所有结点的度数为奇数19、下列关系中能构成函数的是（ ）。A； B；C； D20、下列哪个谓词公式与 等价？（ ）。A B C D二、填空题（20小题，每空1分，共20分）得分1、在偏序集中，是上的整除关系，则的极大元是 2、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则= 3、命题公式的逆反式是 。4、设，则A的幂集是 5、设表示“x是金子”， 表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。 6、写出下表中所定义的命题联结词 0 00 11 01 1 0 0 0 1 7、设表示“是马”，表示“是动物”则命题“马是动物，动物不一定是马”符号化为 8、在偏序集中，其中=2,3,6,12,24,36，是中的整除关系，则集合=2,3,6的极大元是 9、在下图所给的偏序集中，集合的上确界是 。 10、设A为任一集合，则 11、在下图所给的偏序集中，集合的下确界是 。12、一棵树有2个度为2的结点，1个度为3的结点，4个度为4的结点，1个度为5的结点，其余均是度为1的结点，则有 个度为1的结点13、命题公式¬（PQ）的主析取范式为 14、完全图K5 的边数是 。15、设是到的函数，若 ，则称为双射。16、设上的关系的关系图如下，从关系图可知具有的性质是 17、设表示“我将取得好成绩”， 表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为 。18、设是图的邻接矩阵，则图中由到长度为的路径的条数为 19、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树叶。20、设=，则×= 。其中表示集合的幂集三、简答题（4小题，每小题6分，共24分）得分 1 A 第 5 页 共 20 页1、对有向图求解下列问题： 1）写出邻接矩阵； 2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。 2、以给定权2， 4， 5， 8， 13， 15， 18， 25构造一棵最优二叉树3、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。子 集上确界下确界4、今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示要求设计一个最经济的煤气管道路线，并求所需的总费用ABCDEFGHIJKS2222223.55452634531四、证明题（2小题，每小题8分，共16分）得分1、设函数，证明是双射的。2、符号化下列命题并推证其结论所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数）一、单选题（20小题，每小题2分，共40分）第 8 页 共 20 页1、D2、A3、B4、D5、B6、A7、C8、C9、C10、A11、B12、B13、A14、D15、C16、C17、B18、A19、B20、D二、填空题（20小题，每空1分，共20分）1、4，5，62、3、4、5、 或 6、7、或8、69、10、11、12、1413、（PQ）（PQ）14、1015、既是单射又是满射16、反自反性、反对称性和传递性17、18、19、出度为0的结点20、三、简答题（4小题，每小题6分，共24分）1、解：1） 邻接矩阵为：（2分）2） （2分）由到长度为2的路有1条，由到长度为4的路有3条。(1分）3）的可达性矩阵为 （1分）2、（根据树的完整程度酌情减分）3、答：子 集上 确 界下 确 界无无4、解：该问题相当于求图的最小生成树问题，此图的最小生成树为： （4分）因此如图铺设煤气管道所需费用最小，最小费用为：2222222+33+4+125（万元） （2分）四、证明题（2小题，每小题8分，共16分）1、证明：假设存在，使得，则且，那么且，由此得，即f是入射。 （3分）任取，均有，使得，从而是满射。（3分）综合知是双射。 （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、下列等价式不成立的是（）A BC D2、令:是金属，：是液体，：可以溶解在中，则命题“任何金属可以溶解在某种液体中”可符号化为（）A B C D3、设，下列二元关系为到的函数的是( )A BC D 4、设G=V，E为（，）连通图，则要确定的一棵生成树，必删去的边数是（）A；B；C；D5、无向图是欧拉图，当且仅当（ ）A连通且所有结点的度数为偶数；B的所有结点的度数为偶数；C连通且所有结点的度数为奇数； D的所有结点的度数为奇数6、设，则有（ ）。A1,2 ； B1,2 ； C1 ； D27、下列关系中能构成函数的是（ ）。A； B；C； D8、下面四组数能构成无向图的度数列的有（ ）。A2,3,4,5,6,7； B1,2,2,3,4； C2,1,1,1,2； D3,3,5,6,09、设是正实数集，是实数集，：，则是（ ）A是入射不是满射 B是满射不是入射C既非入射也非满射D是双射10、下列哪个谓词公式与 等价？（ ）。A B C D11、设为整数集，：，则是（）A是入射不是满射B是满射不是入射C既非入射也非满射D是双射12、下列语句是命题的是（ ）A明年中秋节的晚上是晴天 B C 请保持安静 D我正在说谎13、设A=1，2，3上的关系如下，有传递性的有（ ）。A<1，2 >，<2，1 >，<1，3>，<3，1>B<1 ,3>，<3 ,1>C<1，2 >，<2, 3 >，<1，1>D<1 ,2 >，<3，2 >14、下列各图是欧拉图的是（ ）A B C D15、下列哪个命题是假命题（）A如果2+2=4，则太阳从东方升起；B如果2+2=4，则太阳从西方升起；C如果2+24，则太阳从东方升起；D如果2+24，则太阳从西方升起16、n阶完全图的边数为（ ）。An(n-1)/2； Bn-1； Cn+1； D2n(n-1)17、在下述公式中是重言式为（ ）A¬ B C DØP®（QÙR）18、设是一个复合映射。下列哪个命题是假命题（）A若是满射，则是满射 B若是入射，则是入射C若是双射，则和都是双射 D若和都是双射，则是双射19、下列各式哪个是错的（ ）？ A.Æ Í Æ ; B.Æ Î Æ ; C.Æ Ì Æ ; D.Æ Î Æ , Æ20、设为无向图，=7，=23，则G一定是（ ）。A完全图； B树； C简单图； D多重图二、填空题（20小题，每空1分，共20分）得分1、设表示“我将取得好成绩”， 表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为 。2、设表示“是马”，表示“是动物”则命题“马是动物，动物不一定是马”符号化为 3、在下图所给的偏序集中，集合的上确界是 。 4、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则= 5、设=，则×= 。其中表示集合的幂集6、设是图的邻接矩阵，则图中由到长度为的路径的条数为 7、一棵树有2个度为2的结点，1个度为3的结点，4个度为4的结点，1个度为5的结点，其余均是度为1的结点，则有 个度为1的结点8、写出下表中所定义的命题联结词 0 00 11 01 1 0 0 0 1 9、完全图K5 的边数是 。10、命题公式¬（PQ）的主析取范式为 11、设A为任一集合，则 12、在偏序集中，是上的整除关系，则的极大元是 13、设表示“x是金子”， 表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。 14、在下图所给的偏序集中，集合的下确界是 。15、命题公式的逆反式是 。16、设，则A的幂集是 17、设上的关系的关系图如下，从关系图可知具有的性质是 18、设是到的函数，若 ，则称为双射。19、在偏序集中，其中=2,3,6,12,24,36，是中的整除关系，则集合=2,3,6的极大元是 20、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树叶。三、简答题（4小题，每小题6分，共24分）得分 1 B 第 15 页 共 20 页1、对有向图求解下列问题： 1）写出邻接矩阵； 2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。 2、今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示要求设计一个最经济的煤气管道路线，并求所需的总费用ABCDEFGHIJKS2222223.554526345313、以给定权2， 4， 5， 8， 13， 15， 18， 25构造一棵最优二叉树4、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。子 集上确界下确界四、证明题（2小题，每小题8分，共16分）得分1、设函数，证明是双射的。2、符号化下列命题并推证其结论所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数）一、单选题（20小题，每小题2分，共40分）第 20 页 共 20 页1、B2、C3、A4、C5、A6、A7、B8、B9、D10、D11、C12、A13、D14、B15、B16、A17、B18、C19、C20、D二、填空题（20小题，每空1分，共20分）1、2、或3、4、5、6、7、148、9、1010、（PQ）（PQ）11、12、4，5，613、 或 14、15、16、17、反自反性、反对称性和传递性18、既是单射又是满射19、620、出度为0的结点三、简答题（4小题，每小题6分，共24分）1、解：邻接矩阵为：（2分）3） （2分）由到长度为2的路有1条，由到长度为4的路有3条。(1分）3）的可达性矩阵为 （1分）2、解：该问题相当于求图的最小生成树问题，此图的最小生成树为： （4分）因此如图铺设煤气管道所需费用最小，最小费用为：2222222+33+4+125（万元） （2分）3、（根据树的完整程度酌情减分）4、答：子 集上 确 界下 确 界无无四、证明题（2小题，每小题8分，共16分）1、证明：假设存在，使得，则且，那么且，由此得，即f是入射。 （3分）任取，均有，使得，从而是满射。（3分）综合知是双射。 （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
