离散数学考研典型试题及参考答案

离散数学考研典型试题及参考答案考试时间：______分钟总分：______分姓名：______一、单项选择题（每小题2分，共10分。下列每小题给出的四个选项中，只有一项是符合题目要求的。请将正确选项的字母填在题后的括号内。）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}(B){2,4,5,6}(C){1,5,6}(D){2,4}2.命题公式(p∨¬q)→(¬p∧q)是：(A)重言式(B)可满足式但非重言式(C)矛盾式(D)无法判断3.设G=(V,E)是一个无向图，V={v1,v2,v3,v4,v5},E={{v1,v2},{v1,v3},{v2,v4},{v3,v4},{v4,v5}}。则G中的连通分量为：(A)1(B)2(C)3(D)44.一个有限自动机M的状态集Q={q0,q1},输入字母表Σ={0,1},状态转换函数δ定义如下：δ(q0,0)=q0,δ(q0,1)=q1,δ(q1,0)=q1,δ(q1,1)=q0。M接受的语言L(M)是：(A){0,1}(B){ε,00,11}(C){字符串w|w中0和1的个数相同}(D){字符串w|w不以01结尾}5.用数学归纳法证明“对于任意正整数n，1+3+5+...+(2n-1)=n^2”时，第二步归纳假设的内容是：(A)等式1+3+5+...+(2n-1)=n^2对n=k成立(B)等式1+3+5+...+(2n-1)=n^2对n=k+1成立(C)等式1+3+5+...+(2k-1)=k^2对某个正整数k成立(D)等式1+3+5+...+(2k+1)=(k+1)^2对某个正整数k成立二、填空题（每小题3分，共15分。请将答案填在题后的横线上。）6.设函数f:A→B,g:B→C，其中A={1,2},B={a,b,c},C={x,y}。若f(1)=b,f(2)=a,g(b)=y,g(a)=x,则复合函数g◦f的值域是__________。7.关系R={(1,2),(2,3),(3,2),(2,1)}不是__________关系。8.一个具有n个顶点的无向树有__________条边。9.用递推关系an=2an-1+3(n≥2,a1=1)定义的序列{an}的通项公式an=__________。10.哈夫曼编码是一种用于数据压缩的算法，其基本思想是使用较短的编码表示出现频率__________的字符。三、判断题（每小题2分，共10分。请将答案“正确”或“错误”填在题后的括号内。）11.若R是集合A上的等价关系，则对于任意a,b∈A，(a,b)∈R当且仅当(b,a)∈R。()12.任何有限自动机都等价于一个确定有限自动机。()13.若一个图的最小生成树存在，则该图一定有唯一的minimumspanningtree。()14.归纳假设是数学归纳法证明中必须使用的一个步骤。()15.容斥原理可以用来计算至少满足其中一项事件的元素个数。()四、计算题（每小题5分，共10分。）16.计算组合数C(10,6)的值。17.写出命题公式p∧(q∨¬r)∧¬q的主析取范式。五、证明题（每小题7分，共14分。）18.证明：设G是一个无向图，则G是连通图当且仅当G中存在一条包含所有顶点的简单路径。19.使用数学归纳法证明：对于任意正整数n≥1，n^3+(n+1)^3+(n+2)^3是9的倍数。试卷答案一、单项选择题1.(A)2.(C)3.(A)4.(C)5.(A)二、填空题6.{x,y}7.反对称8.n-19.4^n-310.高三、判断题11.正确12.错误13.正确14.正确15.正确四、计算题16.C(10,6)=10!/(6!*4!)=(10*9*8*7)/(4*3*2*1)=21017.p∧(q∨¬r)∧¬q=(p∧¬q∧(q∨¬r))∧¬q(分配律)=(p∧¬q∧q)∨(p∧¬q∧¬r)∧¬q(分配律)=(p∧¬q∧¬r)(p∧¬q∧q)为假)=M1∨M3=p'∧q∧¬r∨p∧q'∧¬r(摩根定律及反身性)=∑(1,3)五、证明题18.证明(必要性)：设G是连通图。任取两个顶点u,v∈V(G)。由于G连通，存在u到v的路径P。P可以扩展为一条包含G中所有顶点的路径，因为对于不在P上的顶点w，由于G连通，u到w存在路径Q，v到w存在路径R，将P、Q、R连接起来即可。这条包含所有顶点的路径显然是简单的（因为P本身是简单路径，且连接不重复顶点）。证明(充分性)：设G中存在一条包含所有顶点的简单路径P。则对于任意两个顶点u,v∈V(G)，都在P上，因此存在u到v的路径（即P本身的一部分）。所以G是连通图。19.证明：记P(n)为“n^3+(n+1)^3+(n+2)^3是9的倍数”。基础步骤(n=1)：P(1):1^3+2^3+3^3=1+8+27=36，36是9的倍数。P(1)为真。归纳步骤：假设P(k)为真，即k^3+(k+1)^3+(k+2)^3是9的倍数。需要证明P(k+1)为真，即(k+1)^3+(k+2)^3+(k+3)^3是9的倍数。(k+1)^3+(k+2)^3+(k+3)^3-[k^3+(k+1)^3+(k+2)^3]=(k^3+3k^2+3k+1)+(k^3+6k^2+12k+8)+(k^3+9k^2+18k+27)-[k^3+(k^3+3k^2+3k+1)+(k^3+6k^2+12k+8)]=3(k^3+3k^2+3k+8)=3(k^3+3k(k+1)+8)=3k(k+1)(k+1)+24=3k(k+1)(k+1)+3*8=9k(k+1)(k+1)/3+9*8/3=3k(k+1)(k+1)+24=9*[k(k+1)(k+1)/3+8/3]由于k(k+1)总是偶数，k(k+1)