离散数学试题.doc

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

1、一、填空10%<每小题2分）1、，*表示求两数的最小公倍数的运算中，

2、A

3、>1，如果分别为的幺元和零元，则的关系为。3、设是一个群，是阿贝尔群的充要条件是。4、图的完全关联矩阵为。5、一个图是平面图的充要条件是。二、选择10%<每小题2分）1、下面各集合都是N的子集，<）集合在普通加法运算下是封闭的。A、{x

4、x的幂可以被16整除}；B、{x

5、x与5互质}；C、{x

6、x是30的因子}；D、{x

7、x是30的倍数}。2、设，，其中表示模3加法

8、，*表示模2乘法，则积代数的幺元是<）。A、<0,0>；B、<0,1>；C、<1,0>；D、<1,1>。3、设集合S={1,2,3,6}，“≤”为整除关系，则代数系统是<）。b5E2RGbCAPA、域；B、格，但不是布尔代数；C、布尔代数；D、不是代数系统。4、设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=<）。A、n·k；B、n(k+1>；C、n(k+1>-m；D、n(k+1>-2m。5、一棵树有7片树叶，3个3度结点，其余全是4度结点，84/3则该树有<）个4度结点。A、1；B、2；C、

9、3；D、4。三、判断10%<每小题2分）1、<）设S={1,2}，则S在普通加法和乘法运算下都不封闭。2、<）在布尔格中，对A中任意原子a，和另一非零元b，在或中有且仅有一个成立。3、<）设，+,·为普通加法和乘法，则是域。4、<）一条回路和任何一棵生成树至少有一条公共边。5、<）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1>i=t-1。四、证明38%1、<8分）对代数系统，*是A上二元运算，e为A中幺元，如果*是可结合的且每个元素都有右逆元，则<1）中的每个元素在右逆元必定也是左逆

10、元。p1EanqFDPw<2）每个元素的逆元是唯一的。2、<12分）设是一个布尔代数，如果在A上定义二元运算☆，为，则是一阿贝尔群。3、<10分）证明任一环的同态象也是一环。4、<8分）若是每一个面至少由k(k≥3>条边围成的连通平面图，则。五、应用32%1、84/3<8分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边<其图如右），问至少需几天？DXDiTa9E3d1、用washall方法求图的可达矩阵，并判断图的连通性。<8分）2

11、、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？<8分）RTCrpUDGiT3、用Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W