离散数学2011秋期试卷B

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

1、咸宁学院计算机科学与技术学院2011年秋季学期2010级计算机科学与技术本科、网络工程《离散数学》期末考试试卷（B卷、闭卷）一、填空题（3分×10＝30分）1、在整数集Z中的运算*定义如下：a*b=a+b-3ab，则*运算的单位元为_______________；设a有逆元，则其a-1逆元为_________________。2、设A={1,2,3,4}，A上的二元关系R={<1,2>,<2,4>,<3,3>}，S={<1,3>,<2,4>,<4,2>}，则___________，___________。3、在根树中，若每一个结点的出度_________m,则称这棵树为m叉树。

2、如果每一个结点的出度________m或0，则称这棵树为完全m叉树。4、设无向图G的所有顶点的度数之和为8，则G的边数是_____。5、如下图所示的二部图中，互补顶点子集分别为{a,_____,____}和{b,______,_____}。6、命题逻辑中的五种基本联结词分别是：________、________、________、________、________。7、在一阶逻辑进行等值演算时，将公式中某量词辖域中的一个约束变项的所有出现及相应的指导变元全部改名称为___________规则；而将公式中某个自由出现的个体变项的所有出现全部改名称为_______规则。8、设A={

3、a,b,c,d}，R={,,,,}，它的传递闭包是_____________________。9、布尔代数又称为_________________格。10、设A=Æ,B={a,b}，则((A)=___________________，A×B=_________________________________。二、选择题（3分×10题＝30分）1、在公式中既是自由变元，又是约束变元是（　　）A、xB、yC、ZD、x和z2、下列关系矩阵所对应的关系具有反对称性的是()A、B、C、D、3、下列函数中为双射的是（　　　）A、f：Z→Z,

4、f(j)=j(mod)3B、C、f：Z→N,f(j)=

5、2j

6、+1D、f：R→R,f(r)=2r-154、下面关于群的说法，正确的是（）A、群不是代数系统。B、群中的运算一定满足结合律和交换律。C、阿贝尔群又称为独异点，是指含有单位元且满足结合律的代数系统。D、群中单位元存在且唯一。35、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）A、2个面B、3个面C、4个面D、5个面6、下列句子属于命题的是（）A、y=2x+1B、2012年春节下雪。C、禁止抽烟!D、这句话是错的7、下列可一笔画成的图形是()8、下面四个哈斯图表示的偏序集中，不属于格的是（）A、B、C、D、

7、9、下列无向图一定是树的是（　　）A、连通图B、无回路但添加一条边则有回路的图C、每对结点之间都有通路的图D、有n个结点，n-1条边的图10、在下图的2叉有序正则树表示的算式中，去掉括号后属于逆波兰符号法的是（）A、(a*(b+c)+d*e*f)÷(g+(h-i)*jB、((a*(b+c))+d*(e*f)))÷(g+((h-i)*j)C、÷(+(*a(+bc))(*d(*ef)))(+g(*(-hi)j)D、((a(bc+)*)(d(ef*)*)+)(g((hi-)j*)+)÷3三、计算题、作图题（每题5分，共15分）1、求的主析取范式和主合取范式。2、设有向图G=(V,E)

8、如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。3、设A={1,2,3,6,9,18}，≤为整除关系。（1）画出的哈斯图；（2）求子集B={3,6,9}的极大元、极小元、最大元、最小元。四、证明题：（每题5分，共15分）1、设n阶m条边的平面图是自对偶图，证明：m=2n-22、证明：设是格，任取，令证明是L的子格。3、设H和K分别为群G的r，s阶子群，若r和s互素，证明：H∩K={e}。五、综合应用题（每题5分，共10分）1、设有6个城市V1，V2，…，V6，它们之间有输油管连通，其布置如下图,Si(数字)中Si为边的编号，括号内数字为

9、边的权，它是两城市间的矩离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守管道的最短的总长度。(要求写出求解过程)2、符号化下列命题，并构造推理证明：只要A曾经到过受害者的房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。3