2025年大学《数学与应用数学》专业题库- 离散数学与图论应用

2025年大学《数学与应用数学》专业题库——离散数学与图论应用考试时间：______分钟总分：______分姓名：______一、选择题（本大题共5小题，每小题3分，共15分。在每小题给出的四个选项中，只有一项是符合题目要求的。）1.设集合A={1,2,3,4},B={2,4,6,8},C={3,4,5,6}，则(A∩B)∪C=?(A){1,2,3,4,5,6,8}(B){2,3,4,6}(C){1,3,5}(D){1,2,4,5,6,8}2.下列哪个关系是集合A上的等价关系？(A)R1={(a,b)|a<b,a,b∈A}(B)R2={(a,b)|a≡b(mod3),a,b∈A}(C)R3={(a,a)|a∈A}(D)R4={(a,b)|a+b是偶数,a,b∈A}3.设有向图G=<V,E>，其中V={v1,v2,v3,v4}，E={(v1,v2),(v2,v3),(v3,v4),(v4,v1),(v1,v3)}。则G中是否存在环？如果存在，请写出所有环。4.设A={a,b,c}，则A上共有多少个不同的关系？5.下列关于函数f:A→B的叙述，正确的是？(A)对于任意a1,a2∈A,若a1≠a2，则f(a1)≠f(a2)(B)对于任意b∈B，必存在a∈A，使得f(a)=b(C)函数的值域是集合B的子集(D)函数的像等于函数的值域二、填空题（本大题共5小题，每小题4分，共20分。）1.用集合运算符号表示集合{1,2,3}的幂集。2.设集合A有4个元素，其真子集共有________个。3.关系R={(1,2),(2,3),(3,1),(1,1)}在集合A={1,2,3}上的传递闭包是________。4.一个具有n个顶点的无向简单图中，最多可以有多少条边？最少可以有多少条边？5.用归纳法证明1+2+...+n=n(n+1)/2时，第一步需要验证n=________的情况。三、计算题（本大题共3小题，每小题8分，共24分。）1.计算组合数C(10,6)的值，并用二项式定理展开(x+y)^5。2.已知集合A={a,b,c,d}，关系R={(a,b),(b,c),(c,d)}。求R的闭包R1（自反闭包），R2（对称闭包），R3（传递闭包）。3.求解下列方程组：x+y+z=62x-y+z=3x+2y-z=0四、证明题（本大题共2小题，每小题10分，共20分。）1.证明：集合A上的恒等关系IA是等价关系。2.证明：任何无向连通图至少有n-1条边（n为顶点数）。五、应用题（本大题共1小题，共11分。）设有一个有向图G=<V,E>，其中V={A,B,C,D,E}，E={(A,B),(A,C),(B,D),(C,D),(C,E),(D,E)}。请判断图G是否是强连通的？如果是，请给出所有从顶点A到顶点E的路径；如果不是，请找出G的所有强连通分量。试卷答案一、选择题1.(A)2.(B)3.存在。环为(v1,v4)和(v4,v1)。或环为(v1,v3)和(v3,v1)。4.2^6=64个。5.(C)二、填空题1.P(A)={{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}2.15个。3.{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}4.最多n(n-1)/2条边。最少0条边。5.n=1三、计算题1.C(10,6)=10!/(6!*4!)=(10*9*8*7)/(4*3*2*1)=210。(x+y)^5=C(5,0)x^5y^0+C(5,1)x^4y^1+C(5,2)x^3y^2+C(5,3)x^2y^3+C(5,4)x^1y^4+C(5,5)x^0y^5=x^5+5x^4y+10x^3y^2+10x^2y^3+5xy^4+y^5。2.R1（自反闭包）：R∪{(a,a),(b,b),(c,c),(d,d)}={(a,b),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}。R2（对称闭包）：R∪{(b,a),(c,b),(d,c),(a,b),(c,a),(d,b)}={(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(a,a),(b,b),(c,c),(d,d)}。R3（传递闭包）：R∪{(a,c),(a,d),(b,d),(b,e),(c,e),(d,e)}={(a,b),(a,c),(a,d),(b,c),(b,d),(b,e),(c,d),(c,e),(d,e),(a,a),(b,b),(c,c),(d,d)}。3.解：将三个方程相加得4x+2y=9，即2x+y=9/2。用第一个方程减去第三个方程得-y+2z=6，即y=2z-6。将y=2z-6代入2x+y=9/2得2x+2z-6=9/2，即2x+2z=27/2，得x+z=27/4。解得z=27/4-x。将z=27/4-x代入y=2z-6得y=2(27/4-x)-6=54/4-2x-24/4=30/4-2x=15/2-2x。所以解为：x=t,y=15/2-2t,z=27/4-t（t为任意实数）。四、证明题1.证明IA是等价关系：(1)自反性：对于任意a∈A，有(a,a)∈IA。因此IA是自反的。(2)对称性：对于任意a,b∈A，如果(a,b)∈IA，则必有(b,a)∈IA（因为IA中只有(a,a)这样的对）。因此IA是对称的。(3)传递性：对于任意a,b,c∈A，如果(a,b)∈IA且(b,c)∈IA，则必有(a,c)∈IA（因为IA中只有(a,a)这样的对）。因此IA是传递的。由自反性、对称性和传递性知，IA是集合A上的等价关系。2.证明：用反证法。假设存在一个无向连通图G=<V,E>，其边数少于n-1，即|E|<n-1。设G有n个顶点。考虑G的任何一棵生成树T。T有n-1条边，且T是连通的。根据Menger定理的推论（或树的基本性质），一个无向连通图至少存在一个包含n-1条边的生成树。如果G的边数少于n-1，则无法形成包含n-1条边的生成树，这与连通图的性质矛盾。因此，任何无向连通图至少