1 V1 V2 2 V6 4 6 V3 8 V4 V5
2、解：(1)用Huffman算法求以频率(乘以100)为权的最优2元树. 将权按小到大顺序排列： wg=5,wf=5,we=10,wd=10,wc=15,wb=20,wa=35.得到如下最优2元树：
0
40 0 20 0 10 0 wg=5
1
wf=5
1 we=10
1 wb=20
100
1
60 0 25 0
wd=10
1 wc=15
1 wa=35
(2)如上图所示，得到各字母的前缀码：a:11,b:01,c:101,d:100,e:001,f:0001,g:0000 总权重W(T)＝255
(3) W(T)＝255说明传输100个按给定比例出现的7个字母需要255个二进制数位，传输10000个需要25500个二进制数位；如果用等长的3个二进制传输一个字母，传输10000个需要30000个二进制数位。因此可以节约： 30000-25500=4500个二进制位 3.解：(1)写出R的关系矩阵MR ?0000? ?1010? ?M?? R?1001? ??0100??
(2)求r(R)的关系矩阵 ?0000??1000??1000? ?1010??0100??1110? ???????Mr(R)?MR?E?? ?1001??0010??1011? ??????010000010101??????
(3)求s(R)的关系矩阵 ?0000??0110??0110? ?1010??0001??1011?' M????????M?M??s(R)RR
?1001??0100??????0100??0041 10??1101????0110?
(4)求t(R)的关系矩阵 234Mt(R)?MR?MR?MR?MR ?0000??0000??0 ????? 2?1010??1010??1M?? R?1001??1001??0 ????? ?0100??0100??1 ?0000??0000??0 ?1001??1010??03 M???????R ?0100??1001??1?????
10100100?????1
?0000??0000??0
?0100??1010??1 4????? MR???1010??1001??1
????? 10010100?????0
234 Mt(R)?MR?MR?MR?MR
?0000??0000??00 ???1001??011010 ???????? ?1001??0100??10???? ?01001010????10 ? ?0000? ??1111 ??? ?1111? ??1111? ?
000?001??100??010?000?100??010??001?000?010??001??100?00??0?100????10??1??01??0000?010??001??100?四、证明题（5分+5分+5分，共15分）
1、证：(1)自反性：对于任意的?x,y??A
xy?yx???x,y?,?x,y???R
(2)对称性：对于任意的??x,y?,?u,v???R
?xv?yu?uy?vx???u,v?,?x,y???R
(3)传递性：对于任意的??x,y?,?u,v???R???u,v?,?r,s???R
?xv?yu?us?vr?x/y?u/v?u/v?r/s?x/y?r/s?xs?yr???x,y?,?r,s???R
2、证：用反证法，假设不存在顶点度数大于等于3，则?v?V(G),均有d(v)?2，由握手定理有：
2m?2(n?1)?2n?2??d(vi)?2n，矛盾！所以G中存在顶点v：d(v)≥3
42
3、（此题有多种证明方法） 证：首先由a?H??a???，任取am,al?H,则
am(al)?1?ama?l?am?l?H，根据子群判断定理二可知H?G
五、应用题（6分）
(1)p: 王小红努力学习
q: 王小红取得好成绩 r: 王小红贪玩 s: 按时完成作业
(2)前提：p?q,(r??s)??q 结论：p?s
(3)证明：使用附加前提条件引入证明方法 ①p 附加前提条件 ②p?q 前提条件 ③q ①②假言推理 ④(r??s)??q 前提条件 ⑤?(r??s) ③④拒取 ⑥?r?s ⑤置换 ⑦s ⑥化简
华南农业大学期末考试试卷（ A 卷）
2008 学年第二学期 考试科目： 离散结构
考试类型：（闭卷） 考试时间： 120 分钟
学号 姓名 年级专业
题号 得分 评阅人 一 二 三 四 五 总分 林旭东 口 朱梅阶 口 2．试卷共五大题，满分100分
3．全部答案写在答题纸上，试卷纸上答题无效 ．．．．．．．．
注意事项：1．考试时间120分钟，闭卷考试
一、填空（每空2分，共30分）
1、__________1____________； 2、___________5____________； 3、___?x?y(F(x)?（y,x）)； 4、___________1____________； 5、__________1____________； 6、___________9____________； 7、__________25____________； 8、__________45_____________；
43
9、__________103__________； 10、?x?y?z((P(x,z)?Q(x,y)))； 11、__________2rs____________； 12、__________5____________； 13、_________a_____________； 14、__________否____________； 15、_________是_____________。
二、选择题（每题2分，共30分）
1、 6、 11、
三、计算题（每题6分，共18分）
1、
A A C 2、 7、 12、 C C C 3、 8、 13、 C C B 4、 9、 14、 B B A 5、 10、 15、 D D D
p=1 邻接矩阵
通路长度小于或等于6的条数为13 2、6阶所有非同构的无向树有6棵
44
3关系矩阵
关系图：
传递闭包：t(R)=R
四、证明题（每题6分，共18分）
1、证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。
2、由于T为非平凡树，则n>1，且任何顶点的度数都大于等于1；设T中m条边，k片树叶(顶点度数为1)，则其余n-k个分支点的度数均大于等于2，由握手定理与树的性质(m=n-1)有：
2m?2(n?1)?2n?2??d(vi)?k?2(n?k)，
显然k≥2，这说明T至少有两片树叶。
3、首先证明R是对称的
?a,b??R==〉?b,b??R（因为R自反的）==〉?b,a??R （R是循环的） 即?a,b??R??b,b??R??b,a??R 再证R是传递的
若?a,b??R,?b,c??R
45