2025年大学《数理基础科学》专业题库- 离散数学中的实战计算案例

2025年大学《数理基础科学》专业题库——离散数学中的实战计算案例考试时间：______分钟总分：______分姓名：______一、选择题（每题3分，共15分）1.设集合A={1,2,3,4},B={2,4,6,8},则A∩B=?A.{1,3}B.{2,4}C.{1,2,3,4}D.{6,8}2.下列哪个命题公式是重言式？A.(p∧q)→pB.p∨¬pC.p∧¬pD.¬(p∧q)↔¬p∨¬q3.设集合A有5个元素，集合B有3个元素，则从A到B的函数个数是？A.15B.20C.30D.604.一个无向图G有6个顶点，每个顶点的度数都是3，则图G的边数是多少？A.6B.9C.12D.185.已知a_n=n(n+1)，则a_5的值是？A.10B.15C.20D.30二、填空题（每题4分，共20分）1.谓词公式∀x(P(x)→Q(x))的翻译是？2.集合{1,2,3}的所有子集个数是？3.图G的一个拓扑排序是指图G的一个顶点线性序列，使得对于图G中的任意一条边(u,v)，都有u在v之前，则一个有向无环图存在拓扑排序的充要条件是？4.组合数C(10,3)的值是？5.设a_1=1,a_2=2,a_n=a_(n-1)+a_(n-2)(n≥3)，则a_6的值是？三、计算题（每题6分，共18分）1.求命题公式(p∧q)∨¬r的主析取范式。2.计算集合A={1,2,3}和B={x|x是小于10的偶数}的笛卡尔积A×B。3.一个无向图G有4个顶点，边集E={{1,2},{1,3},{1,4},{2,3},{2,4}}，求图G的连通分量个数。四、证明题（每题7分，共14分）1.证明：对于任意集合A,B,C，有A×(B∩C)=(A×B)∩(A×C)。2.证明：一个无向图G是连通图当且仅当G中存在一个顶点，使得从该顶点到G中其他所有顶点都有路径。五、综合应用题（每题7分，共14分）1.有5个不同的任务要分配给3个不同的机器完成，每个任务只能分配给一个机器，每个机器至少完成一个任务，问共有多少种不同的分配方法？2.某城市有6条南北方向的街道和4条东西方向的街道，一个人从城市的一个角落出发，只允许向右或向上行走，问有多少种不同的路径可以到达城市的另一个角落？试卷答案一、选择题1.B2.B3.D4.B5.D二、填空题1.对于所有x，如果P(x)成立，那么Q(x)也成立。2.83.图G是强连通的。4.1205.13三、计算题1.(p∧q∧¬r)∨(p∧¬q∧¬r)∨(¬p∧q∧¬r)∨(¬p∧¬q∧r)2.{(1,2),(1,4),(1,6),(1,8),(2,2),(2,4),(2,6),(2,8),(3,2),(3,4),(3,6),(3,8)}3.1四、证明题1.证明思路：利用集合论中的元素分析法。任取(x,y)∈A×(B∩C)。则x∈A且y∈B∩C。由y∈B∩C可得y∈B且y∈C。因此(x,y)∈A×B且(x,y)∈A×C。所以(x,y)∈(A×B)∩(A×C)。反之，任取(x,y)∈(A×B)∩(A×C)。则(x,y)∈A×B且(x,y)∈A×C。由(x,y)∈A×B可得x∈A且y∈B。由(x,y)∈A×C可得x∈A且y∈C。因此y∈B∩C。所以(x,y)∈A×(B∩C)。综上，A×(B∩C)=(A×B)∩(A×C)。2.证明思路：必要性。假设G是连通图，任取一个顶点v_0∈V(G)。由于G是连通图，对于任意顶点v∈V(G)，存在一条从v_0到v的路径。因此，从v_0可以到达G中所有其他顶点，即v_0连接到G中所有其他顶点。所以G是连通图。充分性。假设G中存在一个顶点v_0，使得从v_0到G中其他所有顶点都有路径。那么对于任意两个顶点v_1,v_2∈V(G)，存在从v_0到v_1的路径P_1和从v_0到v_2的路径P_2。那么可以通过路径P_1和P_2在G中找到一条从v_1到v_2的路径。因此，G是连通图。五、综合应用题1.解法一：先计算所有任务分配给3个机器的总方法数，再减去不满足每个机器至少完成一个任务的方法数。总方法数是3^5=243。不满足条件的方法数是3×2^5=96(每个机器选择1个任务，剩下的4个任务分配给1个机器)或1×1^5=1(所有任务分配给1个机器)。所以满足条件的方法数是243-96-1=146。解法二：使用容斥原理。满足至少一个机器完成一个任务的方法数是3×2^5-3×1^5+1=117。所以满足每个机器至少完成一个任务的方法数是243-117=146。2.解法一：将路径分解为6次向右和