《2022年离散数学试卷八试题与答案 .docx》由会员分享，可在线阅读，更多相关《2022年离散数学试卷八试题与答案 .docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品_精品资料_试卷八试卷与答案一、 填空 15% （每道题 3 分）1、 n 阶完全图 K n 的边数为.2、 右图的邻接矩阵A= .3、 图的对偶图为.4、 完全二叉树中,叶数为nt,就边数 m= .5、 设 为代数系统, * 运算如下：可编辑资料 - - - 欢迎下载精品_精品资料_*abca abcb bacc ccc就它的幺元为.零元为.a、b、c 的逆元分别为.二、 挑选 15% （每道题 3 分）可编辑资料 - - - 欢迎下载精品_精品资料_1、 图相对于完全图的补图为（）.可编辑资料 - - - 欢迎下载精品_精品资料_2、 对图 G就 k G,G ,G 分别为（）.可编辑资
2、料 - - - 欢迎下载精品_精品资料_A 、2、2、 2. B 、1、1、2. C、2、1、2. D、1、2、 2 .3、 一棵无向树 T 有 8 个顶点, 4 度、 3 度、 2 度的分枝点各1 个,其余顶点均为树叶,就 T 中有（）片树叶.A 、3. B、4. C、5. D、6可编辑资料 - - - 欢迎下载精品_精品资料_4、 设 是代数系统,其中+,为一般的加法和乘法,就A= （）时 是整环.可编辑资料 - - - 欢迎下载精品_精品资料_A 、 x | x2 n,nZ . B、 x | x2 n1, nZ .可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢
3、迎下载精品_精品资料_C、 x | x0,且xZ . D、 x | xab 4 5,a, bR .可编辑资料 - - - 欢迎下载精品_精品资料_5、 设 A=1 , 2, 10 ,就下面定义的运算 * 关于 A 封闭的有（）.可编辑资料 - - - 欢迎下载精品_精品资料_A 、x*y=maxx ,y . B、x*y= 质数 p 的个数使得 xpy .可编辑资料 - - - 欢迎下载精品_精品资料_C、x*y=gcdx , y . gcd x ,y 表示 x 和 y 的最大公约数 . D、x*y=lcmx ,y（ lcmx ,y 表示 x 和 y 的最小公倍数）.三、 证明 45%n 2m可
4、编辑资料 - - - 欢迎下载精品_精品资料_1、设 G 是（ n,m）简洁二部图,就4.（ 8 分）可编辑资料 - - - 欢迎下载精品_精品资料_2、设 G 为具有 n 个结点的简洁图,且m 1 n 21 n2就 G 是连通图.（ 8 分）可编辑资料 - - - 欢迎下载精品_精品资料_3、设 G 是阶数不小于11 的简洁图,就G 或G 中至少有一个是非平图.（14 分）4、记“开”为1,“关”为 0,反映电路规律的代数系统0 , 1 , +, 的加法运算和乘法运算.如下：+0101001000110101证明它是一个环,并且是一个域.（15 分）四、 生成树及应用 10%1 、（ 10
5、分）如下图所示的赋权图表示某七个城市可编辑资料 - - - 欢迎下载精品_精品资料_v1, v2 ,v7 及预先测算出它们之间的一些直接通信线路可编辑资料 - - - 欢迎下载精品_精品资料_造价,试给出一个设计方案,使得各城市之间既能够通信而且总造价最小.2、（ 10 分）构造 H、A 、P、N 、E、W、R、对应的前缀码,并画出与该前缀码对应的二叉树,写出英文短语HAPPY NEW YEAR的编码信息.可编辑资料 - - - 欢迎下载精品_精品资料_五、 5%对于实数集合R,在下表所列的二元远算是否具有左边一列中的性质,请在相应位上填写“Y ”或“ N”.可编辑资料 - - - 欢迎下载精
6、品_精品资料_可结合性可交换性存在幺元存在零元MaxMin+可编辑资料 - - - 欢迎下载精品_精品资料_答案：0101001101000110一、填空 15% （每道题 3 分）可编辑资料 - - - 欢迎下载精品_精品资料_c, a、b、没有11、 2nn1. 2 、. 3 、. 4 、2nt1 . 5、 a,可编辑资料 - - - 欢迎下载精品_精品资料_二、挑选 15% （每道题 3 分）题目12345A ,答案AACDC三、证明 45%1、 （8分）：设G=（V,E）,可编辑资料 - - - 欢迎下载精品_精品资料_VXY , Xn1, Yn2, 就n1n2n可编辑资料 - - -
7、 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_mn1n2n1 nn1n21n1n n12n 2n可编辑资料 - - - 欢迎下载精品_精品资料_对完全二部图有24nnn 2当 12 时,完全二部图n , m 的边数 m 有最大值 4 .n 2可编辑资料 - - - 欢迎下载精品_精品资料_故对任意简洁二部图 n , m 有 m4 .可编辑资料 - - - 欢迎下载精品_精品资料_2、 （8 分）反证法：如G 不连通,不妨设G 可分成两个连通分支G1、G2,假设G1 和 G2 的顶点数分别为 n1 和 n2,明显 n1n2n .n11n21n1n1n2n1可编辑资料
8、- - - 欢迎下载精品_精品资料_n1n11n2 n21n1n1n22 n1 n22222m可编辑资料 - - - 欢迎下载精品_精品资料_与假设冲突.所以G 连通.3、（ 14 分）（ 1）当 n=11 时, GGK 11mK 11 边数1110255条,因而必可编辑资料 - - - 欢迎下载精品_精品资料_有 G 或 G 的边数大于等于 28,不妨设 G 的边数 m28 ,设 G 有 k 个连通分支,就 G中必有回路.（否就G 为 k 棵树构成的森林,每棵树的顶点数为ni,边数mi,就可编辑资料 - - - 欢迎下载精品_精品资料_mini1, ikni1k ,i 1kn 11,mimi
9、 1可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_k28mmi i 1kni1i 1nk11k冲突）可编辑资料 - - - 欢迎下载精品_精品资料_下面用反证法证明G 为非平面图.假设 G 为平面图,由于G 中有回路且G 为简洁图,因而回路长大于等于3 .于是 G可编辑资料 - - - 欢迎下载精品_精品资料_的每个面至少由g g得：3 条边围成,由点、边、面数的关系mgn g2k1,可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_28mg11g2k1311k311311113113227可编辑资
10、料 - - - 欢迎下载精品_精品资料_而 2827 冲突,所以 G 为非平面图.可编辑资料 - - - 欢迎下载精品_精品资料_（ 2）当 n11 时,考虑 G 的具有 11 个顶点的子图G ,就G 或 G 必为非平面图.可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_假如 G假如 G为非平面图,就G 为非平面图.为非平面图,就G 为非平面图.可编辑资料 - - - 欢迎下载精品_精品资料_4、 （ 15 分）1） 0 ,1 , +, 是环 0 ,1 , + 是交换群乘：由“ +”运算表知其封闭性.由于运算表的对称性知：+运算可交换.群：（ 0
11、+0 ） +0=0+ （ 0+0 ）=0 .（ 0+0） +1=0+ （ 0+1 ） =1.（ 0+1） +0=0+ （ 1+0 ） =1 .（ 0+1） +1=0+ （ 1+1 ） =0.（ 1+1） +1=1+ （ 1+1 ） =0 结合律成立.幺：幺元为 0.逆： 0, 1 逆元均为其本身.所以,是 Abel 群.可编辑资料 - - - 欢迎下载精品_精品资料_ 是半群乘：由“”运算表知封闭群： 00 0=0 （ 0 0） =0 .（ 0 0） 1=0 （ 0 1）=1.（ 01） 0=0（ 10） =1 .（ 0 1） 1=0 （ 1 1） =0.（ 11） 1=1（ 11） =0 .
12、对 +的安排律可编辑资料 - - - 欢迎下载精品_精品资料_对 x, y 0,1可编辑资料 - - - 欢迎下载精品_精品资料_ 0（ x+y ）=0=0+0=0 x+0 y 1（ x+y ）当 x=yx+y=0就可编辑资料 - - - 欢迎下载精品_精品资料_1 x00y1 00111 01 11 01 11 x1 y可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_当 xy （ xy1 ）就101 11 0可编辑资料 - - - 欢迎下载精品_精品资料_1 xy1 11011 01 11 x1 y可编辑资料 - - - 欢迎下载精品_精品资料
13、_可编辑资料 - - - 欢迎下载精品_精品资料_所以x, y, z 0,1 均有 z xy z x zy可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_同理可证： xy zxz yz可编辑资料 - - - 欢迎下载精品_精品资料_所以对 + 是可安排的.由得, 是环.（ 2）是域由于 是有限环,故只需证明是整环即可.乘交环：由乘法运算表的对称性知,乘法可交换.含幺环：乘法的幺元是1无零因子： 1 1=1 0因此 0 , 1 ,+, 是整环,故它是域.四、 树的应用 20%1、（ 10 分）解：用库斯克（ Kruskal ）算法求产生的最优树.算
14、法略.结果如图：可编辑资料 - - - 欢迎下载精品_精品资料_树权 CT=23+1+4+9+3+17=57即为总造价五、 （ 10 分）由二叉树知H 、A 、P、Y 、N 、E、W、 R 对应的编码分别为000、001、010、011、100、 101、 110、111.明显 000 , 001, 010,011, 100, 101, 110, 111 为前缀码.英文短语 HAPPY NEW YEAR的编码信息为000 001 010 010 011 100 101 001 001 101 001 111六、 5%MaxMin+可结合性YYY可交换性YYY存在幺元NNY存在零元NNN可编辑资料 - - - 欢迎下载