华南农业大学期末考试试卷（A卷）
2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业
装题号 得分 评阅人 考试注意事项： 一 二 三 四 总分 订 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。
线得分 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分）
1、下面语句是简单命题的为_____。
A、3不是偶数 B、李平既聪明又用功 C、李平学过英语或日语 D、李平和张三是同学
2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。
A、?p??q?r B、?p?q??r C、p??q?r D、p?q?r
3、下列谓词公式不是命题公式P→Q的代换实例的是______。
A、F(x)?G(y)
B、?xF(x,y)??yG(x,y) D、?xF(x)?G(x)
C、?x(F(x)?G(x))
4、设个体域为整数集，下列公式中其值为1的是_____。
A、?x?y(x?y?0) B、?y?x(x?y?0) C、?x?y(x?y?0) D、??x?y(x?y?0)
1
5、下列哪个表达式错误_____。
A、?x(A(x)?B)??xA(x)?B B、?x(A(x)?B)??xA(x)?B C、?x(A(x)?B)??xA(x)?B D、?x(B?A(x))?B??xA(x) 6、下述结论错误的是____。
A、存在这样的关系，它可以既满足对称性，又满足反对称性 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C、存在这样的关系，它可以既满足自反性，又满足反自反性 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A上的关系R为一个等价关系，当且仅当R具有_____。
A、自反性、对称性和传递性 B、自反性、反对称性和传递性 C、反自反性、对称性和传递性 D、反自反性、反对称性和传递性 8、下列说法不正确的是：______。
A、R是自反的，则R2一定是自反的 B、R是反自反的，则R2一定是反自反的 C、R是对称的，则R2一定是对称的 D、R是传递的，则R2一定是传递
9、设R和S定义在P上，P是所有人的集合，R?{?x,y?|x,y?P?x是y的父亲}，S?{?x,y?|x,y?P?x是y的母亲}，则关系{?x,y?|x,y?P?y是的
x外祖父}的表达式是：______。
A、R?1?R?1 B、R?1?S?1 C、S?1?S?1 D、S?1?R?1 10、右图描述的偏序集中，子集{b,e,f}的上界为_____。 A、b,c B、a,b C、b D、a,b,c
11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。
A、1，2，2，3，4，5
2
B、1，2，2，3，3，5 C、2，2，3，4，5，6 D、1，1，2，3，4，5
?11100?装订线 12、设无向图G的关联矩阵为??01110?则G的顶点数与边数分别为_____。 ??10012?，??00000??A、 4, 5 B、4, 10 C、5, 4 D、5, 10
13．设G是简单有向图，可达矩阵P(G)刻划了_____的关系。
A、点与边 B、边与点 C、点与点 D、边与边
14．设V?{a,b,c,d,e,f}，
E?{?a,b?,?b,c?,?c,a?,?a,d?,?d,e?,?f,e?}，则有向图
G??V,E?是_____。
A、强连通的 B、单向连通的 C、弱连通的 D、不连通的 15、以下无向图中，不是二部图的是_____。
A、 B、 C、
D、 16、下图中既不是欧拉图，也不是哈密尔顿图的是_______。
A、 B、 C、
D、
17、以下无向图中，不是平面图的是_____。
A、
B、 C、
D、
18、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树
3
叶，则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、满足等式x1?x2?x3?x4?8的正整数解的个数有______。
3444A、C7 B、C8 C、C11 D、C11
22．在自然数集N上，下列_____运算是可结合的。（对任意a,b?N） A、a?b?a?b B、a?b?max(a,b) C、a?b?a?5b D、a?b?a?b
23、设V1=
24、设?Z6,??是代数系统，Z6?{0,1,2,3,4,5}，?为模6加法运算，则(5)?4= _____。
A、1 B、1/625 C、4 D、2 25．具有如下定义的代数系统?G,??，_____不构成群。
A、G?{1,10}，*是模11乘 B、G?{1,3,4,5,9}，*是模11乘 C、G?{0,1}，*是普通加法 D、G?Q（有理数集），*是普通加法
4
1.5CM 装订线
得分 二、计算题：（本大题共 5个小题，每题 5 分，共 25 分） 1、 求下列谓词公式的前束范式，请写出推导过程：
?x(?yF(x,y)??yG(x,y))
2、给出集合A?{2,3,4,6,8,9,10,12}，分别求出： (1)画出集合A的整除偏序关系的哈斯图；
(2)指出集合A的最大元，最小元，极大元，极小元；
(3)指出集合B?{2,4,6}的上界，下界，最小上界，最大下界。
3、如下图所示的赋权图表示某六个城市V1,V2,?,V6 ，及预先算出它们之间直接通信线路造价(以百万元为单位)，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。
V2 5 V3 1 8 V1 2 4 7 V4 3 V6 6 V5 9
4、画出5阶所有非同构的根树。
5、四个人比赛，名次允许并列，总共有多少种比赛结果。
得分 三、证明题：（本大题共 4 个小题，每题 5 分，共 20 分）
1、 用等值演算法证明下列等值式。
p? (q?r) ?(p? q) ?(p? r)
5
华南农业大学 离散数学 期末考试2013试卷及答案
