(2)利用所求最优2元树找出每个字母的前缀码．
(3)求传输10000个按上述比例出现的字母需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?节约多少个二进制位？
3、设集合
X?{a,b,c,d}，X上的关系R如图所示，试求：
a b c d
（1）写出关系R的关系矩阵MR
（2）求关系R的自反闭包r(R)的关系矩阵Mr(R), (r(R)?（3）求关系R的对称闭包s(R)的关系矩阵Ms(R), (s(R)?（4）求关系R的传递闭包t(R)的关系矩阵Mt(R), (t(R)?R?R0?R?IX) R?R?1)
R?R2?R3?R4)
四、证明题（5分+5分+5分，共15分） 1
、
设
A?Z??Z?,在A上定义二元关系R如下：
??x,y?,?u,v???R?xv?yu,其中x,y,u,v?Z?，证明：R是A上的等价关系。
2、设n阶m条边的无向图G中，m=n+1，证明G中存在顶点v：d(v)≥3。
3、设G为群，a?G，令H
五、应用题（共6分）
1. 如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。
(1) 将命题中的4个简单命题依次符号化为p,q,r,s； (2) 将命题符号化，即将命题的前提和结论符号化； (3) 在自然推理系统P中构造命题的推理证明。 2008-2-A
?{ak|k?Z}，证明：H是G的子群。
11
一、填空（每空2分，共30分）
1、 设P：张晓拿一个苹果，Q：张晓拿一个梨，将命题“张晓只能拿一个苹果或拿一个梨”符号化 (1)___。 2、 设P(x)：x是偶数，Q(x)：x是奇数，在实数R个体域中将命题“存在偶数，也存在奇数”符号化 (2)___，其真值为 (3)___。
3、非空集合A上的自反、对称和 (4)___的关系称为A上的等价关系。 4、给定集合
A?{1,2,3}上的3个关系如下：
R1?{?2,2?,?2,3?,?2,1?,?1,1?}，R2?{?1,1?,?2,2?,?3,3?}， R3?{?2,3?,?2,2?,?3,2?,?1,1?}，
则其中满足自反性的关系是 (5)___；满足对称性的关系是 (6)___； 满足传递性的关系是 (7)___。
5、关系R?{?1,2?,?1,4?,?2,2?,?2,3?}，S则R○S= (8)___。
6、波兰符号表达式 * + 4 5 - / 8 2 1的值是 (9)___。
7、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (10)___个悬挂顶点。
8、设G为连通的平面图，有5个面，总度数为16，则G有 (11)___条边，有 (12)___个顶点。 9、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有 (13)___个树叶。 10、设G??V,E?是无向图，如果G是 (14)___并且 (15)___则G是树。 二、选择题（每题2分，共30分） 1、下面语句是命题的为_____。
A、我正在说谎。 B、把门关上。
C、地球外的星球上也存在生命。 D、吃饭了吗？
2、命题公式(P→Q)∧(P→?Q) ??P为_____。
A、重言式 B、非重言式的可满足式 C、矛盾式 D、等值式 3、下列集合不是连接词完备集的为_____。
12
?{?1,1?,?1,3?,?2,3?,?3,2?,?3,3?}，
A、{?,∧,∨,→, ?} B、{?,∧} C、{→, ?} D、{?}
4、下列谓词公式不是命题公式P→Q的代换实例的是______
A、
F(x)?G(y)
B、
?xF(x,y)??yG(x,y)
C、
?x(F(x)?G(x))
D、
?xF(x)?G(x)
5、下列哪个表达式错误_____。
A、 B、 C、 D、
?x(P(x)?Q(x))??xP(x)??xQ(x)
?xP(x)??xQ(x)??x(P(x)?Q(x))
?x(P(x)?Q(x))??xP(x)??xQ(x) ?x(P(x)?Q(x))??xP(x)??xQ(x)
6、下列哪个表达式错误_____。
A、 B、 C、 D、
7、设集合
?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(B?A(x))?B??xA(x)
?x(A(x)?B)??xA(x)?B
A?{1,2,3,4}上的两个关系R?{?1,1?,?2,4?,?4,2?,?3,3?}，则R具有____。
A、对称性 B、传递性 C、自反性 D、反自反性 8、下述结论错误的是____。
A、存在这样的关系，它可以既满足对称性，又满足反对称性。 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。 C、存在这样的关系，它可以既满足自反性，又满足反自反性。 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。 9、下面关于对称关系的描述错误的是_____。
A、对称关系与其逆关系相等 B、对称关系的矩阵与其逆矩阵相等 C、对称关系的矩阵与其转置矩阵相等
D、对称关系的关系图中任何两个顶点之间如果有边必是一对方向相反的边 10、以下无向图中，不是二部图的是_____。
A、
B、
C、
D、
13
11、在下列关于图论的命题中，正确的是_____。
A、哈密顿图一定是欧拉图
B、无向完全图Kn(n?3)都是欧拉图
C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出 D、哈密顿图是平面图
12、以下无向图中，不是平面图的是_____。
A、
B、
C、
13、下面编码_____不是前缀码。
A、11，00，10，01 B、01，11，001，1001 C、101，11，001，011，010
D、010，11，011，1011，1001，11101 14、5阶非同构的无向树有_____棵。
A、3 B、4 C、5 D、6 15、在下列选项中，关于n阶树(n>1)的性质描述不正确的是_____。
A、在连通n阶图中，n阶树的边的数量最少 B、在n阶无回路图中，n阶树的边的数量最多 C、n阶树不一定是平面图 D、n阶树(n>1)至少有两片树叶
14
D、
三、计算题（5分+8分，共13分）
1、如下图所示的赋权图表示某七个城市V1,V2,?,V7 ，及预先算出它们之间直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。
1 V1 3 V2 2 V3 4 5 V4 7 8 V6 10 V7 9
6 V5 2、设集合
X?{a,b,c,d}，X上的关系R如图所示，试求：
a b c d
（1）写出关系R的关系矩阵MR； （2）画出关系R的自反闭包r(R)的关系图； （3）画出关系R的对称闭包s(R)的关系图； （4）画出关系R的传递闭包t(R)的关系图。 四、证明题（6分，共6分）
1、设T=
五、应用题（9分+6分+6分，共21分） 1、给出集合
A?{1,2,3,4,5,6}，分别求出：
(1)画出集合
(2)集合
A的整除偏序关系的哈斯图；
A的最大元，最小元，极大元，极小元；
?{2,3,6}的上界，下界，最小上界，最小下界。
(3)集合B
2、某研究机构要从A,B,C三人中选派若干人出国考察, 由于工作需要必须满足下述条件:
①若A去，则C必须去； ②若B去，则C不能去； ③若C不去，则A或B可以去。
15