华南农业大学离散数学期末考试2012试卷20130108.pdf

《华南农业大学离散数学期末考试2012试卷20130108.pdf》由会员分享，可在线阅读，更多相关《华南农业大学离散数学期末考试2012试卷20130108.pdf（16页珍藏版）》请在三一文库上搜索。

1、华南农业大学离散数学期末 考试 2012 试卷 2013-01-08 D、)()()(HGHFHGF 9、设10,.,3,2, 1A，定义 A 上的关系10,|,yxSyxyxR，则 R 具有的性质为 _。 A、自反的B、对称的C、传递的，对称的D、传递的 10、设 R和 S定义在 P 上， P 是所有人的集合，RxPyxyx,|,是 y 的 父亲， SxPyxyx,|,是 y 的母亲 ，则关系 yPyxyx,|,是 的x外祖母 的表达式是： _。 A、SS 1 B、SRC、 11 SSD、RS 11、在 5 元素集合上有 _个不同的等价关系恰有3 个不同的等价类。 A、25 B、21 C、1

2、0 D、6 12、设1 ,0S， F 是 S中的字符构成的长度不超过4的串的集合，即 1111,.,01,00, 1 ,0 ,F，其中表示空串， 在 F 上定义偏序关系 R：Fyx,， xRyx,是 y 的前缀，则RF ,的最小元是： _。 A、B、0 C、, 1 ,0D、不存在 13、设0|xZxxZ，*表示求两个数的最小公倍数的运算，则对于*运 算的幺元是 _。 A、0 B、1 C、任意值D、不存在 14、设 R 是实数集合，“”为普通乘法，则代数系统 是_。 A、群B、阿贝尔群C、半群D、含幺半群 15、非同构的无向的 4阶自补图有 _个。 A、0 B、1 C、 2 D、3 16、 在一

3、棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点，则该树有 _ 个 4 度结点。 A、1 B、2 C、3 D、4 17、 设, 6 Z是代数系统，5 ,4,3 ,2 ,1 ,0 6 Z，为模6加法运算，则2 5= _。 1 装 订 线 A、10 B、1/10 C、4 D、2 18、给定下列各序列，可以构成无向简单图的度数序列为_。 A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,5 19、具有 6 个顶点， 12条边的连通简单平面图中，次数为3的面有 _个。 A、5B、 6C、 7D、 8 20、设A=，1，1，3，1，2，3则A上包含

4、关系“”的哈斯图为 _。 A、B、C、 D、 21、以下无向图中，不是二部图的是_。 A、B、C、 D、 22、下图中既不是欧拉图，也不是哈密尔顿图的是_ 。 A、B、C、 D、 2 装 订 线 23、以下无向图中，不是平面图的是_。 A、B、C、 D、 24、由0、1、2、3这四个数字能构成 _个3位数。 A、64 B、48 C、24 D、18 25、四个人比赛，名次允许并列，则有_种比赛结果。 A、256 B、72 C、75 D、24 二、计算题：（本大题共5 个小题，每题5 分，共 25 分） 1、设 A=1, 2, 3, 4，R=|x A，y A且x-y1，-为普通减法 （1）写出 R

5、的集合表达式和关系矩阵，画出R的关系图。（2分） （2）画出关系 R的自反闭包 r(R) 、对称闭包 s(R) 、传递闭包 t(R)。 （3分） 2、设有 7 个字母在通信中出现的频率(%) 如下： a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5% (1)以频率 (或乘 100)为权，求最优 2 元树。 （3 分） (2)利用所求最优 2元树找出每个字母的前缀码。 （2分） 3、如下图所示的赋权图表示某七个城市 721 ,VVV，及预先算出它们之间直 接通信线路造价 (以百万元为单位 )，试给出一个设计方案，使得各城市之间能 够通信而且总造

6、价最小，并计算出最小造价。 得分 1.5CM 3 装 订 线 4、通过并行的执行某些语句，计算机程序可以执行得更快。语句与前面语句 的相关性可以表示成有向图，用顶点表示每条语句，请画出语句执行顺序 图。例如 s2一定在 s1后才能执行，就画一条由s1指向 s2的有向边。 s1: x=0 s2: x=x+1 s3: y=2 s4: z=y s5: x=x+2 s6: y=x+z s7: z=4 5、求下面带权图中a到其它顶点的最短路径及对应的权。 三、证明题：（6+5+5+5，共 21 分） 1、构造下面推理的证明。 前提：)(sqp， q，rp 结论：sr 2、证明一个关系 R的对称闭包的自反

7、闭包和它的自反闭包的对称闭包是相 同的，即 )()(RrsRsr， 其中)(Rr，)(Rs分别表示关系 R的自反闭包和传递闭包。 3、设n阶m条边的无向图 G 中，1nm，证明 G 中存在顶点v：)(vd3。 4、若,G是群，Gu，定义 G 中的运算“”为：buaba 1 ，对 Gba, 证明,G为含幺半群。 得分 得分 V V V V V V 1 3 5 2 4 6 7 8 9 V 1 az 12 7 4 3 4 3 2 g dfb e 5 5 c 6 5 4 装 订 线 四、应用题（共 4 分，任选一题，多选不加分） 1、一个商人骑一头驴要穿越1000 公里长的沙漠， 去卖 3000根胡萝

8、卜。 已知驴 一次性可驮 1000 根胡萝卜， 但每走 1 公里又要吃掉 1 根胡萝卜。 问：商人最多 可卖出多少胡萝卜？ (4 分) 2、一个多米诺骨牌是一个由两个正方体组成的长方体，每个正方体上用数字 0， 1，6标注，一套多米诺骨牌如下图所示。一个多米诺骨牌的两个正方体上 可以有相同的数字，请说明一套多米诺骨牌可以放在一个回路里，并且相邻两 张骨牌连接处数字相同。(4分) 5 装 订 线 解： （1）R的集合表达式： 2,4,1 ,4,1 , 3R R的关系图：R的关 系矩阵 : （2）R的自反闭包 r(R)关系图：对称 闭包s(R)关系图： 传递闭包 t(R)关系图： 解 ： 首 先

9、将 各 边 的 权 重 按 小 到 大 排 序 ： 1,2,3,4,5,6,7,8,9,10 然后使用避圈法得到如下最小生成树，其总权 2134 21342134 2134 0011 0001 0000 0000 6 装 订 线 重为 1+2+4+6+8+10=31 华南农业大学期末考试参考答案（A卷） 2012-2013学年第一 学期考试科目：离散结构 一、选择题（本大题共25 小题，每小题2 分，共 50 分） 1 A 2 D 3 C 4 D 5 C 6 D 7 B 8 B 9 B 10 C 11 A 12 A 13 B 14 D 15 B 16 A 17 D 18 B 19 D 20 C

10、 21 C 22 B 23 D 24 B 25 B 二、计算题：（本大题共5 个小题，每题5 分，共 25 分） 1、解： （1）R的集合表达式： 2,4,1 ,4,1 , 3R R的关系图：R的关 系矩阵 : 得分 得分 V V V V V V 1 2 4 6 8 V 1 1.5CM 7 装 订 线 （2）R的自反闭包 r(R)关系图：对称 闭包s(R)关系图： 传递闭包 t(R)关系图： 2、解：(1)用 Huffman 算法求以频率 (乘以 100) 为权的最优 2 元树. 将权按小到大顺序排列： wg=5,wf=5,we=10,wd=10,wc=15,wb=20,wa=35.得 到如下

11、最优 2 元树： 2134 21342134 2134 0011 0001 0000 0000 8 装 订 线 (2) 如 上 图 所 示 ， 得 到 各 字 母 的 前 缀 码 ： a:11,b:01,c:101,d:100,e:001,f:0001,g:0000 总权重 W(T) 255 3 、解 ： 首 先 将 各 边 的 权 重 按 小 到 大 排 序 ： 1,2,3,4,5,6,7,8,9,10 然后使用避圈法得到如下最小生成树，其总权 重为 1+2+4+6+8+10=31 4、 V V V V V V 1 2 4 6 8 V 1 wg=5 wf=5 10 we=10 20 wd=1

12、0 wc=15 25wb=20 40 wa=35 60 100 0 1 0 0 0 0 0 1 1 1 1 1 9 装 订 线 5、 v r a b c d e f g z 0 0 4 3 1 4 3/a 6 9 2 4/a 6 9 3 6/c 7 11 4 7/d 11 12 5 11/d 12 18 6 12/e 16 7 16/g 8 0 4 3 6 7 11 12 16 三、证明题：（6+5+5+5，共 21 分） 1、证明： r （前提引入） rp （前提） p（析取三段论） )(sqp（前提） )(sq （假言推理） q（前提） 得分 10 装 订 线 s（假言推理） 2、证明：对

13、于任意 A上关系R来说，都有 A IRRr)(， 1 )(RRRs 左边= )( 1 RRr A IRR)( 1 右边= )( A IRs= 1 )()( AA IRIR 11 )()(RIIR AA= 1 )(RIIR AAA IRR)( 1 =左边 3、证：用反证法，假设不存在顶点度数大于等 于 3，则 2)(),(vdGVv均有，由握手定理有： nvdnnm i 2)(22) 1(22，矛盾！所以G 中存在顶 点 v：d(v)3 4、证明： (1)封闭性：对a,bG ab=a*u -1*bG (利用*封闭性 ) (2) 结合律：a,b,cG (ab)c=(a*u -1*b)c= a*u-

14、1*b*u-1*c a(bc)=a(b*u -1*c) = a*u-1*b*u-1*c 所以(ab)c= a(bc) (3)设二元运算 *的单位元为 e 设二元运算的左右单位元为el,er： xG:xer=x x*u -1*e r=x u -1*e r=e er=u xG:elx=x el*u -1*x=x el*u -1=e el=u 由单位元唯一性定理： 二元运算的单位元u 四、应用题（共 4 分，任选一题，多选不加分） 1、解：3000根胡萝卜变成 2000根胡萝卜，需要 转运三次，两次返回，消耗1000根胡罗卜，所 以骆驼走了 200公里，即第二次起运点在出发后 得分 11 装 订 线

15、 200公里，此时只有 2000根胡萝卜，需要转运 2 次，一次返回，消耗 1000根胡萝卜，第二次共 行进1000/3 公里，此时仅 1000根胡萝卜可直接 运输出沙漠，需要消耗 1000-200-1000/3 根胡萝 卜，所以剩余胡萝卜为： 1000-（1000-200-1000/3 ）=200+1000/3 533根 2、解：用一个图 G 来描述这个问题。图 G 有7个 顶点，分别用 0，1，2, ,6 来标注。边代表多 米诺骨牌：在每一对不同的定点之间存在一条 边，每个顶点上有一个回路。 注意到 G 是连通的。 现在不同的多米诺骨牌可以放在一个回路里， 并且相邻的立方体有不同的数字当且仅当G 中 存在一个欧拉回路。由于每个顶点的度数是8， 所以每个顶点有偶数度。根据欧拉图判定定理， G 中存在一个欧拉回路。因此，不同的多米诺骨 牌可以当在一个回路里，并且相邻的立方体有 不同的数字。