离散题库完整版.doc

一 1、从集合分类的角度看,命题公式可分为(???) ? A.永真式、矛盾式?????? ?? 　　B. 永真式、可满足式、矛盾式? C. 可满足式、矛盾式??? 　????D. 永真式、可满足式? 2、设B不含有，等值于?(???) A.? ?B. C.? ?D. 3、设S,T,M是集合，下列结论正确的是（???? ） A．如果S∪T=S∪M，则T=M B．如果S-T=Φ，则S=T C． D． 4、设R是集合A上的偏序关系，则R不一定是(???) A.自反的?? ??B. 对称的? ?C. 反对称的?? ???D. 传递的 5 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。 A. B. C. ?D. 6、设二元运算，则它满足(???) A.交换律?? ??B. 吸收律? ?C. 幂等律?? ???D. 消去律 7、设A={1,2},则群的单位元和零元是(???) A. 与A??????B.?? A?与 ?C. {1}与?? ?D. {1}与A? 8、下列编码是前缀码的是(?? ?). A.{1,11,101} ?B.{1,001,0011} C.?{1,01,001,000}??D.{0,00,000} 9、下图中不是二部图的是（???? ） A． 三角形 B．四边形 C．六四边形 D．八边形 10、下图所示的二叉树中序遍历的结果是（???? ） A．abcde B．edcba C．bdeca D．badce 二、填空题 1、含3个命题变项的命题公式的主合取范式为, 则它的主析取范式为 。() 2、公式中，约束出现 次。 3、从公式分类的角度看，是 式。 4、A={1,2,3}的幂集有 个元素。 5、集合A={{},{},{}},那么的广义交=?????????????????????。 6、三年级一班有40名学生，会唱歌的15人，会跳舞的10人，会唱歌且会跳舞的5人，则不会唱歌且不会跳舞的 人。 7、〈，〉模4加群， 则3是 阶元， 8、已知n阶无向简单图G有m条边，则G的补图有 条边。 9、一个有向图是强连通的充分必要条件是 。 7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m， 则m= . 10、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。 1、已知命题公式， 构造真值表。(2) 指出公示的类型。 2、={1,2,1,3,2,3}, ={2,2,2,3,3,4},求： （1） (2) 　　（3） 　(4) （5） 3、设A,R为一个偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除关系。 （1）画R出的哈斯图； （2）求A的极大元（写一个即可）和极小元； （3）求B={4,6}的上确界和下确界。 4、画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权。 1、前提： 结论: 2、设S为有理数集合，定义S上的二元运算：，。 (1)求； (2)求单位元； (3)证明S, 是群。 二 一、选择题 1、使命题公式为假的赋值是?(???) ???A.10?????????B.01 ? ? ?C. 00???????????D.11 2、令A(x)：x是学生，B(x)：x是女生，则命题“并不是所有学生都是女生”可符号化为（???? ） A. B． C. D． 3、设B不含有x，等值于?(???) A.? ?B. C.? ?D. 4、 设A={1,2}，则A的幂集的幂集P(P(A))含有（???? ）个元素。 A．2 B．4 C．8 D．16 5、集合A={a，b，c，d}，则对?A 的元素进行分类正确的是（ ） A. {,{a,b},{c,d}} ???B. {{a,b,c},{c,d}} C. {{a,b,d},{a,c}}? ???? ???D. {{a,b,c,d}} 6、设A={1,2},则群得单位元和零元是