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

精品文档，仅供学习与交流，如有侵权请联系网站删除离散数学复习题(二)一选择题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个 (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是哈密尔顿图 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爱唱歌，命题“有的人不爱唱歌”在一阶逻辑(谓词逻辑 )中符号化形式为_。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中 有条边，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人会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将下面的命题符号化，给出前提和结论，再用构造法证明结论是正确的。“红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四。或者白队不是第一，或者红队第三。已知黄队第二。因此，如果白队第一，则蓝队第四。”【精品文档】第 2 页