离散数学专项试题及参考答案

离散数学专项试题及参考答案考试时间：______分钟总分：______分姓名：______一、单项选择题（每题2分，共20分。下列每小题给出的四个选项中，只有一项是符合题目要求的。请将正确选项前的字母填在题后的括号内。)1.设集合A={1,2,3},B={2,3,4},C={3,4,5}，则(A∪B)∩C=?(A){1,2,3,4}(B){3}(C){2,3,4}(D){1,4,5}2.下列哪个关系是集合A={1,2,3}上的等价关系？(A)R1={(1,1),(2,2),(3,3),(1,2),(2,1)}(B)R2={(1,1),(2,2),(3,3),(1,3),(3,1)}(C)R3={(1,1),(2,2),(3,3),(1,3)}(D)R4={(1,1),(2,2),(3,3),(1,2),(2,3),(3,2)}3.设函数f:Z→Z定义为f(x)=x+1，则f的逆函数f⁻¹(5)的值是？(A)4(B)5(C)6(D)不存在4.下列哪个命题是永真式（重言式）？(A)(p∧¬q)→p(B)p→(p∨q)(C)p∧(q∨r)↔(p∧q)∨(p∧r)(D)¬(p∧q)↔¬p∨¬q5.用数学归纳法证明“对于所有正整数n，1+3+5+...+(2n-1)=n²”时，第二步（归纳步骤）需要假设？(A)1+3+5+...+(2n-1)=n²(B)1+3+5+...+(2(n-1)-1)=(n-1)²(C)1+3+5+...+(2(n+1)-1)=(n+1)²(D)1+3+5+...+(2n+1)=(n+1)²6.一个无向图G有6个顶点，12条边，则G的连通分支数最多是？(A)2(B)3(C)4(D)67.设G是一棵具有n个顶点的树，则G的边数是多少？(A)n-1(B)n(C)n+1(D)2n8.用Prim算法构造最小生成树，每次选择连接到生成树中顶点的边中权值最小的边，这种策略称为？(A)近端优先策略(B)破环策略(C)普遍邻接点策略(D)最小权值优先策略9.计算组合数C(10,6)的值是？(A)210(B)252(C)328(D)33010.递推关系a_n=3a_(n-1)+2a_(n-2)，且a_0=1,a_1=2，则a_3的值是？(A)13(B)16(C)19(D)21二、多项选择题（每题3分，共15分。下列每小题给出的四个选项中，有多项是符合题目要求的。请将正确选项前的字母填在题后的括号内。多选、错选、少选均不得分。)1.下列哪些命题形式是等价的？(A)p→q(B)¬q→¬p(C)¬p∨q(D)p↔¬¬q2.下列哪些图是欧拉图？(A)一个具有4个顶点的完全图K4(B)一个具有5个顶点，每个顶点度数为2的连通图(C)一个圈（例如，六边形）(D)一个有两个奇度顶点的连通图3.在有向图G中，如果存在一条从顶点u到顶点v的路径，那么？(A)u和v一定是强连通的(B)v一定是u的后继(C)从u到v可能存在多条路径(D)u的出度一定大于v的入度4.下列关于排列的说法哪些是正确的？(A)从n个不同元素中取出k个元素的排列数记作P(n,k)(B)P(n,k)=n(n-1)(n-2)...(n-k+1)(C)P(n,n)=n!(D)P(n,0)=15.在一个有n个元素的集合S中，可以定义多少种不同的二元关系？(A)n(B)2^n(C)n^2(D)2^(n^2)三、判断题（每题1分，共10分。请将“对”或“错”填在题后的括号内。)1.空集是任何集合的子集。()2.如果R是集合A上的自反关系，那么R也是对称的。()3.函数f:A→B是满射的，当且仅当对于每一个b∈B，都存在至少一个a∈A使得f(a)=b。()4.命题公式(p∨q)→r与(¬p∧¬q)→¬r是等价的。()5.任何一棵树都至少有一个叶节点。()6.如果一个无向图是欧拉图，那么它一定是连通的。()7.组合数C(n,k)总是小于等于阶乘函数，即C(n,k)≤n!。()8.递推关系a_n=a_(n-1)+a_(n-2)(a_0=0,a_1=1)描述的是斐波那契数列。()9.邻接矩阵只能表示无向图。()10.任何有限状态自动机都可以用正则表达式来描述。()四、计算题（每题6分，共30分。请写出详细的计算过程。)1.设集合A={x|x是小于10的正偶数},B={x|x是小于10的质数}。求A∪B和A∩B。2.判断下列命题公式的类型（永真式、矛盾式、可满足式）：(p∧¬q)∨(¬p∧q)3.计算组合数C(12,4)和C(12,8)。4.设无向图G的顶点集V={v1,v2,v3,v4,v5}，边集E={(v1,v2),(v1,v3),(v2,v4),(v3,v4),(v4,v5)}。求G的邻接矩阵M(G)。并求顶点v3的度数。5.解递推关系a_n=5a_(n-1)-6a_(n-2)，初始条件为a_0=4,a_1=15。五、证明题（每题10分，共20分。请写出严谨的证明过程。)1.证明：设R是集合A上的等价关系，那么对于任意a,b,c∈A，如果[a]_R∩[b]_R≠∅，则[a]_R=[b]_R。2.证明：对于任何正整数n，n^3+5n总是可以被6整除。试卷答案一、单项选择题1.(C)2.(D)3.(A)4.(B)5.(B)6.(A)7.(A)8.(D)9.(B)10.(A)二、多项选择题1.(A,B,C,D)2.(B,C)3.(B,C)4.(A,B,C,D)5.(B,D)三、判断题1.对2.错3.对4.对5.对6.对7.错8.对9.错10.对四、计算题1.A∪B={2,3,4,5,6,8}；A∩B={5}解析：首先列出集合A和B的元素。A={2,4,6,8}。B={2,3,5,7}。并集包含A和B中的所有元素，不重复：2,3,4,5,6,8。交集包含同时属于A和B的元素：5。检查无误。2.该命题公式为可满足式。解析：分析真值表或等价变换。原式(p∧¬q)∨(¬p∧q)可以用分配律变形为(p∨¬p)∧(¬q∨q)，即常真式∧常真式=常真式。所以是永真式。（*注：题目要求判断类型，若允许多选，则永真式也是可满足式。若严格按定义，永真式和可满足式需区分。此处按最常见理解，永真式即为真值总为T，属于可满足式的一种特殊情况。若按标准定义严格区分，此题应选“永真式”。为符合多项选择题“多选”特点且常见出题思路，此处按可满足式包含永真式处理，选ABCD。但需注意，单选题中p∨¬p恒真，故原式恒真，应选A。若此题为单选题，应选A。此处按原单选答案C，则解析应修正为：该命题公式为永真式。解析：利用等价公式进行化简。原式(p∧¬q)∨(¬p∧q)。利用分配律，可得(p∨¬p)∧(¬q∨q)。由于p∨¬p恒为真(T)，¬q∨q恒为真(T)。真与真合取仍为真。因此，该命题公式在任何赋值下都为真，即永真式。*）3.C(12,4)=495；C(12,8)=495解析：利用组合数性质C(n,k)=C(n,n-k)。所以C(12,8)=C(12,12-8)=C(12,4)。计算C(12,4)=12!/(4!*(12-4)!)=12!/(4!*8!)=(12*11*10*9)/(4*3*2*1)=12*11*5*3=1980。（*注：此处计算结果与选项B(252)不符，且与标准答案C(495)不符。根据公式计算C(12,4)=12*11*10*9/(4*3*2*1)=495。C(12,8)=C(12,4)=495。*）4.邻接矩阵M(G)=[[0,1,1,0,0],[1,0,0,1,0],[1,0,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]。顶点v3的度数是3。解析：邻接矩阵中，第i行第j列的元素表示顶点vi和vj之间是否有边。根据边集E，填写矩阵。例如，(v1,v2)存在，M(1,2)=1；(v1,v3)存在，M(1,3)=1；等等。矩阵中第3行为[1,0,0,1,0]。顶点v3的度数等于其对应的行（或列）中1的个数，即1+0+0+1+0=2。（*注：此处计算结果与答案不符，且与直观理解不符。根据边集E，v3与v1,v4相连，度应为2。但根据图论定义，度是边的条数。检查边集，v3与v1,v4,v2相连（因为v2与v4相连，而v3与v4相连，形成间接连接，但边集明确列出v3,v4之间无边）。修正：邻接矩阵M(G)=[[0,1,1,0,0],[1,0,0,1,0],[1,0,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]。顶点v3的度数是其在矩阵中对应的行/列中1的个数，即第3行[1,0,0,1,0]中的1的个数，共2个。根据边集E={(v1,v2),(v1,v3),(v2,v4),(v3,v4),(v4,v5)}，v3的直接邻接点是v1,v4。所以度数为2。*）5.通解a_n=A*5^n+B*(-6)^n。代入a_0=4，得A+B=4。代入a_1=15，得5A-6B=15。解方程组得A=3,B=1。所以a_n=3*5^n+1*(-6)^n。解析：这是一个二阶常系数线性非齐次递推关系（此处实际上为齐次，因为右侧为0）。首先求解对应的齐次方程a_n=5a_(n-1)-6a_(n-2)。其特征方程为r^2-5r+6=0，解得特征根r1=2,r2=3。因此齐次通解为A*2^n+B*3^n。由于原方程右侧为0，非齐次部分为0，所以通解即齐次通解a_n=A*2^n+B*3^n。然后利用初始条件求解常数A和B。a_0=A*2^0+B*3^0=A+B=4。a_1=A*2^1+B*3^1=2A+3B=15。解这个二元一次方程组：A+B=4，2A+3B=15。乘法消元法：3(A+B)=3*4=12。2A+3B=15。相减得A=3。代入A+B=4，得3+B=4，B=1。所以通解为a_n=3*2^n+1*3^n。（*注：此处计算结果与答案不符。特征方程r^2-5r+6=0，根为r1=2,r2=3。齐次通解为A*2^n+B*3^n。代入a_0=4:A+B=4。代入a_1=15:2A+3B=15。解方程组A=3,B=1。所以a_n=3*2^n+1*3^n。*）五、证明题1.证明：设x∈[a]_R。根据等价类的定义，xRa，即x与a相关。由于R是自反的，所以aRa。又因为R是对称的，所以aRx。再由传递性，因为xRa且aRx，所以xRx。根据R的自反性，x与x相关，即x∈[x]_R。因此，[a]_R是x的等价类，x∈[x]_R。所以[a]_R∩[x]_R≠∅推出[a]_R=[x]_R。由于x是[a]_R中的任意元素，我们得