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

山东理工大学《离散数学》答案及评分细则（A）卷第2007-2008学年第二学期班级：姓名：学号：…………………………………装……………………………订…………………………线………….………………………………适用专业计算机科学与技术考核性质考试闭卷命题教师张艳华石少俭考试时间100分钟题号一二三四五六七八九十十一总分得分评阅人复核人一、判断题：(对者划√,错者划×10分)1．如果BA，则有AB。(√)2．设R与S是集合A上的任意两个关系。若R与S是反对称的，则RoS也是反对称的。（×）3．（0，1，3，3，3）可以构成简单图的度数序列。（×）4．如一个有向图是欧拉图，则此图一定是强连通图。此命题真值为真。（√）5．若〈S，*〉是一个阿贝尔群，则在关于运算*的运算表中任意两行或两列都是不相同的。（√）二、填空题：（每空2分共20分）1．将命题符号化。“凡偶数均能被2整除”。其中F(x)：x是偶数。G(x)：x能被2整除。（))()((xGxFx）。2．已知集合A={1,2}，则A上可以定义（16）个不同的二元关系，A的幂集为（{{1},{2},{1,2},}）。3．设M(x)：x是人，G(x)：x犯错误。则命题“没有不犯错误的人”形式化为（))()((xGxMx）。4．已知集合A和B，|A|=3，|B|=4则A,B间有（64）个函数；5．若G=V,E为n阶无向完全图，则每个结点的度数为（n-1）。6．若某连通平面图有10个结点，12条边，r个面，则r=（4）。7．在代数系统I,+中，－5的逆元为（5）,33=（9）。8．10阶群的子群的阶数可能为（1，2，5，10）三、（10分）试求))()((PQQPP的主析取范式与主合取范式。解：方法一：10)()()()))(())((())()(())()((MQPQPPPQPPQPQQPPPQPQPPPQQPP(4分)))()((PQQPP的主析取范式为)()()(110100QPQPQPmmm（3分）))()((PQQPP的主合取范式为QP（3分）方法二：真值表法PQ))()((PQQPPFFTFTTTFFTTT（4分）))()((PQQPP的主析取范式为)()()(110100QPQPQPmmm（3分）))()((PQQPP的主合取范式为QPM10（3分）四、（10分）.设正整数的序偶集合A，在A上定义二元关系R如下:x,y,u,v∈R,当且仅当xv=yu,证明：R是A上的等价关系。证明：1）自反：因为x,y∈A,xy=yx所以x,y,x,y∈R（3分）2）对称：因为x,y,u,v∈Rxv=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页山东理工大学《离散数学》试卷纸（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，*是群，对任一aG，令H={y|y*a=a*y，yG},试证明H，*是G，*的子群。证明：显然HG,运算*在H中满足结合性。对于任意的x,yH,以及任意的aG,因为(x*y)*a=x*y*a=x*a*y=a*x*y=a*(x*y)所以x*yH,运算*关于H是封闭的。（5分）记e为G的幺元，因为e*a=a*e,所以eH对于任意的xH，由于x*a=a*x,所以x-1*(x*a)*x-1=x-1*(a*x)*x-1即得a*x-1=x-1*a有x－1H综上所述H，*是G，*的子群。（5分）七、（10分）Q为有理数集，设*为定义在Q上的运算a*b=a+b-41）.*在Q上可结合吗？*在Q上可交换吗？2）.求Q中关于运算*的幺元。3）.集合Q上所有的元素都有逆元吗？若有逆元，请求出。解：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-4＝b*a所以*在Q上可交换。（2分）2）设e为所求的幺元，则对于任意的a∈Q有a*e=e*a=a=a+e-4解得e=4,所以Q中关于运算*的幺元为4。(3分)3）任取a∈Q，有8-a∈Q,而a*(8-a)=a+(8-a)-4=4(8-a)*a=(8-a)+a-4=4所以Q上任一的元素a都有逆元8-a..（3分）共3页第2页山东理工大学《离散数学》试卷纸（A）卷第2007-2008学年第二学期班级：姓名：学号：…………………………………装……………………………订…………………………线………….………………………………八、（10分）1、（5分）试画出一个无向图，它是欧拉图，但不是哈密尔顿图。（5分）（答案不唯一）2、（5分）求下图的最小生成树。（不写步骤）（5分）评分细则：每画错一条边扣1分，直到扣为0分止。九、（10分）设在通信中a，b，c，d，e，f，g这7个字母，传输时出现的频率分别为35%，20%，15%，9%，11%，5%，5%，画出相应的最优二叉树，并写出每个字母对应的前缀码。（答案不唯一）（6分）评分细则：每画错一个结点扣1分，直到扣为0分止。若树高度画错此题记为0分。a对应的前缀码为：00b对应的前缀码为：10c对应的前缀码为：010d对应的前缀码为：111e对应的前缀码为：011f对应的前缀码为：1100g对应的前缀码为：1101(4分)评分细则：每写错两个字母前缀码扣1分。共3页第3页1235689123568941211107acebdfg