2025年大学《数理基础科学》专业题库- 组合数学与离散数学

2025年大学《数理基础科学》专业题库——组合数学与离散数学考试时间：______分钟总分：______分姓名：______一、选择题（本大题共10小题，每小题2分，共20分。下列每小题给出的四个选项中，只有一项是符合题目要求的。请将正确选项前的字母填在答题卡相应位置。）1.从n个不同元素中取出k个元素，不考虑顺序组成一组，称为从n个不同元素中每次取出k个元素的（）。A.排列B.组合C.排列数D.组合数2.设集合A有m个元素，集合B有n个元素，则从集合A到集合B的映射个数是（）。A.mB.nC.mnD.2^(mn)3.在40个学生中，有30个会打篮球，有25个会打排球，且至少会打这两种球中的至少一种的人数是55个，则两种球都会打的共有（）个。A.10B.15C.20D.254.下列数中，哪个是素数？（）A.49B.53C.57D.615.5个不同的球放入3个不同的盒子里，每个盒子至少放一个球，不同的放法共有（）种。A.150B.210C.240D.3126.一个有向图G包含n个顶点，则G中边的条数最多是（）条。A.nB.n(n-1)C.n(n+1)/2D.n(n-1)/27.在一棵树中，顶点的度数之和等于（）。A.顶点数-1B.顶点数+1C.边数-1D.边数+18.下列命题中，真命题是（）。A.空集是任何集合的子集B.任何集合都有无数个子集C.两个集合的交集一定是真子集D.两个集合的并集一定是真子集9.设命题p:2是偶数，命题q:3是质数，则命题“p且q”的真值是（）。A.真假不定B.假C.真D.无法判断10.下列逻辑表达式，哪个是永真式？（）A.p∧¬pB.p∨¬pC.p∧pD.p∨p二、填空题（本大题共5小题，每小题3分，共15分。请将答案填在答题卡相应位置。）1.一个排列中，若某个元素不在其原来的位置上，则称这个元素为该排列的一个（）。2.设集合A有m个元素，集合B有n个元素，则从集合A到集合B的所有函数个数是（）。3.10个人两两握手的次数总和是（）次。4.在有向图中，一个顶点的入度是指以该顶点为（）的边的条数。5.命题逻辑中，命题p和命题q的逆否命题是（）。三、计算题（本大题共5小题，每小题6分，共30分。请将详细的计算过程和答案写在答题卡相应位置。）1.计算组合数C(10,3)。2.计算排列数P(6,4)。3.有5门课要排在一天的4节课里，每天至少安排一门课，有多少种不同的排法？4.计算有向图G中所有顶点的度数之和，其中G有6个顶点，且每条边都连接了两个不同的顶点。5.计算逻辑表达式(p∧q)∨(¬p∧¬q)的真值表。四、证明题（本大题共3小题，每小题15分，共45分。请将详细的证明过程写在答题卡相应位置。）1.证明：对于任意正整数n，2^n>n。2.证明：任何一棵树都至少有两个度数为1的顶点。3.证明：命题逻辑中，一个命题公式是永假式，当且仅当它的否定是永真式。五、应用题（本大题共2小题，每小题20分，共40分。请将详细的解答过程和答案写在答题卡相应位置。）1.在一个小组中有7名男生和5名女生，要选出一个小组委员会，其中包含3名男生和2名女生，有多少种不同的选法？2.一个通讯网络由n个节点组成，每个节点都可以与其他节点直接或间接连接。证明：如果每个节点至少与其他两个节点连接，则网络中存在一个节点，它至少与其他三个节点连接。试卷答案一、选择题1.B2.D3.A4.B5.C6.D7.A8.A9.C10.B二、填空题1.错位2.n^m3.454.终点5.(¬q)∧(¬p)三、计算题1.C(10,3)=10!/(3!*(10-3)!)=10!/(3!*7!)=(10*9*8)/(3*2*1)=1202.P(6,4)=6!/(6-4)!=6!/2!=6*5*4*3=3603.先从5门课中选出1门安排在第一节课，有C(5,1)种选法；然后从剩下的4门课中选出2门安排在第二节课，有C(4,2)种选法；剩下的2门课安排在第三节课；最后1门课安排在第四节课。由于课程顺序不同被视为不同排法，因此总的排法数为C(5,1)*C(4,2)*2!*1!=5*6*2*1=60种。但是，每天至少安排一门课，所以需要减去一天都不安排课的情况，即5门课都安排在3节课中的情况，有C(5,3)*3!=10*6=60种。因此，总的排法数为60-60=0种。这里有一个错误，正确的计算应该是从5门课中选出2门安排在第一节课，有C(5,2)种选法；然后从剩下的3门课中选出2门安排在第二节课，有C(3,2)种选法；剩下的1门课安排在第三节课；最后1门课安排在第四节课。由于课程顺序不同被视为不同排法，因此总的排法数为C(5,2)*C(3,2)*2!*1!=10*3*2*1=60种。4.由于每条边都连接了两个不同的顶点，因此每个顶点的度数为2。图中有6个顶点，所以所有顶点的度数之和为6*2=12。这里有一个错误，正确的计算应该是每条边连接两个顶点，所以边的条数是顶点度数之和的一半。如果每个顶点的度数为2，那么顶点度数之和应该是2*n，其中n是边的条数。因此，顶点度数之和应该是2*n=6*2=12，所以n=6。但是，题目中说每条边都连接了两个不同的顶点，这意味着这是一个完全图，每个顶点都与所有其他顶点相连。在一个有n个顶点的完全图中，顶点度数之和是n*(n-1)，因为每个顶点都与其他n-1个顶点相连。所以，顶点度数之和应该是6*(6-1)=30。5.真值表如下：|p|q|¬p|¬q|p∧q|¬p∧¬q|(p∧q)∨(¬p∧¬q)||---|---|----|----|-----|-------|----------------||T|T|F|F|T|F|T||T|F|F|T|F|F|F||F|T|T|F|F|T|T||F|F|T|T|F|T|T|四、证明题1.证明：对于任意正整数n，2^n>n。使用数学归纳法证明。基础情况：当n=1时，2^1=2>1，成立。归纳假设：假设对于某个正整数k，2^k>k成立。归纳步骤：需要证明2^(k+1)>k+1。2^(k+1)=2*2^k>2*k(根据归纳假设)>k+k=2k。因为k是正整数，所以2k>k+1。因此，2^(k+1)>k+1。根据数学归纳法，对于任意正整数n，2^n>n成立。2.证明：任何一棵树都至少有两个度数为1的顶点。证明：使用反证法。假设存在一棵树T，它不包含至少两个度数为1的顶点。由于树是连通的且没有环，所以它至少有两个顶点。如果树只有一个顶点，那么它的度数为0，不满足条件。如果树有两个顶点，那么这两个顶点之间的边是唯一的，每个顶点的度数为1，满足条件。如果树有三个或更多顶点，那么由于每个顶点的度数之和等于边数的两倍，而边数至少为顶点数减1，所以至少有两个顶点的度数为1。因此，任何一棵树都至少有两个度数为1的顶点。3.证明：命题逻辑中，一个命题公式是永假式，当且仅当它的否定是永真式。证明：使用定义和推理规则。必要性：假设命题公式P是永假式，即对于所有的真值赋值，P的值为假。那么，对于P的否定¬P，对于所有的真值赋值，¬P的值为真。因此，¬P是永真式。充分性：假设命题公式P的否定¬P是永真式，即对于所有的真值赋值，¬P的值为真。那么，对于P，对于所有的真值赋值，P的值为假。因此，P是永假式。根据必要性和充分性，命题逻辑中，一个命题公式是永假式，当且仅当它的否定是永真式。五、应用题1.在一个小组中有7名男生和5名女生，要选出一个小组委员会，其中包含3名男生和2名女生，有多少种不同的选法？从7名男生中选出3名，有C(7,3)种选法；从5名女生中选出2名，有C(5,2)种选法。因此，总的选法数为C(7,3)*C(5,2)=35*10=350种。2.一个通讯网络由n个节点组成，每个节点都可以与其他节点直接或间接连接。证明：如果每个节点至少与其他两个节点连接，则网络中存在一个节点，它至少与其他三个节点连接。证明：使用反证法。假设网络中不存在一个节点，它至少与其