山东理工大学《离散数学》答案及评分细则

1、精选优质文档-倾情为你奉上 山东理工大学离散数学答案及评分细则（ A）卷 第2007-2008学年第二 学期 班级： 姓名： 学号： 装订线.适用专业计算机科学与技术考核性质考试闭 卷命题教师张艳华 石少俭考试时间100分钟题号一二三四五六七八九十十一总分得分评阅人复核人 一、 判断题：(对者划, 错者划× 10分)1如果 ，则有AB 。( )2设R与S是集合A上的任意两个关系。若R与S是反对称的，则RoS也是反对称的。（× ）3（0，1，3，3，3）可以构成简单图的度数序列。（ × ）4如一个有向图是欧拉图，则此图一定是强连通图。此命题真值为真。（ ）5若S，*

2、是一个阿贝尔群，则在关于运算*的运算表中任意两行或两列都是不相同的。（ ）二、填空题：（每空2分 共20分）1将命题符号化。“凡偶数均能被2整除”。其中F(x)：x是偶数。G(x)：x能被2整除。（ ）。2已知集合A=1,2，则 A上可以定义（ 16 ）个不同的二元关系， A的幂集为（1,2,1,2, ）。3设 M(x)：x是人，G(x)：x犯错误。则命题“没有不犯错误的人”形式化为（ ）。4已知集合A和B，|A|=3， |B|=4 则A,B间有（ 64 ）个函数； 5若G=<V, E>为n阶无向完全图，则每个结点的度数为（n-1 ）。6若某连通平面图有10个结点，12条边，r个面

3、，则r=（ 4 ）。7在代数系统<I,+>中，5的逆元为（ 5 ）,33=（ 9 ） 。810阶群的子群的阶数可能为（1，2，5，10 ）三、（10分）试求 的主析取范式与主合取范式。解：方法一： (4分)的主析取范式为 （3分）的主合取范式为 （3分）方法二：真值表法P QFFTFTTTFFTTT （4分）的主析取范式为 （3分）的主合取范式为 （3分） 四、（10分）.设正整数的序偶集合A，在A上定义二元关系R如下:<<x,y>,<u,v>>R,当且仅当xv=yu,证明：R是A上的等价关系。证明：1）自反：因为<x,y>A,xy=

4、yx 所以<<x,y>,<x,y>>R （3分）2）对称：因为<<x,y>,<u,v>>R xv=yu, uy=vx, 所以<<u,v>,<x,y>>R （3分）传递：因为如果<<x,y>,<u,v>>R , <<u,v>,<s,t>>R ,xv=yu,ut=vs,xvut=yuvs,xt=ys, 所以<<x,y>,<s,t>>R （4分） 共 3 页 第 1 页山东理工大学离散数

5、学试卷纸（A）卷 第2007-2008学年第 二 学期 班级： 姓名： 学号： 装订线.五、简答题（10 分）设集合A=1，3，4，5，6，12，24，D为A上的整除关系，则（1）.A ，D 是偏序集吗？（2）.写出集合3，4，6，12的上确界、下确界、极大元、极小元、最大元、最小元。答：（1）.A ，D 是偏序集。（4分） （2）集合3，4，6，12的上确界为12、下确界为1、极大元为12、极小元为3，4、最大元为12、最小元无（每个1分，共6分）六、证明题：(10分) 设<G，*>是群，对任一aG，令H=y|y*a=a*y，yG,试证明<H，*>是<G，*&g

6、t;的子群。证明：显然HG,运算*在H中满足结合性。对于任意的x,yH,以及任意的aG,因为(x*y)*a=x*y*a=x*a*y=a*x*y=a*(x*y)所以x*yH,运算*关于H是封闭的。 （5分）记e为G的幺元，因为e*a=a*e,所以eH对于任意的xH，由于x*a=a*x,所以x-1*(x*a)*x-1=x-1*(a*x)*x-1即得a*x-1=x-1*a有x1H综上所述<H，*>是<G，*>的子群。 （5分）七、（10分）Q为有理数集，设*为定义在Q上的运算a*b=a+b-41）.*在Q上可结合吗？*在Q上可交换吗？2）.求Q中关于运算*的幺元。3）.集合Q

7、上所有的元素都有逆元吗？若有逆元，请求出。解：1).对于Q中的任意元素a,b,c ,(a*b)*c=(a+b-4)*c= a+b-4+c-4=a+b+c-8=a*(b*c) ,所以*在Q上可结合。（2分）因为a*b=a+b-4b*a 所以*在Q上可交换。（2分）2）设e为所求的幺元，则对于任意的aQ 有a*e=e*a=a =a+e-4 解得e=4 ,所以Q中关于运算*的幺元为4。(3分)3）任取aQ，有8-aQ, 而a*(8-a)=a+(8-a)-4=4 (8-a)*a=(8-a)+a-4=4所以Q上任一的元素a都有逆元8-a. .（3分） 共 3 页 第 2 页山东理工大学离散数学试卷纸（A

8、 ）卷 第2007-2008学年第 二 学期 班级： 姓名： 学号： 装订线.八、（10分）1、（5分）试画出一个无向图，它是欧拉图，但不是哈密尔顿图。（5分）（答案不唯一）2、（5分）求下图的最小生成树。（不写步骤） 1235689412111071235689 （5分）评分细则：每画错一条边扣1分，直到扣为0分止。九、（10分）设在通信中a，b，c，d，e，f，g这7个字母，传输时出现的频率分别为35%，20%，15%，9%，11%，5%，5%，画出相应的最优二叉树，并写出每个字母对应的前缀码。acebdfg（答案不唯一）（6分）评分细则：每画错一个结点扣1分，直到扣为0分止。若树高度画错此题记为0分。a对应的前缀