2026年离散数学测试题及答案

2026年离散数学测试题及答案

一、单项选择题（每题2分，共20分）1.设命题公式G=(p→q)∧(¬q∨r)，则使G为假的真值指派是A.p=1,q=1,r=1B.p=1,q=0,r=0C.p=0,q=1,r=0D.p=1,q=0,r=12.在集合A={1,2,3,4}上，关系R={(x,y)|x+y为偶数}的等价类个数为A.1B.2C.3D.43.下列哪一条不是偏序集的性质A.自反性B.对称性C.反对称性D.传递性4.无向图G有12条边且每个顶点度数为3，则G的顶点数为A.6B.8C.9D.125.设函数f:ℤ→ℤ,f(x)=2x+1，则f是A.满射非单射B.单射非满射C.双射D.既非单射又非满射6.在代数系统⟨ℤ,⟩中，运算ab=a+b+ab，其单位元为A.0B.1C.-1D.不存在7.下列逻辑等价式正确的是A.¬(p∨q)⇔¬p∧¬qB.¬(p∧q)⇔¬p∨qC.p→q⇔q→pD.p∨¬p⇔08.设树T有n个顶点且恰有3个叶子，则T的边数为A.n-1B.n-2C.n-3D.n-49.若群G的阶为素数p，则G的子群个数为A.1B.2C.pD.p+110.命题“所有可满足的公式都是重言式”是A.真B.假C.无法判断D.依赖于语言二、填空题（每题2分，共20分）11.命题公式(p→q)∧(q→¬p)的主合取范式中含________个极大项。12.集合A={a,b,c}的幂集元素个数为________。13.若关系R的关系图中有环，则R一定不满足________性。14.完全二分图K_{3,4}的边数为________。15.设f:A→B，|A|=5,|B|=3，则不同的满射函数共有________种。16.格中若a∧b=a∨b，则a与b的关系是________。17.循环群C_{12}的生成元个数为________。18.具有n个顶点的有向完全图的边数为________。19.设图G的邻接矩阵A满足A^3的(2,3)元为4，则G中从顶点2到3长度为3的通路有________条。20.设命题p,q的真值分别为1,0，则(p↑q)↓(p↓q)的真值为________。（↑表示与非，↓表示或非）三、判断题（每题2分，共20分）21.空关系在任意非空集上都是等价关系。22.若图G的色数为2，则G必为二分图。23.任意有限格都必有最大元和最小元。24.命题公式(p∨¬p)→q是重言式。25.若函数f有左逆，则f必为满射。26.群中任意元的阶都整除群的阶。27.有向图存在欧拉回路当且仅当强连通且每个顶点入度等于出度。28.集合上的全序关系一定是良序。29.若R是A上的偏序，则R的逆关系也是偏序。30.树中任意两顶点间恰有一条简单通路。四、简答题（每题5分，共20分）31.叙述并证明集合A上等价关系与A的划分之间的一一对应。32.给出哈密顿图的必要条件和充分条件各一条，并说明其区别。33.设⟨L,∧,∨⟩是分配格，证明对任意a,b,c∈L，有a∧(b∨c)=(a∧b)∨(a∧c)。34.说明命题逻辑中“可满足”与“有效”的区别，并举例。五、讨论题（每题5分，共20分）35.讨论在有限域上构造一个阶为16的有限域的思路，需涉及多项式不可约性的作用。36.对比Prim算法与Kruskal算法在稠密图与稀疏图下的时间表现，并给出适用场景。37.群同态基本定理指出ker(f)◁G，讨论其在判定两个群是否同构时的实际应用价值。38.命题逻辑与一阶逻辑在表达“每个数都有素因子”时的差异，说明为何前者无法直接表达。答案与解析一、1.B2.B3.B4.B5.B6.A7.A8.A9.B10.B二、11.212.813.反自反14.1215.15016.a=b17.418.n(n-1)19.420.0三、21.×22.√23.√24.×25.×26.√27.√28.×29.√30.√四、31.对任意等价关系R，其商集A/R构成划分；反之给定划分π，定义xRy当且仅当x,y同属π的某块，则R为等价关系。两映射互逆，故为双射。32.必要条件：若图G为哈密顿图，则对任意非空真子集S⊂V，有ω(G-S)≤|S|。充分条件：Ore定理——若对任意不相邻顶点u,v有deg(u)+deg(v)≥n，则G为哈密顿图。前者用于否定，后者用于肯定。33.分配格定义即满足a∧(b∨c)=(a∧b)∨(a∧c)，无需再证；若题目要求验证，可用真值表或格图逐点检验。34.“可满足”指存在至少一个解释使其为真，如p∨q；“有效”指所有解释下为真，如p∨¬p。前者不要求普遍真，后者要求普遍真。五、35.先取F=ℤ_2，找四次不可约多项式f(x)∈F[x]，则F[x]/⟨f(x)⟩为含16元域，其乘法群为15阶循环群，可用本原元生成。36.Prim用邻接矩阵实现O(V^2)，稠密图占优；Kruskal用并查集O(ElogE)，稀疏图占优。稠密图选Prim，稀疏图选Kruskal。3