1、离散数学试题带答案试卷十四试题与答案一、 填空 10% （每小题 2分）1、 设是由有限布尔格诱导的代数系统，S是布尔格，中所有原子的集合，则 。2、 集合S=，上的二元运算*为*那么，代数系统中的幺元是 , 的逆元是 。3、 设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，则+3的运算表为 ；是否构成群 。4、 设G是n阶完全图，则G的边数m= 。5、 如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行 次这个加法指令。二、 选择 20% （每小题 2分）1、 在有理数集Q上定义的二元运算*，有，则Q中满足（ ）。A、 所有元
2、素都有逆元； B、只有唯一逆元； C、时有逆元； D、所有元素都无逆元。2、 设S=0，1，*为普通乘法，则是（ ）。A、 半群，但不是独异点； B、只是独异点，但不是群；C、群； D、环，但不是群。3、图 给出一个格L，则L是（ ）。A、分配格； B、有补格； C、布尔格； D、 A,B,C都不对。3、 有向图D= ，则长度为2的通路有（ ）条。A、0； B、1； C、2； D、3 。4、 在Peterson图中，至少填加（ ）条边才能构成Euler图。A、1； B、2； C、4； D、5 。三、 判断 10% （每小题 2分）1、 在代数系统中如果元素的左逆元存在，则它一定唯一且。（ ）2
3、、 设是群的子群，则中幺元e是中幺元。（ ）3、 设， +,为普通加法和乘法，则代数系统是域。（ ）4、 设G=是平面图，|V|=v, |E|=e，r为其面数，则v-e + r=2。（ ）5、 如果一个有向图D是欧拉图，则D是强连通图。（ ）四、证明 46%1、 设，是半群，e是左幺元且，使得，则是群。（10分）2、 循环群的任何非平凡子群也是循环群。（10分）3、 设aH和bH是子群H在群G中的两个左陪集，证明：要末，要末 。（8分）4、 设，是一个含幺环，|A|3，且对任意，都有，则不可能是整环（这时称是布尔环）。（8分）5、 若图G不连通，则G的补图是连通的。（10分）五、布尔表达式 8
4、%设是布尔代数上的一个布尔表达式，试写出其的析取范式和合取范式。六、图的应用 16%1、 构造一个结点v与边数e奇偶性相反的欧拉图。（6分）2、 假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。（10分）答案一、 填空 10%（每小题2分）+30120012112022011、；2、，；3、 是；4、；5、9二、 选择 10%（每小题 2分）题目12345答案CBDBD三、 判断 10%（每小题2分）题目12345答案NYYNY四、 证明 46%1、（10分
5、）证明：（1）(2) e 是之幺元。事实上：由于e是左幺元，现证e是右幺元。（3）由（2），（3）知：为群。2、（10分）证明：设是循环群,G=(a)，设是的子群。且，则存在最小正整数m，使得：，对任意，必有，故： 即：所以但m是使的最小正整数，且，所以r=0即：这说明S中任意元素是的乘幂。 所以是以为生成元的循环群。3、（8分）证明：对集合，只有下列两种情况：（1）； （2）对于，则至少存在，使得，即有，这时任意，有，故有同理可证：所以 4、（8分）证明：反证法：如果，是整环，且有三个以上元素，则存在即有：这与整环中无零因子条件矛盾。因此不可能是整环。5、（10分）证明：因为G=不连通，设其
6、连通分支是，则有两种情况：（1） u , v，分别属于两个不同结点子集Vi，Vj，由于G(Vi) , G(Vj)是两连通分支，故(u , v)在不G中，故u , v 在中连通。（2） u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故(u , w),(w , v )均在中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点u和v，即u , v在中也是连通的。五、布尔表达式 8%函数表为：00000011010001111000101111011111析取范式：合取范式：六、 树的应用 16%1、（6分）解：2、（10分）解：根据权数构造最优二叉树：传输它们的最
7、佳前缀码如上图所示，happy new year的编码信息为：10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最优二叉树求解过程如下：试卷十五试题与答案四、 填空 20% （每空 2分）1、 如果有限集合A有n个元素，则|2A|= 。2、 某集合有101个元素，则有 个子集的元素为奇数。3、 设S=a1，a2,，a8，Bi是S的子集，由B17表达的子集为 ， 子集a2,a6,a7规定为 。4、 由A1，A2,，An，生成的最小集的形式为 ，它们的并为 集，它们的交为 集。5、 某人有三个儿子，组成集合A=S1,S2,S3，在A上的兄弟关系
8、具有 性质。6、每一个良序集必为全序集，而 全序集必为良序集。7、若是函数，则当f是的 ，是f的逆函数。五、 选择 15% （每小题 3分）1、 集合的幂集为（ ）。A、；B、；C、；D、2、 下列结果正确的是（ ）。A、；B、；C、；D、；E、；F、AA=A 。3、 集合的最小集范式为（ ）（由A、B、C生成）。A、 ； B、；C、 ； D、。4、 在（ ） 下有。A、；B、；C、；D、5、 下列二元关系中是函数的有（ ）。A、；B、；C、。三、 15% 用Warshall算法，对集合A=1，2，3，4，5上二元关系R=,求t（R）。四、15%集合，C*上定义关系，则R是C*上的一个等价关系，并给出R等价类的几何说明。五、计算 15%1、 设A=1，2，3，4，S=1，2，3，4
