广州大学 2003-2004 学年第二学期考试a卷。
课程离散数学考试形式（闭卷，考试）
信息学院计算机工程与应用系计算机专业 03级班学号： 姓名。
一、 填空题：（每格1分，共20分）
1．由n个命题变元组成不等价的命题公式的个数为 （2分）
2．集合a上的二元运算对二元运算 * 可分配，当且仅当a,b,ca，以下两个式子同时成立： a(b*c)= ab) *ac) 和 (b*c) a = ba) *ca)
3．具有4个结点的非同构的无向树的数目为 2
4．n阶4正则图(有n个结点，每个结点的度是4)一定是欧拉图 (欧拉图/哈密顿图)。
5．个体域是自然数，a(x,y)表示x比y大，表示“不存在最大的自然数”的谓词公式是。
(x) (y) b(y,x) 或 (x) (y) b(y,x) （2分）
6．结点总数为9的完全二叉树共有 5 个叶结点。
7．具有5个结点7条边的简单连通平面图，共有 4 个平面。
8. r为实数集， +为普通加法， 代数系统的单位元是 0 ，3的逆元是 -3 ，零元不存在 ( 是0 / 不确定 / 不存在 )
9．已知有限集合a，|a|=n，则|a×a| =n2 , a上共有 2 个不同的关系，a到a共有 nn 个不同的函数，a到a共有 n! 个不同的双射。
10．非空集合a上的关系r满足自反 、 对称 、 传递 ，则r是等价关系。
判断题（在括号内填上“√”或“╳”每题1分，共15分，做错不倒扣）
1人与人之间的同龄关系是等价关系；
2运算均可表示为和 ；
3树的结点总数一定与树的边数有关；
4集合a, b均为非空有限集， 则a×b = b×a ；
5a = a；
6任何二元运算都有单位元和零元；
7代数系统的自同构函数一定是恒等函数；
8非空集合上的对称关系一定不是反对称关系；
9无向连通图g中无回路，则g的每一条边都是割边；
10无向图g中有n个结点，n-1条边，则g一定是无向树；
11在有10个结点的无向图中，不存在结点总度数为45的图；
13一个群不可能同构于自己的一个真子群；
14正整数之间的整除关系是偏序关系；
15pq)(q)(p) 是重言式。
二、 选择题（每题1分，共10分）
1（ b ）集合a=上的关系r=，则r的性质为。
a） 自反的
b） 对称的
c） 传递的、对称的
d） 反自反的、传递的。
2．（ b ）图g与图g’的结点和边分别存在着一一对应关系是g与g’同构的。
a） 充分条件
b） 必要条件
c） 充分必要条件
d） 既不充分也不必要。
3．（ b ）在有n个结点的无向连通图中，其边数。
a） 最多有n-1条；
b） 至少有n-1条；
c） 最多有n条；
d） 至少有n条。
4．( d ) 以"如果甲乙都不是木工，那么丙是木工"为一前提，若再增加另一前提则可必然推出"乙是木工"的结论。下列命题中的哪一个最适合？
a） 丙是木工。
b） 丙不是木工。
c） 甲不是木工。
d） 甲和丙都不是木工。
5. (b ) 给定下列序列，哪一个可构成无向简单图的结点度数序列？
a） （1，1，2，2，3）
b） （1，1，2，2，2）
c） （0，1，3，3，3）
d） （1，3，4，4，5）
6. (b ) 下列关系中哪些能够构成函数？
a）f =
b）g =
c）f =
d）g =
7．（ b ）实数集上定义的二元运算*，哪个是可交换的？
a）a*b = a|b|
b）a*b = a+b+2
c）a*b = a/b
d）a*b = ab+2b
8．（ c ）5个结点可构成多少棵非同构的无向树？
a）1 （b）2 （c）3 （d）4
9．（ d ）设g = v,e)是无向图，|v|=7，|e|=23，则g一定是。
a） 完全图。
b） 零图。
c） 简单图。
多重图。10（ c ）有4个元素的集合上共有多少个不同的等价关系？
a） 8 （b）14 （c）15 （d）16
三、 （1）5个结点、3条边的不同构的简单图有几个？请画出来。（6分）
2）某次会议有20人参加，每人至少有10个朋友，这20人围一圆桌入席，要使每人相邻的两位都是朋友，是否可能？根据是什么？（4分）
解：用结点代表人，用边代表朋友关系，则得到一个有20个结点、每个结点的度大于等于10的无向图，这一无向图满足判断汉密尔顿图的充分条件，故是汉密尔顿图，存在汉密尔顿回路，按此回路各点位置入席即可。
四、 列出集合的所有子集，并画出各子集之间包含关系的哈斯图：（5分）
五、 定义ab=a∪b - a∩b，a=b当仅当ab=，这里a，b表示集合。（8分）
证明：必要性：
当a=b时，ab=aa= a∪a - a∩a = a-a=
充分性：ab=
a (ab)= a
a a) b = a
b = ab = a
六、 证明：不存在19阶5正则图 ( 有19个结点，每个结点的度是5 )。8分）
证明：用反证法。
若存在19阶5正则图，则该图的结点的总度数之和为19*5=95，与握手定理矛盾，故不存在19阶5正则图。
七、 设和是两个群，在ab上定义运算：★ 证明：是一个群。（8分）
解： a≠φ，b≠φ，因此 ab≠φ 且★在ab上封闭；
因*和△是可结合的，故★也是可结合的；
设e1和e2分别是和的幺元，则可以证明是的幺元；
aa，bb，逆元分别为a-1、b-1，则。
ab，且。★ =从而 -1 =
八、 设*是集合s上可结合的二元运算，对于s中任意元素x,y，如果x*y=y*x则x=y。证明：* 满足幂等率。（8分）
解： xs，因*满足结合率，故 x*(x*x) =x*x) *x，取y=x*x代入x*y=y*x，有x=y，即 x = x*x.，因此* 满足幂等率。
九、 画出下面二元表达式的二叉树表示，再通过先序遍历，写出该式的波兰式：（8分）
a+b)*(c-d)+(e*f)/g
解：波兰式：+*ab-cd/*efg
03模拟卷答案
模拟卷答案及分析。必考部分 35分 一 选择题 本题有10小题，每小题2分，共20分。选出各题中一个符合题意的正确选项，不选 多选 错选均不给分 分析 该题考查信息的特征。本题主要考查的是信息的特征，该过程体现了信息的传递与共享的特征。分析 该题考查ultraedit软件的应用和十六进制数的理解。一...
03 期末测试 一 答案
a.孱ch n。b.赦sh d.吟y n。a.其 棋。c.配 沛。d.藉 籍。不是 而是 表示后者是正确的，是表并列关系的关联词 不是 就是 表示两者都有可能是正确的，是表选择关系的关联词。4.答案标点符号修改 将第 句的 改为 句子修改 将第 句中 的静穆 删去，平凡 改为 非凡 解析第 句是选择...
03级自控 答案
汽车工程学院车辆工程专业2003级。自动控制基础 课程期终考试试卷。姓名班级学号。考试时间 120分钟 一 填空题 本题共25分 1 所谓自动控制，就是没有人直接参与的情况下，使被控制对象的某些物理量准确地按照预期的规律变化 本小题1分 2 反馈是指输出量通过适当的测量装置将信号的全部或一部分返回输...