离散数学样卷参考答案.doc

《离散数学样卷参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、参考答案试卷一一、选择填空1.C2.A3.D4.D5.A6.A7.B8.C9.D10.B二、填空1.主合取范式.前束范式或2.n-k,93.{Φ,{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,4510．2,0三1.×2.√3.√4.×5.×四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。试求其共有多少个结点？多少

2、片叶？解:设该树其有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＝{,,,,}R2＝{,},R3＝{

3、a>}R4＝{,},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={,,,〈d,b>,,,,},(2).略(3)．X的极大元c、极小元d、最大元c、最小元d；(4)

4、.Y的上界e,a,b,c、下界d、最小上界e、最大下界d。2．已知有向图G=,其中v={a,b,c,d}，E={,,,,,,,,}(1).求出各点的入度序列、出度序列(2).判定图G是否为欧拉图？，是否哈密顿图？并说明理由。(3).写出G的邻接矩阵；(4).找出所有长度等于3的路的条数.解:1.各点的入度序列:2,3,1,3各点的出度序列:2,4,1,22.不是欧拉图,是哈密顿图3.4.,所有长度等于3的路共有59条六、证明题1．构造推理证明，前题，结论证明:(1)附加前题;(2)T(1)EI规

5、则;(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上的普通运算，证明是可交换独异点。证明:按下列4步进行证明(1)*是二元运算,是代数系统;(2)*满足结合律,是半群;(3)0是单位元,是独异点;(4)*满足交换律试卷二一、选择填空1.A2.D3.C4.D5.D6.B7.C8.B9.D10.B二、填空1.主析取范式.前束范式2.2,3.{Φ,{Φ}}，={〈1,1〉,<1,2>,<2,1>

6、,<2,2>}4.[b]R={1,2},X/R={{1,2},{3},{4,5}}.5．3,206.{<1,2>,<2,1>,<4,2>,<2,4>,<3,3>}，{<4,4>,<2,2>}。7.10，12.8.=(1243)=(234)9．1,-1/410．2,0三1.√2.√3.√4.√5.×四.1．一棵树具有2个2度结点，3个3度结点，4个4度结点，其余为叶。试求其共有多少个结点？多少片叶？解:设该树其有x片叶,则顶点数为x+9,根据树的性质知,该树有x+8条边,由握手定理有:2*2+3*3+4*4+x*1=2(x+8),得x=13故该树共有22个结点,13片叶.2.．已知X={a,b,

7、c},给出X上所有的双射。答X上共有六个双射:f1＝{,,},f2＝{,,}f3＝{,,},f4＝{,,}f5＝{,,},f6＝{,,}3.．画一棵权为2，3，3，4，5，6，7，8的最优二叉树，并计算出它的树权。解:图