2026年大一离散数学考试试题及答案

2026年大一离散数学考试试题及答案考试时长：120分钟满分：100分班级：__________姓名：__________学号：__________得分：__________一、单选题（总共10题，每题2分，总分20分）1.在集合论中，集合A包含于集合B的符号表示是______。A.A∪BB.A∩BC.A⊆BD.A⊇B2.下列命题中，属于逻辑联结词“非”的例子是______。A.p∧qB.p∨qC.¬pD.p→q3.在命题逻辑中，命题公式(p∧q)→p的永真性是______。A.假B.真C.依赖p和qD.无法判断4.下列图论概念中，表示图中顶点之间不存在直接边的是______。A.邻接矩阵B.完全图C.空图D.有向图5.在树的结构中，一个非叶顶点的度数至少为______。A.0B.1C.2D.36.下列数制中，基数为2的是______。A.八进制B.十进制C.二进制D.十六进制7.在组合数学中，从n个不同元素中取出k个元素的组合数记作______。A.P(n,k)B.C(n,k)C.A(n,k)D.G(n,k)8.下列算法中，用于对图进行拓扑排序的是______。A.Dijkstra算法B.Floyd-Warshall算法C.拓扑排序D.快速排序9.在关系代数中，表示关系R中所有元组的集合的运算符是______。A.πB.σC.∩D.×10.在形式语言理论中，有限自动机（FA）能够识别的语言属于______。A.递归可枚举语言B.正则语言C.上下文无关语言D.不可计算语言二、填空题（总共10题，每题2分，总分20分）1.集合A={1,2,3}与集合B={2,3,4}的并集是______。2.命题逻辑中，联结词“或”的符号表示是______。3.在命题公式p∧(q∨r)中，优先级最高的联结词是______。4.完全图中n个顶点共有______条边。5.树的叶节点是指______的顶点。6.二进制数1011转换为十进制数是______。7.组合数C(5,2)的值等于______。8.拓扑排序适用于有向无环图（DAG），其基本思想是______。9.关系代数中，选择运算的符号表示是______。10.正则表达式用于描述______。三、判断题（总共10题，每题2分，总分20分）1.任何两个集合的并集仍然是集合。（√）2.命题公式p∨¬p的永真性为假。（×）3.在树中，任意两个顶点之间有且仅有一条路径。（√）4.完全二叉树的叶节点数总是奇数。（×）5.二进制数1001转换为十六进制数是9。（√）6.组合数C(n,k)等于排列数P(n,k)。（×）7.拓扑排序的结果唯一。（×）8.关系代数中的投影运算会改变关系的属性顺序。（×）9.有限自动机只能识别正则语言。（√）10.上下文无关文法（CFG）可以描述所有形式语言。（×）四、简答题（总共4题，每题4分，总分16分）1.简述命题逻辑中联结词“与”的定义及其真值表。2.解释图论中“连通图”的概念，并举例说明。3.描述树的基本性质，并说明为什么树是二分图。4.简述有限自动机（FA）的基本组成及其工作原理。五、应用题（总共4题，每题6分，总分24分）1.已知集合A={1,2,3}，B={2,3,4}，C={3,4,5}，计算(A∩B)∪C，并画出Venn图表示。2.给定命题公式p:“今天下雨”，q:“我带伞”，用自然语言解释命题公式p→q的含义，并判断其永真性。3.画出完全二叉树，其中n=5，标出所有顶点及其度数，并计算该树的边数。4.设计一个有限自动机（FA），用于识别由0和1组成的字符串，其中字符串必须以1结尾。【标准答案及解析】一、单选题1.C解析：集合A包含于集合B表示A的所有元素都在B中，符号为A⊆B。2.C解析：“非”联结词表示命题的否定，符号为¬。3.B解析：(p∧q)→p永真，因为当p为真时，p∧q为真，则p为真；当p为假时，p∧q为假，→仍为真。4.C解析：空图表示图中没有任何边。5.C解析：非叶顶点至少有一条入边和一条出边，度数至少为2。6.C解析：二进制基数为2，其他选项基数分别为8、10、16。7.B解析：组合数表示从n个元素中取k个不考虑顺序的选法，符号为C(n,k)。8.C解析：拓扑排序用于对有向无环图进行线性排序。9.A解析：π表示投影运算，选择关系的某些属性。10.B解析：有限自动机只能识别正则语言。二、填空题1.{1,2,3,4}解析：并集包含A和B的所有元素，不重复。2.∨解析：逻辑“或”的符号表示。3.∧解析：联结词优先级：¬>∧>∨。4.n(n-1)/2解析：完全图每对顶点间都有边。5.度数为1解析：叶节点没有子节点。6.11解析：1011₂=1×8+0×4+1×2+1×1=11₁₀。7.10解析：C(5,2)=5!/(2!×3!)=10。8.按顶点的入度递减顺序删除顶点及其出边解析：拓扑排序的核心思想。9.σ解析：选择运算的符号表示。10.正则语言解析：正则表达式描述正则语言。三、判断题1.√解析：并集是集合的并集，仍为集合。2.×解析：p∨¬p永真，因为p和¬p必有一个为真。3.√解析：树是无环连通图，任意两顶点间路径唯一。4.×解析：完全二叉树叶节点数可能为偶数。5.√解析：1001₂=9₁₆。6.×解析：C(n,k)=n!/[k!(n-k)!]，P(n,k)=n!/(n-k)!.7.×解析：拓扑排序结果可能不唯一，取决于删除顺序。8.×解析：投影运算可以指定属性顺序。9.√解析：有限自动机只能识别正则语言。10.×解析：上下文无关文法不能描述所有形式语言（如递归可枚举语言）。四、简答题1.联结词“与”的定义：p∧q表示p和q同时为真时结果为真，真值表为：|p|q|p∧q||---|---|-------||T|T|T||T|F|F||F|T|F||F|F|F|2.连通图：图中任意两个顶点之间存在路径的图。例如，图G=(V,E)，若对任意u,v∈V，存在u到v的路径，则G为连通图。3.树的基本性质：-无环连通图-n个顶点的树有n-1条边-任意两个顶点间路径唯一树是二分图：树可以按顶点的度数分为叶节点（度1）和非叶节点（度≥2），满足二分图定义。4.有限自动机（FA）组成：-状态集合Q-输入字母表Σ-转移函数δ:Q×Σ→Q-初始状态q₀∈Q-接受状态集合F⊆Q工作原理：FA通过读取输入字符串，根据转移函数在状态间移动，若最终状态在F中，则接受该字符串。五、应用题1.(A∩B)∪C={2,3}∪{3,4,5}={2,3,4,5}Venn图：```A:123234B:34C:45```合并重叠部分得{2,3,4,5}。2.p→q含义：若今天下雨，则我带伞。永真性：永真，因为p为假时→总为真，p为真时q必须为真。3.完全二叉树（n=5）：```1/|\234```度数：1（根）度2（2,3,4），3（无）边数：4=5-1（树性质）。