离散数学样卷参考解析.doc

参考答案 试卷一 一、选择填空 1.C 2.A 3.D 4.D 5.A 6.A 7.B 8.C 9.D 10.B 二、填空 1.主合取范式. 前束范式或 2. n-k,9 3.{Φ,{1}，{2}，{1，2}}，={〈1,a〉,1,b,2,a,2,b} 4. [b]R ={1,2,3}, X/R={{1,2,3},{4},{5}}. 5． 。 6.{ 2,1, 4,2,1,1,3,3,2,2}，{1,4,2,2}。 7.15，12. 8. =(132) =(123) 9．0, 45 10．2,0 三 1.× 2.√ 3. √ 4.× 5.× 四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。试求其共有多少个结点？多少片叶？ 解: 设该树其有x片叶,则顶点数为x+7, 根据树的性质知,该树有x+6边,由握手定理有: 3*2+2*3+2*4+x*1=2(x+6), 得x=8 故该树共有15个结点,8 片叶 . 2.已知X={a,b,c},给出X上的所有等价关系。 解:X的划分其有五种: S1={{a,b,c}}, S2={{a,b},{c}}, S3={{a,c},{b}}, S4={{a},{b,c}},S5={{a},{b},{c}}, 因为X上划分与等价关系一一对应,故x上共有五个等价关系，它们是： R1＝{a,b,b,a,a,cc,a,b,c,c,b} R2＝{a,b,b,a}, R3＝{a,cc,a} R4＝{b,c,c,b}, R5＝ 3.．画一棵权为2，3，3，4，5，6，7，8 的最优二叉树，并计算出它的树权。 解:图略,W(T)=106 五、 1、已知偏序集〈X,R〉,其中X={a,b,c,d,e}, Y={d,e}, R的关系矩阵为 求：(1).用集合的列举法写出R (2).画出R的哈斯图； (3).找出X的极大元、极小元、最大 元、最小元； (4).找出Y的上界、下界、最小上界、最大下界。 解:(1). R的关系矩阵R={a,c,b,c,d,a, 〈d,b,d,cd,e,e,a,e,b,e,c}, (2).略 (3)．X的极大元c、极小元d、最大元c、最小元d； (4). Y的上界e,a,b,c、下界d、最小上界e、 最大下界d。 2．已知有向图G=V,E,其中v={a,b,c,d}，E={a,b,a,d,b,a, b,b,b,c,b,d,c,d,d,a,d,b} (1).求出各点的入度序列、出度序列 (2).判定图G是否为欧拉图？，是否哈密顿图？并说明理由。 (3).写出G的邻接矩阵； (4).找出所有长度等于3的路的条数. 解:1. 各点的入度序列:2 ,3,1,3 各点的出度序列:2 ,4,1,2 2. 不是欧拉图,是哈密顿图 3. 4. , 所有长度等于3的路共有59条 六、证明题 1．构造推理证明，前题 ， 结论 证明:(1) 附加前题; (2) T(1) EI规则; (3) P; (4) T(3) UI规则; (5) T(2)(4)假言推理规则; (6) P; (7) T(6) UI规则; (8) T(5)(7)析取三段论. (9) T(8) EG规则. 2．在实数集R上定义二元运算 ?：，其中的其它运算符均为R上的普通运算，证明R，?是可交换独异点。 证明: 按下列4步进行证明 (1)*是二元运算, R，*是代数系统; (2) *满足结合律 , R，*是半群; (3) 0是单位元, R，*是独异点; (4)*满足交换律 试卷二 一、选择填空 1.A 2.D 3.C 4.D 5.D 6.B 7.C 8.B 9.D 10.B 二、填空 1.主析取范式. 前束范式 2. 2, 3.{Φ,{Φ}}， ={〈1,1〉,1,2,2,1,2,2} 4. [b]R ={1,2}, X/R={{1,2},{3},{4,5}}. 5． 3, 20 6.{ 1,2,2,1, 4,2,2,4,3,3}， {4,4,2,2}。 7.