离散数学复习题(二).doc

《离散数学复习题(二).doc》由会员分享，可在线阅读，更多相关《离散数学复习题(二).doc（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除离散数学复习题(二)一选择题1设 p: 天下大雨；q: 我乘公共汽车上班。则命题“除非天下大雨，否则我不乘公共汽车上班”的符号化为（ ）。 （A）pq （B）pq（C）p q （D）p q 2命题公式(pq)q的主析取范式为（ ）。 (A) pq (B) (pq)q (C) pq (D) (pq) q3R是A上的等价关系，R与它的闭包满足（ ）。(A) r(R)= s(R)= t(R)=R (B) r(R)R (C) s(R) R (D) t(R) R 4G是有24条边的6度正则图，G中的顶点有（ ）。 (A) 5个 (B) 6个 (C) 7个

2、(D) 8个5集合A=1,2,3,4,5,6,7,8,9上的等于关系R为（ ）。(A) 偏序关系 (B) 全序关系 (C) 线序关系 (D) 以上三个都对6设V1=R,+和V2R+,为两个代数，R和R+ 分别为实数集和正实数集，：RR+ 对xR，有(x)=e x，则映射为(A)仅为单射 (B)仅为满射 (C) 仅为同态映射 (D) 同构映射7无向树T有5片树叶，其余顶点的度均为3，T中有几个3度顶点。 (A) 3个 (B) 4个 (C) 5个 (D) 6个8n阶(n为奇数)无向图G是一个初级回路，则下列说法不正确的是（ ）。(A) G是连通图 (B) G是二部图 (C) G是欧拉图 (D) G

3、是哈密尔顿图 9关于格和布尔代数下面的说法正确的是（ ）。 (A) 有界格一定是有补格 (B) 有补格一定是分配格 (C) 有限格不一定是有界格 (D) 布尔代数是有补格且是分配格10G=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爱唱歌，命题“有的人不爱唱歌”在一

4、阶逻辑(谓词逻辑)中符号化形式为_。3命题公式 p(qr)p 和(pq) q的类型分别为_式和 式。4设A=1,2，B=a,b,c，则可产生_个A到B的函数，其中有_个双射函5IA是集合A上的恒等关系，A上的关系R具有 性当且仅当IAR。6若群G中的二元运算满足交换律，则称G是_群。7G为n(n为偶数)阶简单无向图，则G对应的完全图Kn中各顶点的度为_数，已知G中有k个奇度数顶点，则在G的补图中有_个偶度数顶点。8完全二部图K3,4中每个顶点的度数至多为_，其中的完备匹配M含 条边。9无向连通图G是二部图的一个必要条件是G的阶为 数。106阶无向带权图G中每条边的权值均为 ，则G的最小生成树T

5、中 有条边，T的权W(T)20。三 判断题1A、B为任意的命题公式，若(AB)AB。（ ）2在命题逻辑中，任何命题公式的析取范式都存在但不唯一。（ ）3设A=1,2,3,4，B=a,b,c,d，则不存在从A到B的双射。（ ） 4A上的恒等关系是A上的等价关系，并且是A上的偏序关系。（ ）5是有限群G1到G2的同态映射并且是双射，则G1和G2同构。6在图G中简单回路必初级是回路。（ ） 7设G1,G2,G3,G4都是4阶3条边的无向简单图，则它们之间至少有两个是同构的。（ ）8二部图中的完备匹配一定是完美匹配。（ ）四计算题1对60名员工调查表明，其中25人会C+语言，26人会VB语言，26人会

6、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 是生成元。证明G一定是阿贝尔群(交换群)。3将下面的命题符号化，给出前提和结论，再用构造法证明结论是正确的。“红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四。或者白队不是第一，或者红队第三。已知黄队第二。因此，如果白队第一，则蓝队第四。”【精品文档】第 2 页