《离散数学》典型例题.pdfVIP

《离散数学》典型例题 一、选择题 1. 图 1 哈斯图所示的偏序集为格的是（ ）。 2. 设有无向图如图 2，则（ ）是一条哈密顿回路。 A．gabcdefg B．abcdefg C ．cfabcdeg D．efgabcd 3. 哪个顶点可成为图 3 的割点？（ ） A. a B. b C. c D. d 4. 图 4 中（ ）是欧拉图。 5. 下列（ ）是满 2 元树。 二、填空题 1. 设A={1,2}, B={2,3}, C={ a,b,c} ，则 |( A ∪B) ×C |=______________________________。 2．无向完全图 Kn的边数为 _______________ 。 3. 给定A={1,2,3,4} ，A上的关系 R={1,3,1,4,2,3,2,4,3,4} 满足的性质是 1 _________________________。 4. 设A={ a,b,c} ，F是A 上的二元关系， F={a,a, b,b, c,c} ，则其自反闭包为 r( F)= ______________________________。 5. 设A和B是有穷集合， | A|= m，| B|= n，A到 B有_______多少个不同一对一映射。 三、判断题 1．每个正整数都可以唯一地表示为素数的乘积。（ ） 2．集合 X 上的关系 R如果是自反的、反对称的、传递的则称此关系为相容关系。（ ） 3．一条基本回路一定是简单回路，但一条简单回路不一定是基本回路。（ ） 4．树是不包含回路的连通图，在（ n，m）树中必有 m=n+1 （ ） 5．一个有限群 G，* 的阶 n 一定被它的任一个子群的阶 m所等分。（ ） 四 、综合题 1． 求公式 ( ～P→Q) →(Q→～ P) 的主析取范式和主合取范式。 2. 6 个人一起吃饭，围绕圆桌就餐，有多少种就座方式？如果要从 4种不同的菜系中点足 6道 菜，问有多少种点法？ 3. 一个面包店里有 5 种不同口味的面包， 要挑选 8 个面包，并且至少有 2 个奶油味面包和不 超过 2 个咸味面包。有多少选择方法？ 4. 求解下述递推关系 a =7a -1 -2 n n -12 an ，a0 0, a1 1 5. 求解在集合 {1 ，2，3，4} 上的关系 {(1,2), (2,1), (2,3), (3,4), (4,1)} 的传递闭包。 6. 对偏序集（ {2 ，4，5，10，12，20，25} ，| ）上的整除关系，画出哈斯图并回答下列问题： （1）求极大、极小元素； （2 ）求最大、最小元素； （3 ）找出{2 ，5} 的所有上界，如果存在的话求出最小上界； （3 ）找出{12 ，10} 的所有下界，如果存在的话求出最大下界。 2