华南农业大学离散数学期末考试试卷

1、华南农业大学 离散数学 期末 考试 2012 试卷 2013-01-08作者:日期:华南农业大学期末考试试卷（A卷）20122013学年第 一 学期考试科目:离散结构考试类型：（闭卷）考试考试时间：120 分钟得分D、A-C均有可能学号 姓名 年级专业题号A四总分得分评阅人考试注意事项:本试题分为试卷与答卷2部分。试卷有四大题，共6页。 所有解答必须写在答卷上，写在试卷上不得分。一、选择题（本大题共25小题,每小题2分，共50分）1、矛盾式的否定是OA、重言式 B、矛盾式 C、可满足式2、个体域为全体人类，是工的最好朋友；则命题“每个人恰有一个最好的朋友J可表示为 oA Vx寺(8(x,y)B

2、、y)C、V,自归z(8(尤 y)(z 工 y) a -£(x, z)D、Vx3yVz(B(x, y) A(y W z) - -18(3 z)3、甲乙丙丁四人的车分别为白色、银色、蓝色和红色。在问到他们各自车的颜色时，甲说：“乙的车不是白色的工乙说：“丙的车是红色的二丙说：“丁的车 不是蓝色的二丁说：“甲、乙、丙三人中有一个人的车是红色的，而且只有这个人说的是真话”。如果丁说的是实话，那么以下说法正确的是:A、甲的车是白色的,乙的车是银色的B、乙的车是蓝色的，丙的车是红色的 C、丙的车是白色的，丁的车是蓝色的 D、丁的车是银色的，甲的车是红色的4、甲、乙和丙，一位是山东人，一位是河南

3、人，一位是湖北人。现在只知道： 丙比湖北人的年龄大，甲和河南人不同岁，河南人比乙年龄小。由此可以推知 下列说法正确的是oA、甲不是湖北人B、河南人比甲年龄小C、河南人比山东人年龄大D、湖北人年龄最小5、某市要建花园或修池塘，有下列4种假设：修了池塘要架桥；架了桥就不能 建花园；建花园必须植树；植树必须架桥。据此不可能推出的是：A、最后有池塘B、最后一定有桥C、最后可能有花园D、池塘和花园不能同时存在6、设p:他主修计算机科学他是新生，r.他可以从校园内访问因特网，下列 命题“除非他主修计算机科学，否则只要他是新生就不可以从校园内访问因特 网。”可以符号化为 o DA、 /? a -q >

4、rB、 一夕C、八r fD、p Aqff7、下列说法不正确的是：。A、R是自反的，则正一定是自反的B、R是反自反的，则史一定是反自反的C、R是对称的，则史一定是对称的D、R是传递的，则* 一定是传递的8、下列关于关系的等式不成立的是。A、（F oG）。H = Fo（G。H）B、（FoG）-, =F-,oG-,C、（FnG）oHc（FoH）n（GoH）D、（/UG）oH=（/。H）U（G。"）9、设4 = 1,2,3,.10,定义 A 上的关系£ = vx,y>lx,ywS人x+y = 10,则 R 具有的性质为 OA、自反的 B、对称的 C、传递的，对称的 D、传递的

5、10、设R和S定义在尸上，尸是所有人的集合，R =是），的父亲, S =八4是y的母亲,则关系 vx,y >lx,y eP人y是的工外祖母的表达式是：OA、S-loS B、RoS C、5_1oS_1D、SoR11、在5元素集合上有 个不同的等价关系恰有3个不同的等价类。A、25B、21C、 10D、612、设5 = 0,1,尸是S中的字符构成的长度不超过4的串的集合，即尸=40,1,00,01,1111,其中2表示空串，在尸上定义偏序关系R： Vx,yeF, vx,y>eRox是），的前缀，则vE,R>的最小元是：。A、4B、0C、0,1,2D、不存在13、设Z+=xlxtZ

6、八x>。, *表示求两个数的最小公倍数的运算，则对于*运 算的幺元是。A、0 B、1C、 任意值D、不存在14、设R是实数集合，“x”为普通乘法，则代数系统vR , x>是。A、群 B、阿贝尔群 C、半群D、含幺半群15、非同构的无向的4阶自补图有 个。A、0 B、1C、2D、316、在一棵树中有7片树叶，3个3度结点，其余都是4度结点，则该树有 个4度结点。A、1B、2C、3D、417、设 <26,是代数系统，Z。=0,123,4,5,为模6加法运算，则2-5=。A、10B、1/10C、4D、218、给定下列各序列，可以构成无向简单图的度数序列为。A、1,122,3B、1,

7、1,233C、0,1,133D、134,4,519、具有6个顶点，12条边的连通简单平面图中，次数为3的面有 个。A、5B、6C、7D、820、设人=，1), 1, 3, 1, 2, 3则A上包含关系的哈斯图为A、B、C、D、23、以下无向图中，不是平面图的足24、由0、1、2、3这四个数字能构成 个3位数。A、64B、48C、24D、1825、四个人比赛,名次允许并列，则有种比赛结果。A、256B、72D、24得分二、计算题：（本大题共5个小题，每题5分，共25分） 1、设人=1,2,3,4, R=<x, y>lxeA, yeA且x-y>l,-为普通减法（1）写出R的集合表

8、达式和关系矩阵，画出R的关系图。（2分）（2）画出关系R的自反闭包r（R）、对称闭包s（R）、传递闭包t（R）0 （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、如下图所示的赋权图表示某七个城市匕,匕,吃 ,及预先算出它们之间直 接通信线路造价（以白万元为单位），试给出一个设计方案，使得各城市之间能够 通信而且总造价最小，并计算出最小造价。4、通过并行的执行某些语句，计算机程序可

9、以执行得更快。语句与前面语句 的相关性可以表示成有向图，用顶点表示每条语句，请画出语句执行顺序 图。例如s2 一定在si后才能执行，就画一条由si指向s2的有向边。sl:x=0s2:x=x+ls3:y=2s4: z=ys5:x=x+2s6:y=x+zs7:z=45、求下面带权图中。到其它顶点的最短路径及对应的权。得分三、证明题：(6+5+5+5,共21分)1、构造下面推理的证明。前提：p f (q f s) , q t p v i/-结论：rf s2、证明一个关系R的对称闭包的自反闭包和它的自反闭包的对称闭包是相 同的，即r(s(R) = s("R)，其中/(/?) , 5(7?)分

10、别表示关系R的自反闭包和传递闭包。3、设阶加条边的无向图G中，7 = ” + 1,证明G中存在顶点y ： 4(0 23。4、若vG,*是群，定义G中的运算"”为：tzAZ? = a*u1 *b ,对证明GJ为含幺半群。得分四、应用题(共4分，任选一题，多选不加分)1、一个商人骑一头驴要穿越1000公里长的沙漠，去卖3000根胡萝卜。已知驴 一次性可驮1000根胡萝卜，但每走1公里乂要吃掉1根胡萝卜。问：商人最多 可卖出多少胡萝卜？(4分)2、一个多米诺骨牌是一个由两个正方体组成的长方体，每个正方体上用数字0, 1,，6标注，一套多米诺骨牌如下图所示。一个多米诺骨牌的两个正方体上 可以

11、有相同的数字，请说明一套多米诺骨牌可以放在一个回路里，并且相邻两 张骨牌连接处数字相同。(4分)R的关系图：(2) R的自反闭包！'(R)关系图：R的关系矩阵：Fo o o o ,/aoooo10 0 0 110 0对称闭包S(R)关系图：解：(1) R的集合表达式：R = v3>,v4>,v4,2>传递闭包t(R)关系图:解：首先将各边的权重按小到大排序:然后使用避圈法得到如下最小生成树,1,2,3,45678910其总权重为1+2+4+6+8+10=31华南农业大学期末考试参考答案(A卷)2012-2013学年第一学期考试科目:散结构得分一、选择题（本大题共25小

12、题，每小题2分，共50分）1A2D3C4D5C6D7B8B9B10C11A12A13B14D15B16A17D18B19D20C21c22B23D24B25B得分二、计算题：（本大题共5个小题，每题5分，共25分）1、解：（1） R的集合表达式：R = v3,l>,v4J>,v4,2>R的关系图:R的关系矩阵:0 00 01 01 10 00 00 00 0对称闭包s（R）关系图:（2） R的自反闭包r（R）关系图:传递闭包HR）关系图:2、解：用Huffman算法求以频率（乘以100）为权的最优2元树.将权按小到大顺序 排列：M'g=5，卬尸5 jiTc= 10.m

13、i= 10.vvc=l 5,m%=20j0=35 ,得到如下最优 2 兀树:(2)如上图所示，得到各字母的前缀码：a: 11 ,b:0l,c: 10Ld:100.e:001 J:0001 ,g:0000总权重W(T)=2553、解：首先将各边的权重按小到大排序：123,4,5,6,7,8910 然后使用避圈法得到如下最小生成树，其总权重为1+244+6+8+10=31g00 743occo000000143/a6900co0024/a6900co0036/c711co0047/d111200511/d1218612/e16716/g804367111216得分三、证明题：（6+5+5+5,共2

14、1分）1、证明：r （前提引入）pvf （前提）p（析取三段论）（前提）（夕-s）（假言推理）q （前提）s （假言推理）2、证明：对于任意A上关系R来说，都有=s（R） = R 2 R-i左边二r（R UR、=（Ru/?_,）u IA右边=s（Ru/八）= （/C o/人）（/? J/人）1=（Ru ）0 （1八）"2 R-' = （R 21J u IR 2 R-' = （R 2 R-）u I A=左边3、证：用反证法，假设不存在顶点度数大于等于3,则Vi，eV（G）,均有由 握手定理有：27 = 2（ + 1） = 2 + 2 =2"（匕）2，矛盾！所以

15、 G 中存在顶点 v： d（v）34、证明：（1）封闭性：对Va、b£GaAb=a*u1*bGG (利用*封闭性)结合席：VahcCG(aAb)Ac=(a*ud *b)Ac= a*u-1 *b*u/ *caA(bAc)=aA(b*u-I*c) = a*u"*b*u/*c所以(aZkb)Zkc= aA(bAc)(3)设二元运算*的单位元为e设二元运算的左右单位元为ei,er：VxGG:xAer=x=x*u"*e 尸 x =u"*er=e =>er=uVxGG:eiAx=x=>ei*ud*x=x nei*u4=e =>ei=u由单位元唯一性定理：二元运算的单位元u得分四、应用题(共4分，任选一题，多选不加分)1、解：3000根胡萝卜变成2000根胡萝卜，需要转运三次，两次返回，消耗1000根胡罗卜， 所以骆驼走了200公里，即第二次起运点在出发后200公里，此时只有2000根胡萝卜，需要 转运2次，一次返回，消耗1000根胡萝卜，第二次共行进1000/3公里，此时仅1000根胡萝卜 可直接运输出沙漠，需要消耗1000-200-1000/3根胡萝卜，所以剩余胡萝卜为： 1000- (1000-20