华南农业大学期末考试试卷（A 卷）
2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业
①本试题分为试卷与答卷2部分。

试卷有四大题，共6页。

②所有解答必须写在答卷上，写在试卷上不得分。

一、选择题（本大题共 25 小题，每小题 2 分，共 50 分）
1、下面语句是简单命题的为_____。

A 、3不是偶数
B 、李平既聪明又用功
C 、李平学过英语或日语
D 、李平和张三是同学
2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。

”可以符号化为______。

A 、r q p →⌝∧⌝
B 、r q p ⌝→∧⌝
C 、r q p →⌝∧
D 、r q p ∧→
3、下列谓词公式不是命题公式P →Q 的代换实例的是______。

A 、)()(y G x F →
B 、),(),(y x yG y x xF ∃→∀
C 、))()((x G x F x →∀
D 、)()(x G x xF →∃
4、设个体域为整数集，下列公式中其值为
1的是_____。

A 、)0(=+∃∀y x y x
B 、)0(=+∀∃y x x y
C 、)0(=+∀∀y x y x
D 、)0(=+∃⌝∃y x y x
2
5、下列哪个表达式错误_____。

A 、
B x xA B x A x ∧∃⇔∧∃)())(( B 、B x xA B x A x ∨∃⇔∨∃)())((
C 、B x xA B x A x →∃⇔→∃)())((
D 、)())((x xA B x A B x ∃→⇔→∃ 6、下述结论错误的是____。

A 、存在这样的关系，它可以既满足对称性，又满足反对称性
B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性
C 、存在这样的关系，它可以既满足自反性，又满足反自反性
D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。

A 、自反性、对称性和传递性
B 、自反性、反对称性和传递性
C 、反自反性、对称性和传递性
D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。

A 、R 是自反的，则2R 一定是自反的
B 、R 是反自反的，则2R 一定是反自反的
C 、R 是对称的，则2R 一定是对称的
D 、R 是传递的，则2R 一定是传递
9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。

A 、11--R R
B 、11--S R
C 、11--S S
D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。

A 、c b , B 、b a , C 、b D 、c b a ,,
11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。

A 、1，2，2，3，4，5
3
B 、1，2，2，3，3，5
C 、2，2，3，4，5，6
D 、1，1，2，3，4，5
12、设无向图G 的关联矩阵为⎥
⎥
⎥⎥⎦
⎤⎢⎢⎢⎢
⎣⎡00000
2100101110
00111，则G 的顶点数与边数分别为_____。

A 、 4, 5 B 、4, 10 C 、5, 4 D 、5, 10
13．设G 是简单有向图，可达矩阵P(G)刻划了_____的关系。

A 、点与边
B 、边与点
C 、点与点
D 、边与边
14．设},,,,,{f e d c b a V =，
},,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ，则有向图
>=<E V G ,是_____。

A 、强连通的
B 、单向连通的
C 、弱连通的
D 、不连通的 15、以下无向图中，不是二部图的是_____。

16、下图中既不是欧拉图，也不是哈密尔顿图的是_______。

C
D
17、以下无向图中，不是平面图的是_____。

18、已知一棵无向树T 中有4度、3度和2度分支点各1个，其余顶点均为树
4
叶，则T 有 个树叶。

A 、2
B 、3
C 、4
D 、5
19、具有6 个顶点，12条边的连通简单平面图中，次数为3的面有______个。

A 、5
B 、 6
C 、 7
D 、 8 20、下面编码_____不是前缀码。

A 、11，00，10，01
B 、01，11，101，1001
C 、11，101，001，011，010
D 、11，010，011，1011，0101，10101
21、满足等式84321=+++x x x x 的正整数解的个数有______。

A 、47C
B 、4
8C C 、311C D 、411C
22．在自然数集N 上，下列_____运算是可结合的。

（对任意N b a ∈,） A 、b a b a -=* B 、),max(b a b a =* C 、b a b a 5+=* D 、b a b a -=*
23、设V 1=<R*,+>，V 2=< R*, ⋅> 是代数系统, R*为非零实数的集合，+为普通加法，⋅为普通乘法，下面函数中是V 1到V 2的同态映射的是_____。

A 、f (x )=2x B 、f (x )= -x C 、 f (x )=1/x D 、f (x )=e x
24、设>⊕<,6Z 是代数系统，}5,4,3,2,1,0{6=Z ，⊕为模6加法运算，则(5)-4= _____。

A 、1
B 、1/625
C 、4
D 、2 25．具有如下定义的代数系统>*<,G ，_____不构成群。

A 、}10,1{=G ，*是模11乘
B 、}9,5,4,3,1{=G ，*是模11乘
C 、}1,0{=G ，*是普通加法
D 、Q G =（有理数集），*是普通加法
5
二、计算题：（本大题共 5个小题，每题 5 分，共 25 分） 1、 求下列谓词公式的前束范式，请写出推导过程：
)),(),((y x yG y x yF x ∀→∃∀
2、给出集合}12,10,9,8,6,4,3,2{=A ，分别求出： (1)画出集合A 的整除偏序关系的哈斯图；
(2)指出集合A 的最大元，最小元，极大元，极小元；
(3)指出集合}6,4,2{=B 的上界，下界，最小上界，最大下界。

3、如下图所示的赋权图表示某六个城市621,,,V V V ，及预先算出它们之间直接通信线路造价(以百万元为单位)，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。

4、画出5阶所有非同构的根树。

5、四个人比赛，名次允许并列，总共有多少种比赛结果。

三、证明题：（本大题共 4 个小题，每题 5 分，共 20 分）
1、 用等值演算法证明下列等值式。

p → (q ∧r) ⇔(p → q) ∧(p → r)
6
2、设++⨯=Z Z A ,在A 上定义二元关系R 如下：
| ,,,{>><><<=d c b a R ,,++⨯>∈<Z Z b a ,,++⨯>∈<Z Z d c }c b d a +=+
证明：R 是A 上的等价关系。

3、设T=<V , E>是n 阶非平凡的无向树，证明：T 至少有两片树叶。

4、实数集R 上定义运算*，2
b
a b a ⋅=
*，·为普通乘法。

判断<R,*> 能构成半群、独异点和群中的何种代数系统。

写出详细证明过程。

四、 应用题（2选1，两道都做仅以第1道算分；5分）
1、构造一个与英文字母b, d, g, o ,y e 对应的前缀码，并画出该前缀码对应的二叉树，写出good bye 的编码信息。

2、计算机系期末要安排7门公共课的考试，课程编号为1到7，下列每一对课程有学生同时选修：1和2、1和
3、1和
4、1和7、2和3、2和4、2和
5、2和7、3和4、3和
6、3和
7、4和5、4和6、5和6、5和7、6和7。

这7门课的考试至少要安排在几个不同的时间段？给出一个安排方案。