安徽理工大学 09-10离散数学A卷

2009～2010学年 第 2学期 试 标准分 专业班级： 09级计算机、信息安全各专业 专业班级： 学号： 姓名： [该项由出卷人填写] 得 分 一 15 二 15 三 46 四 24 五 六 七 八 九 十 总 分 100 卷 课程名称：《离散数学》 考试形式：(闭)卷 试卷： A 2.(5分) 画出一棵带权为2,2,2,3,3,4,5,8的最优2叉树T，并计算它的权W（t）. 3.(10分) 设R是A={1,2,3,4,5,6}上的关系，R={<1,1>,<1,3>,<1,6>,<2,2>,<2,5>,<3,1>, <3,3>,<3,6>,<4,4>,<5,2>,<5,5>,<6,1>,<6,3>,<6,6>}, 1) 画出R的关系图； 2) R是否是等价关系，若是，写出R的所有等价类； 3) 写出A关于R的商集A∕R. 4.(8分) 设群G =<Ｚ6,+6>，其中Ｚ6={0,1,2,3,4,5},\6\为模6加法， 1)试写出G的每个子群； 2) 2阶子群相应的左陪集； 3)求元素2的周期。 (后附空白纸作为答题卡，答案一律写在答题卡上，写在试卷上无效，大题务必标清题号) 一、单选题（5×3分=15分） 1. 设集合A={ a,Φ,{ a }}，则下列结论错误的是（ ）. 2. 设集合A中有3个元素，则在A上可有（ ）种不同的二元关系. A. 3 B. 8 C. 9 D. 512 3. 设函数f：R→R，g：R→R（R为实数集)，且f(x)?2x?1,g(x)?x2，则复合 函数 g ? f是（）. 装 订 线 A. 单射 B. 满射 C. 双射 D. 既不是单射，也不是满射 4. 谓词公式?x(P(x)??yR(y))?Q(x)中变元x是（ ）. A. 自由变元 B. 约束变元 C.既是自由变元又是约束变元 D.都不是 5. 下列所给图形既不是欧拉图又不是哈密顿图的是（ ）. A. B. C. D. 二、填空题 (5×3分=15分) 1. A={a,b,c,d},其偏序关系R的哈斯图为 ，则用列举法写出R =__________ ________. 2. 设G1，G2，G3，G4都是4阶3条边的无向简单图，则这四个图中至少有___个是同构的. 3. 一组学生，用两两扳手腕子比赛来测定臂力的大小，则单位元是____________,零元是 _____________. 4. 设命题变元P：天下雨，Q：我打车上学，则“只有天下雨，我才打车上学”符号化为 ____________. 5. 设二元关系R ={< x ,y>|x ,y∈N,x + y = 100},则R具有的性质有___________________. 三、 解答题 （46分） 1.(10分) 求公式(P→Q)∧(Q→R)的主析取范式和主合取范式（用二进制的编码表示给 出），并给出公式的成真赋值。 A. { a}∈A B. { a}?A C. {Φ}?A D. {{ a}}?A 5. (8分) 设A={a,b,c},关系R={,,,},求出R的自反闭包r(R)、对称 闭包s(R)、传递闭包t(R). 6.(5分) 右图表示五个城市A,B,C,D,E及对应 两城市间公路长度，试给出一个最优化的设 计方案，使得各城市间都能够有公路通过。 四、证明题（24分） 1.(6分) 设A,B为任意集合，证明:(A-B)∪(B-A)=(A∪B)-(A∩B). 2.(6分) 设R和S为A上的二元关系，证明(R –S )= R -S . 3.(6分) 设是一个群,u∈G, 在G中定义运算“ ? ”为： ?a,b?G,a?b?a*u?1-1 -1-1 *b, 证明：也是群。 4.(6分) 右图是否为平面图，给出证明。 第 ( 1 ) 页 共 ( 1 ) 页

专业班级： 专业班级： 学号： 姓名： [该项由出卷人填写] 装 订 线 2009～2010学年 第 2学期 试 卷 课程名称：《离散数学》 考试形式：(闭)卷 试卷： A 第 ( 2 ) 页 共 ( 1 ) 页