离散数学试题A

第1页共4页_______________学院__________专业________________班级姓名：___________学号：________________座号：___密封线内不要答题———————————密———————————————封———————————————线————————————_______________学院__________专业________________班级姓名：___________学号：________________座号：___密封线内不要答题———————————密———————————————封———————————————线————————————一、单项选择题（每小题2分，共40分）1.无向树T中有3个3度,2个2度顶点,其余顶点都是树叶，T有几片树叶。（）A.8B.6C.4D.52.设A={a,b,c}，则下列哪个是集合A的划分。（）A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},{c}}D.{a,{b,c}}3.设集合X={0,1,2,3}R是X上的二元关系，R={0,0,0,2,1,0,1,1,2,3,3,2,3,3,}，则哪个是R的关系矩阵MR。（）A．1100100000110101B.1000001111000101C.0111101001011000D.01011000110001114.从下列描述中，指出不正确的表述。（）A.P({a,{b,c}})={φ,{a},{{b,c}},{a,{b,c}}}B.P({φ})={φ,{φ}}C.P(φ)={φ}D.P({a,{b,c}})={{φ},{a},{{b,c}},{a,{b,c}}}5.从下列图中找出欧拉图。（）6.令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为什么逻辑表达式。（）A.(x)(F(x)∧(y)(G(y)∧H(x,y)))B.(x)((x)F(x)→(G(y)→H(x,y)))C.(x)(F(x)→(y)(G(y)∧H(x,y)))D.(x)(F(x)→(y)(G(y)→H(x,y))7.在个体域D={a,b}中，指出与公式(x)A(x)等价又不含量词的公式。（）A.A(a)∧A(b)B.A(a)→A(b)C.A(a)∨A(b)D.A(b)→A(a)8.指出下列是命题的句子。（）A.水开了吗?B.x1.5C.再过9000年，地球上就没水了。D.我没讲真话。9.给定算式:(((a＋(b＊c))＊d－e)÷(f＋g))－((h＊i)＊j)找出与此算式对应的波兰符号表示式。（）A．－＊＊a＋bc＋def－g＊hij＊＊B.abc＊＋d＊e－fg＋÷hi＊j＊－C．－÷－＊＋a＊bcde＋fg＊＊hijD.ab＋c＊de＋＊fgh＊－＋ij＊－10.设N是自然数集，函数f:N→N×N.f(n)＝﹤n,n＋1﹥,f({5})是什么。（）A．满射函数B．单射函数C．{5,6}D．双射函数11.已知(p→q)←→r的主析取范式是m1∨m3∨m4∨m7，指出与其对应的主合取范式。A．m1∨m2∨m5∨m7B．M0∧M2∧M5∧M6（）C．m0∧m3∧m5∧m6D．M1∨M3∨M5∨M612.设T(x)：x具有性质T，S(y)：y具有性质S。命题“若存在x具有性质T，则所有的y都没有性质S“的符号化形式是什么。（）A.x(T(x)→S(x))B.x(T(x)∧S(x))C.xT(x)→yS(y)D.xT(x)→yS(y)13.判断下列各非负整数列哪个不是可图化的。（）A.(5,5,4,4,2,1)B.(4,4,2,1,3)C.(5,4,3,2,2)D.(3,3,1,1)14.设Z,N分别为整数和自然数集，函数g:Z→N,g(x)＝|x|,g是什么函数。（）A．满射非单射B．双射函数C．单射非满射D．以上答案都不对得分第2页共4页_______________学院__________专业________________班级姓名：___________学号：________________座号：___密封线内不要答题———————————密———————————————封———————————————线————————————15.给定下列各图，判断哪些为简单图。（）G1=V1,E1,其中,V1={a,b,c,d,e},E1={(a,b),(b,c),(c,d),(a,e)}G2=V2,E2,其中,V2=V1,E2={(a,b),(b,e),(e,b),(a,e),(d,e)}D3=V3,E3,其中,V3=V1,E3={a,b,b,c,c,a,a,d,d,a,d,e}D4=V4,E4,其中,V4=V1,E4={a,b,a,b,b,c,d,e,c,d}A.G1,D4B.G1,D3C.G2,D3,D4D.G2,D416.下列哪个不是平面图。（）17.设A={a,b,c}，B={1,2,3}，以下哪一个关系是从A到B的双射函数？（）A.f={a,2,b,2,c,1}B.f={a,3,b,1,c,2}C.f={a,1,b,2,c,3,a,3}D.f={a,1,b,2}18.给定命题公式如右：p∨（q∧┐r），指出公式的成真赋值。（）A.无B.全体赋值C.000，100，101，111D.010，11019.设S={ø，{1}，{1，2}}，则P（S）有几个元素。（）A.3B.6C.7D.820.下述哪一个不是命题。（）A.离散数学是计算机系的一门必修课。B.不存在最大偶数。C.若我有空，我就看书。D.请勿随地叶痰！二、填空题（每空2分，共20分）1.设p:天下雨，q:天刮风，r:我去书店，则命题“如果天不下雨并且不刮风，我就去书店”的符号化形式为。2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为。3.设A={a，b}，则A上共有个不同的二元关系。4.设A={1,2},B={2,3},C={a,b,c}，则(A∪B)×C=。5.无环有向图的关联矩阵的所有元素之和为6.设G是完全二叉树，G有15个点，其中8个叶子，则G的总度数为__________。7.设}4321{，，，A，AAR，},|,{RbababaR，，则domR=。8.设简单图G所有结点的度之和为12，则G一定有条边。9.下图中结点V6的度数为。10.(p∧q)→r的主合取范式为。三、计算与应用题（6小题，共25分）1.设A,R为一个偏序集，其中，A={1，2，3，4，6，9，24，54},R是A上的整除关系。(1).画出A,R的哈斯图；（1分）得分得分V2V6V1V5V4V3第3页共4页v1v3v4v2v5v1v3v4v2v5_______________学院__________专业________________班级姓名：___________学号：________________座号：___密封线内不要答题———————————密———————————————封———————————————线————————————(2).求R关于A的极大元；（2分）(3).求B={4,6,9}的最小上界和最大下界。(2分)2．有向图D如下图所示，写出D的邻接矩阵（2分）。3．设7个字母在通信中出现的频率如下:a:30%,b:20%,c:15%,d:10%,e:15%,f:5%,g:5%.(1).编一个最佳2元前缀码。(3分)(2).在这个前缀码中,a,b,c,d,e,f,g的码长分别是多少?(1分)(3).传输10000个按上述比例出现的字母需要多少个二进制数字?(2分)4．设A={a,b,c,d,},R=IA∪{a,b,b,a,c,d,d,c,}是A上的等价关系，求商集A/R及各元素的等价类。（4分）5．求公式p→((q∧r)∧(p∨(q∧r)))的主析取范式（4分）得分第4页共4页6．判断推理是否正确（4分）设y＝2|x|,x为实数，推理如下：若y在x＝0可导，则y在x＝0连续。y在x＝0连续。所以，y在x＝0可导。四、证明题（2小题，共15分）1．设f:A→B,g:B→C是两个函数，证明：若f⊙g是单射且f是满射，则g是单射。（7分）2.在自然推理系统P中构造下面推理的证明（8分）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。