离散数学试卷及答案

《离散数学试卷及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、填空10%（每小题2分）1、设是由有限布尔格诱导的代数系统，S是布尔格，中所有原子的集合，则～。2、集合S={α，β，γ，δ}上的二元运算*为*αβγδαδαβγβαβγδγβγγγδαδγδ那么，代数系统中的幺元是,α的逆元是　　　　。3、设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，则+3的运算表为；是否构成群。4、设G是n阶完全图，则G的边数m=。5、如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行次这个加法指令。二、选择20%（每小

2、题2分）1、在有理数集Q上定义的二元运算*，有，则Q中满足（）。A所有元素都有逆元；B、只有唯一逆元；C、时有逆元；D、所有元素都无逆元。2、设S={0，1}，*为普通乘法，则是（）。A半群，但不是独异点；B、只是独异点，但不是群；C、群；D、环，但不是群。3、图给出一个格L，则L是（）。A、分配格；B、有补格；C、布尔格；D、A,B,C都不对。2、有向图D=，则长度为2的通路有（）条。A、0；B、1；C、2；D、3。1、在Peterson图中，至少填加（）条边才能构成Euler图。A、1；B、2；C、4；D、5。二

3、、判断10%（每小题2分）1、在代数系统中如果元素的左逆元存在，则它一定唯一且。（）2、设是群的子群，则中幺元e是中幺元。（）3、设，+,·为普通加法和乘法，则代数系统是域。（）4、设G=是平面图，

4、V

5、=v,

6、E

7、=e，r为其面数，则v-e+r=2。（）5、如果一个有向图D是欧拉图，则D是强连通图。（）四、证明46%1、设，是半群，e是左幺元且，使得，则是群。（10分）2、循环群的任何非平凡子群也是循环群。（10分）3、设aH和bH是子群H在

8、群G中的两个左陪集，证明：要末，要末。（8分）4、设，是一个含幺环，

9、A

10、>3，且对任意，都有，则不可能是整环（这时称是布尔环）。（8分）5、若图G不连通，则G的补图是连通的。（10分）五、布尔表达式8%设是布尔代数上的一个布尔表达式，试写出其的析取范式和合取范式。六、图的应用16%1、构造一个结点v与边数e奇偶性相反的欧拉图。（6分）2、假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happyn

11、ewyear的编码信息。（10分）一、填空10%（每小题2分）+3[0][1][2][0][0][1][2][1][1][2][0][2][2][0][1]1、；2、β，γ；3、是；4、；5、9一、选择10%（每小题2分）题目12345答案CBDBD二、判断10%（每小题2分）题目12345答案NYYNY三、证明46%1、（10分）证明：（1）(2)e是之幺元。事实上：由于e是左幺元，现证e是右幺元。（3）由（2），（3）知：为群。2、（10分）证明：设是循环群,G=(a)，设是

12、,*>的子群。且，则存在最小正整数m，使得：，对任意，必有，故：即：所以但m是使的最小正整数，且，所以r=0即：这说明S中任意元素是的乘幂。所以是以为生成元的循环群。3、（8分）证明：对集合，只有下列两种情况：（1）；（2）对于，则至少存在，使得，即有，这时任意，有，故有同理可证：所以4、（8分）证明：反证法：如果，是整环，且有三个以上元素，则存在即有：这与整环中无零因子条件矛盾。因此不可能是整环。5、（10分）证明：因为G=不连通，设其连通分支是，，则有两种情况：（1）u,v，分别属于两

13、个不同结点子集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分）解：根据权数构造最优二叉树：传输它们的最佳前缀码如上图所示，happynewyear的编码信息为

14、：10011010101010011101110100001111011000附：最优二叉树求解过程如下：一、单项选择题(本大题共15小题，每小题1分，共15分)1.设P：天下大雨,Q：他在室内运动,命题“