离散数学试卷及答案(13)

离散数学试卷（十三）82一、填空10%（每小题2分）1、}0|{xZxxZ，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*运算的幺元是，零元是。2、代数系统A,*中，|A|1，如果和e分别为A,*的幺元和零元，则和e的关系为。3、设G,*是一个群，G,*是阿贝尔群的充要条件是。4、图的完全关联矩阵为。5、一个图是平面图的充要条件是。二、选择10%（每小题2分）1、下面各集合都是N的子集，（）集合在普通加法运算下是封闭的。A、{x|x的幂可以被16整除}；B、{x|x与5互质}；C、{x|x是30的因子}；D、{x|x是30的倍数}。2、设},2,1,0{1G，},*1,0{2G，其中表示模3加法，*表示模2乘法，则积代数21GG的幺元是（）。A、0,0；B、0,1；C、1,0；D、1,1。3、设集合S={1,2,3,6}，“≤”为整除关系，则代数系统S,≤是（）。A、域；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度结点，则该树有（）个4度结点。离散数学试卷（十三）83A、1；B、2；C、3；D、4。三、判断10%（每小题2分）1、（）设S={1,2}，则S在普通加法和乘法运算下都不封闭。2、（）在布尔格A,≤中，对A中任意原子a，和另一非零元b，在ba或ba中有且仅有一个成立。3、（）设NxZxxS}0|{，+,·为普通加法和乘法，则S，+，·是域。4、（）一条回路和任何一棵生成树至少有一条公共边。5、（）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i=t-1。四、证明38%1、（8分）对代数系统A,*，*是A上二元运算，e为A中幺元，如果*是可结合的且每个元素都有右逆元，则（1）A,*中的每个元素在右逆元必定也是左逆元。（2）每个元素的逆元是唯一的。2、（12分）设,,,A是一个布尔代数，如果在A上定义二元运算☆，为)()(☆bababa，则A,☆是一阿贝尔群。3、（10分）证明任一环的同态象也是一环。4、（8分）若),(,eEvVEVG是每一个面至少由k(k≥3)条边围成的连通平面图，则2)2(kvke。五、应用32%1、（8分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？离散数学试卷（十三）842、用washall方法求图的可达矩阵，并判断图的连通性。（8分）3、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分）4、用Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a，b，c，d，e，f的频率分别为2%，3%，5%，7%，8%，9%求传输它的最佳前缀码。（8分）一、填空10%（每小题2分）1、1，不存在；2、e；3、Gba,有)*(*)*()*(*)*(bbaababa；4、1e2e3e4e5e1v111002v-100013v0-101-14v00-1-105、它不包含与K3,3或K5在2度结点内同构的子图。二、选择10%（每小题2分）题目12345答案A，DBCDA三、判断10%题目12345答案YYNNN离散数学试卷（十三）85四、证明38%1、（8分）证明：（1）设Acba,,，b是a的右逆元，c是b的右逆元，由于bebbab*)*(*，abeabcbabcbabcbe**)*()*(*)*(*)*(**所以b是a的左逆元。（2）设元素a有两个逆元b、c，那么ccecabcabebb**)*()*(**a的逆元是唯一的。2、（12分）证明：[乘]，A，，上封闭在运算☆在A上也封闭。[群]Acba,,)()()()()(:)()()()()))()((()()())()(()()())()(()))()((())()(()(cbacbacbacbacbacbacbacbacbacbabacbacbacbabacbacbacbabacbabacbabacba☆☆同理可得☆☆☆)()(cbacba☆☆☆☆即☆满足结合性。[幺]Aa,aaaaaaa0)1(0)0()0(00☆☆故全下界0是A中关于运算☆的幺元。[逆]Aa,000)()()(aaaaaa☆即A中的每一个元素以其自身为逆元。[交]abababbababa☆☆)()()()(即运算☆具有可交换性。所以A,☆是Abel群。3、(10分)证明:设,,A是一环,且,,)(Af是关于同态映射f的同态象。离散数学试卷（十三）86由,A是Abel群，易证,)(Af也是Abel群。,A是半群，易证,)(Af也是半群。现只需证：对是可分配的。3,2,1,)(:,,),(,,321321ibafaaaAfbbbii使得则必有相应的于是)()())()(())()(()()())()(())(())(()())()(()()(3121312131213121321321321321bbbbafafafafaafaafaaaafaaafaafafafafafbbb同理可证)()()(1312132bbbbbbb因此,,)(Af也是环。5、（8分）证明：设G有r个面，kerkrerikreririi22)1()deg(,2)deg(1即而2)2(22,2kvkekrevrev即故而。五、应用32%1、（8分）解：)(G即为最少考试天数。用Welch-Powell方法对G着色：685421739vvvvvvvvv第一种颜色的点6419vvvv，剩余点85273vvvvv第二种颜色的点573vvv，剩余点82vv第三种颜色的点82vv所以)(G≤3任932vvv构成一圈，所以)(G≥3故)(G=3所以三天下午即可考完全部九门课程。离散数学试卷（十三）872、（8分）解：0010100001011100)(GAi1：A[2，1]=1，0010100011011100A；i2：A[4，2]=1，1111100011011100Ai3：A[1，3]=A[2，3]=A[4，3]=1，1111100011011100Ai4：A[k，4]=1，k=1，2，3，4，1111111111111111Ap中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。3、（8分）解：用a,b,c,d,e,f,g7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为此图中的Hamilton回路即是圆桌安排座位的顺序。Hamilton回路为abdfgeca。4、（8分）解：(1)离散数学试卷（十三）8883282729354342)(TW（1）用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e传输它们的最优前缀码为{0000，0001，001，01，10，11}。