您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 薪酬管理 > 离散数学复习题(二)
离散数学复习题(二)一.选择题1.设p:天下大雨;q:我乘公共汽车上班。则命题“除非天下大雨,否则我不乘公共汽车上班”的符号化为()。(A)┐p→q(B)┐p→┐q(C)┐p←→┐q(D)p←→q2.命题公式(p→q)∧┐q的主析取范式为()。(A)┐p∧q(B)(┐p∧q)∨q(C)┐p∧┐q(D)(┐p∧┐q)∨q3.R是A上的等价关系,R与它的闭包满足()。(A)r(R)=s(R)=t(R)=R(B)r(R)≠R(C)s(R)≠R(D)t(R)≠R4.G是有24条边的6度正则图,G中的顶点有()。(A)5个(B)6个(C)7个(D)8个5.集合A={1,2,3,4,5,6,7,8,9}上的等于关系R为()。(A)偏序关系(B)全序关系(C)线序关系(D)以上三个都对6.设V1=<R,+>和V2<R+,·>为两个代数,R和R+分别为实数集和正实数集,φ:R→R+对x∈R,有φ(x)=ex,则映射φ为(A)仅为单射(B)仅为满射(C)仅为同态映射(D)同构映射7.无向树T有5片树叶,其余顶点的度均为3,T中有几个3度顶点。(A)3个(B)4个(C)5个(D)6个8.n阶(n为奇数)无向图G是一个初级回路,则下列说法不正确的是()。(A)G是连通图(B)G是二部图(C)G是欧拉图(D)G是哈密尔顿图9.关于格和布尔代数下面的说法正确的是()。(A)有界格一定是有补格(B)有补格一定是分配格(C)有限格不一定是有界格(D)布尔代数是有补格且是分配格10.G=<V1,V2,E>为二部图,|V1|<|V1|,已知M是V1到V2的匹配且V1中的点均为M饱和点,则M为()。(A)不是极大匹配(B)不是最大匹配(C)是完备匹配(D)是完美匹配二.填空题1.设p:星期六有课,q:天下雨,r:我去体育场看足球赛,则命题“如果星期六没课并且天不下雨,我就去体育场看足球赛”的符号化形式为______________。2.设F(x):x是人,G(x):x爱唱歌,命题“有的人不爱唱歌”在一阶逻辑(谓词逻辑)中符号化形式为_______________。3.命题公式┐p∧(q∨r)→┐p和┐(p→q)∧q的类型分别为________式和式。4.设A={1,2},B={a,b,c},则可产生_______个A到B的函数,其中有______个双射函5.IA是集合A上的恒等关系,A上的关系R具有性当且仅当IAR。6.若群G中的二元运算满足交换律,则称G是______群。7.G为n(n为偶数)阶简单无向图,则G对应的完全图Kn中各顶点的度为_____数,已知G中有k个奇度数顶点,则在G的补图G中有______个偶度数顶点。8.完全二部图K3,4中每个顶点的度数至多为______,其中的完备匹配M含条边。9.无向连通图G是二部图的一个必要条件是G的阶为数。10.6阶无向带权图G中每条边的权值均为,则G的最小生成树T中有条边,T的权W(T)=20。三.判断题1.A、B为任意的命题公式,若┐(A∨B)=┐A∨┐B。()2.在命题逻辑中,任何命题公式的析取范式都存在但不唯一。()3.设A={1,2,3,4},B={a,b,c,d},则不存在从A到B的双射。()4.A上的恒等关系是A上的等价关系,并且是A上的偏序关系。()5.Φ是有限群G1到G2的同态映射并且是双射,则G1和G2同构。6.在图G中简单回路必初级是回路。()7.设G1,G2,G3,G4都是4阶3条边的无向简单图,则它们之间至少有两个是同构的。()8.二部图中的完备匹配一定是完美匹配。()四.计算题1.对60名员工调查表明,其中25人会C++语言,26人会VB语言,26人会VF语言,9人会C++语言学和VF语言,11人会C++语言和VB语言,8人会VB语言和VF语言,还有8人三种语言都不会。求:(1)这三种语言全会的有几人?只会C++语言的有几人,只会VB语言的有几人?只会VF语言的有几人?(2)画出相应的文氏图。2.用Huffman算法对求一棵带权为1,2,4,5,6的最优2元树T,并求:(1)T的树叶顶点、2度顶点、3度顶点、4度顶点各有几个?(2)T的权W(T)(3)T的树高H五.证明题1.证明:如果无向连通图中G中有割边,G必定不是欧拉图。2.设G=a是循环群,a是生成元。证明G一定是阿贝尔群(交换群)。3.将下面的命题符号化,给出前提和结论,再用构造法证明结论是正确的。“红、黄、蓝、白四队参加足球联赛。如果红队第三,则当黄队第二时,蓝队第四。或者白队不是第一,或者红队第三。已知黄队第二。因此,如果白队第一,则蓝队第四。”
本文标题:离散数学复习题(二)
链接地址:https://www.777doc.com/doc-5046839 .html