5、M(x)：x是人，F(x)：x活百岁以上；则“有人能活百岁以上”可表示为______。
A、F(x)?M(x)
B、?xF(x)?M(x)
C、?x(F(x)?M(x))
D、?x(M(x)?F(x))
?0,a1?1；DI特定函数
6、给定解释I如下：个体域DI为整数集合；DI中特定元素a0f(x,y)?x?y,g(x,y)?x?y；DI上特定谓词F(x,y)为x?y。给定下面各公式：
A、F(f(x,a1),g(x,a1))
B、?x?yF(f(x,y),g(x,y))
C、?x?yF(f(x,y),g(x,y))
(x,y),g(x,y))))
D、?y(F(y,a0)??x(?F(f则公式________真值为假。 7、若|A|?3，则A?A上可以定义______个二元关系。
A、9 B、27 C、81 D、512 8、下列关于关系的等式不成立的是______。
A、(F?G)?H?F?(G?H)
B、(F?G)?1?F?1?G?1
C、(F?G)?H?(F?H)?(G?H)
D、(F?G)?H?(F?H)?(G?H)
9、若关系R的关系矩阵为对称矩阵，则关系R一定具有______。
31
A、自反性 B、对称性 C、反对称 D、传递性 10、若T为树，以下叙述不正确的是_____。
A、T是连通的且每个点都是割点 B、T的每对顶点之间有唯一的一条路径 C、T是连通的且每条边都是割边 D、T是连通的且不含回路
11、在下列选项中，不是群的是_____。
A、(Q,?)，Q为有理数，*为乘法运算 B、(R?,?)，R?为非零实数集，?为乘法运算
C、全体实对称矩阵集合，对于矩阵的加法运算 D、(Q,?)，Q为有理数，+为加法运算
12、给定下列各序列，可以构成无向简单图的度数序列为______。
A、1,1,2,2,3 B、1,1,2,2,2 C、0,1,3,3,3 D、1,3,4,4,5 13、5个顶点非同构的根树有______个。
A、7 B、8 C、9 D、 10 14、下面编码______不是前缀码。
A、11，00，10，01 B、01，11，011，1001 C、101，11，001，011，010
D、010，11，011，1011，1001，10101 15、无向完全带权图Kn(n?2)中，按权计算最多有______条不同的哈密顿回路。
A、n! B、(n?1)! C、(n?1)!/2 D、n!/2
得分
32
二、填空题（本大题共 15 空，每空 2 分，共 30 分） 1、若有限集合
A上的等价关系R有三个等价类，则其关系图的连通分支数为_______。
2、设个体域为整数集合，命题(?x)(?x)(x?y?0)的真值为：______。
3、?x(F(x,y)??yG(x,y))的前束范式为：______。
4、设R是集合A上的二元关系，如果关系R同时具有自反性、______和传递性，则称R是A上的偏序关系。 5、设S?{1,2,3,...,10}，定义S上的关系R?{?x,y?|x,y?S?x?y?10}，则R具有______性
质。
6、在有理数集Q上定义二元运算?，?x,y?Q有x?y?x?y?xy，
则关于运算? 的幺元是______。7、在群、半群、独异点中，______满足消去律。
8、35条边，每个顶点的度数至少为3的图最多有______个顶点。
9、设n阶图G中有m条边，每个顶点的度数不是k就是k?1，若G中有_____个k度顶点（用关于m、n、k的表达式表示）。
10、若10阶平面图G中有5个面，则图G中有______条边。 11、一颗带权为1，2，3，4，5，6的最优三元树，其权为______。 12、群?Z6,??中（?为模6加法运算），则5的阶为______。
13、若某个简单图不是欧拉图但具有欧拉通路，则图中奇度数的顶点个数一定为______。 14、n个顶点的无向树是平面图，它的无穷面的次数为：_______。 15、求满足不等式x1?x2?x3?6的正整数解的个数有______
三、计算题：（本大题共 4 个小题，每题 5 分，共 20 分） 1、画出下列集合关于整除关系的哈斯图 {1,2,3,4,5,6,8,12,15,24}，并指出它的极小元、最小元、极大元、最大元。
2、已知：有向图
D??V,E?，
V?{1,2,3,4}，E={
?1,2?,?1,4?,?2,3?，
?3,4?,?2,4?,?3,1?}，求有向图D的邻接矩阵和可达矩阵。
33
CM
3、带有n个顶点的2元完全正则树有多少树叶？
4、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？
四、证明题：（本大题共 4 个小题，每题 5 分，共 20 分） 1、P?(Q?R)?Q?(P?R)
2、设R1和R2是集合
A上的等价关系，且R1?R2?R2?R1，证明：
R1?R2是集合A上的对称关系。
3、设G为n阶无向简单图，证明：若G为自补图（若一个图的补图为本身则称为自补图），则n?4k或
n?4k?1，其中k为正整数。
4、证明：设?R,??是一个代数系统，*是R上的二元运算，?a,b?R,R,??是含幺半群。（R为实数集合）。
a?b?a?b?ab，
则0是单位元，且?
34
答案：
华南农业大学期末考试试卷参考答案（ A 卷）
2006学年第二学期 考试科目： 离散结构
考试类型：（闭卷） 考试时间： 120 分钟
学号 姓名 年级专业
题号 得分 评阅人 一 二 三 四 五 总分 注意事项：1．考试时间120分钟，闭卷考试
2．试卷共五大题，满分100分
3．全部答案写在答题纸上，试卷纸上答题无效 ．．．．．．．．
一、填空（每空2分，共30分）
1、______P?Q___________； 2、___________1___________； 3、______ _ y____________； 4、___________全是1_______； 5、______ 对称矩阵______； 6、__________对称 ______； 7、_________单向连通____； 8、___________7__________； 9、_________14____________； 10、__________28__________； 11、_________23____________； 12、__________a___________； 13、________ c，d _______ _ _； 14、__________e___________； 15、_____{e,a,a2,a3} ___。
二、选择题（每题2分，共30分）
1、 6、 11、 三、计算题
参见PPT《离散结构（2007-a）考题提示和参考》
A C C 2、 7、 12、 C 3、 8、 13、 B B C 4、 9、 14、 D C B 5、 10、 15、 D B D 无 B 四、证明题
参见PPT《离散结构（2007-a）考题提示和参考》
五、应用题
35