离散样卷2.docVIP

样卷二 选择题 1.命题公式的001赋值为 。 A.成真赋值 B.成假赋值 C.都不是 2. 以下各命题中 为真。 A.{b}({{a},a,b} B.{(}(( C.ρ(()=( D. {0}(ρ({0}) 3．设表示“是学生。”，表示“考试不及格。”，表示“要补考。”, 则“考试不及格的学生都要补考。”可翻译成______。 A. B. C. D. 4. 设F={-1,0,1}，运算(是普通乘法，则F,( 。 A. 是群 B. 是半群但不是独异点 C. 不是半群 D.是独异点 5. R为实数集，函数f(x)=x2是R到R的 。 A．双射 B. 单射 C．满射 D .都不是 6. 集合A上的恒等关系IA没有的性质是( ) A.对称性 B.反自反性 C.传递性 D. 反对称性 7. T是无向树，则T不具有的性质是 。 A． T是最小连通图 B. T中每条边均是桥 C．T的边数等于顶点数 D. T是最大无回路图. 8. 设，则关于如下_____定义的*运算不能构成半群。 A. B. C. D. 9.有向图G是哈密顿图, 则该图 ___。 A.是弱连通图但不是单侧连通图 ; B. 是单侧连通但不是强连通图; C. 肯定不是强连通图 ; D.. 一定是强连通图. 10. A上函数的复合运算满足_________。 A.交换律 B. 结合律 C. 幂等律 D. 消去律 填空题 1.在两个变元p、q的命题公式中,的主析取范式是 ; 公式的前束范式为 . 2.公式中, 自由出现 次, 的辖域是 。 3.设 集合, B={(},则 _______________,=_____________________。 4. X={1,2,3,4,5}, X上的等价关系 R={1,2,2,1,4,5,5,4}∪Ix ,则 [2]R=___________,X/R=__________________________. 5.平面图G有9个顶点、10条边，则G有 个面。总的面的次数为 。 6. 设A={1,2,3,4},A上关系R={3,3,1,2,2,4},S={1,3,2,4,4,2}， 则 ______________ , ___ ________。 7.无向完全图共有 边，无向完全二部图共有 边. 8. S={1,2,3,4}, S上的置换，，则 。 。 9．R为整数集，运算*是普通乘法，则群〈R，*〉上单位元是 ，-4的逆元是 。 10．无向半欧拉图至多有（ ）个奇点，无向欧拉图共有（ ）个奇点。 判断题（错的打“×”，对的打“√”；） 1. 一个有5个结点，4条边的无向连通图是树。 　　　　　　 （　 ） 2.　 f，g 是A上的函数，若复合函数是双射，则g一定是满射。 （ ） 3. 命题公式是重言式。 （ ） 4.　循环群一定是交换群。 　　　　　　　　　　 　（ ） 5.　一个关系不是自反的就一定是反自反的。 （ ） 　　　　　　　　　　　 四. 1．一棵树具有2个2度结点，3个3度结点，4个4度结点，其余为叶。试求其共有多少个结点？多少片叶？ 2．已知X={a,b,c},给出X上所有的双射。 3．画一棵权为2，2，3，3，4，4，5 的最优二叉树，并计算出它的树权。 五 1、