华南农业大学 离散数学 期末考试2012试卷 2013-01-08 作者： 日期：华南农业大学期末考试试卷（A卷）2012-2013学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间：120 分钟学号 姓名 年级专业 题号一二三四总分得分评阅人考试注意事项： 本试题分为试卷与答卷2部分。试卷有四大题，共6页。所有解答必须写在答卷上，写在试卷上不得分。得分一、选择题（本大题共 25 小题，每小题 2 分，共 50 分）1、矛盾式的否定是_。A、重言式 B、矛盾式 C、可满足式 D、 A-C均有可能2、个体域为全体人类，：是的最好朋友；则命题“每个人恰有一个最好的朋友。”可表示为_。A、 B、C、 D、3、甲乙丙丁四人的车分别为白色、银色、蓝色和红色。在问到他们各自车的颜色时，甲说：“乙的车不是白色的”。乙说：“丙的车是红色的”。丙说：“丁的车不是蓝色的”。丁说：“甲、乙、丙三人中有一个人的车是红色的，而且只有这个人说的是真话”。如果丁说的是实话，那么以下说法正确的是：A、甲的车是白色的，乙的车是银色的B、乙的车是蓝色的，丙的车是红色的C、丙的车是白色的，丁的车是蓝色的D、丁的车是银色的，甲的车是红色的4、甲、乙和丙，一位是山东人，一位是河南人，一位是湖北人。现在只知道：丙比湖北人的年龄大，甲和河南人不同岁，河南人比乙年龄小。由此可以推知下列说法正确的是_。A、甲不是湖北人 B、河南人比甲年龄小C、河南人比山东人年龄大 D、湖北人年龄最小5、某市要建花园或修池塘，有下列4种假设：修了池塘要架桥；架了桥就不能建花园；建花园必须植树；植树必须架桥。据此不可能推出的是：A、最后有池塘 B、最后一定有桥C、最后可能有花园 D、池塘和花园不能同时存在6、设 p:他主修计算机科学, q:他是新生，r:他可以从校园内访问因特网，下列命题“除非他主修计算机科学，否则只要他是新生就不可以从校园内访问因特网。”可以符号化为_。DA、 B、C、 D、7、下列说法不正确的是：_。A、是自反的，则一定是自反的B、是反自反的，则一定是反自反的C、是对称的，则一定是对称的D、是传递的，则一定是传递的8、下列关于关系的等式不成立的是_。A、B、C、D、9、设，定义A上的关系，则R具有的性质为_。A、自反的 B、对称的 C、传递的，对称的 D、传递的10、设和定义在上，是所有人的集合，是的父亲，是的母亲，则关系是的外祖母的表达式是：_。A、 B、 C、 D、11、在5元素集合上有_个不同的等价关系恰有3个不同的等价类。A、25 B、21 C、 10 D、612、设，是中的字符构成的长度不超过4的串的集合，即，其中表示空串，在上定义偏序关系：，是的前缀，则的最小元是：_。A、 B、0 C、 D、不存在13、设，*表示求两个数的最小公倍数的运算，则对于*运算的幺元是_。A、0 B、1 C、 任意值 D、不存在14、设R是实数集合，“”为普通乘法，则代数系统 是_。A、群 B、阿贝尔群 C、半群 D、含幺半群15、非同构的无向的4阶自补图有_个。A、0 B、1 C、 2 D、316、在一棵树中有7片树叶，3个3度结点，其余都是4度结点，则该树有_个4度结点。A、1 B、2 C、3 D、417、设是代数系统，为模6加法运算，则2-5= _。A、10 B、1/10 C、4 D、218、给定下列各序列，可以构成无向简单图的度数序列为_。A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,519、具有6 个顶点，12条边的连通简单平面图中，次数为3的面有_个。A、5 B、 6 C、 7 D、 820、设A=，1，1，3，1，2，3则A上包含关系“”的哈斯图为_。A、 B、C、D、 21、以下无向图中，不是二部图的是_。 A、 B、C、D、 22、下图中既不是欧拉图，也不是哈密尔顿图的是_。A、 B、C、D、 23、以下无向图中，不是平面图的是_。 A、 B、C、D、 24、由0、1、2、3这四个数字能构成_个3位数。 A、64 B、48 C、24 D、1825、四个人比赛，名次允许并列，则有_种比赛结果。 A、256 B、72 C、75 D、24得分1.5CM二、计算题：（本大题共 5 个小题，每题 5 分，共 25 分）1、设A=1, 2, 3, 4，R=|xA，yA且x-y1，-为普通减法（1）写出R的集合表达式和关系矩阵，画出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、如下图所示的赋权图表示某七个城市 ，及预先算出它们之间直接通信线路造价(以百万元为单位)，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。V1V2V3V4V5V6135246789V7104、通过并行的执行某些语句，计算机程序可以执行得更快。语句与前面语句的相关性可以表示成有向图，用顶点表示每条语句，请画出语句执行顺序图。例如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 55 5、求下面带权图中到其它顶点的最短路径及对应的权。65ceaz12743432gdfb 得分三、证明题：（6+5+5+5，共 21 分）1、构造下面推理的证明。前提：，结论：2、证明一个关系的对称闭包的自反闭包和它的自反闭包的对称闭包是相同的，即，其中，分别表示关系的自反闭包和传递闭包。3、设阶条边的无向图中，证明中存在顶点：3。4、若是群，定义G中的运算“”为：，对证明为含幺半群。得分四、应用题（共4分，任选一题，多选不加分）1、一个商人骑一头驴要穿越1000公里长的沙漠，去卖3000根胡萝卜。已知驴一次性可驮1000根胡萝卜，但每走1公里又要吃掉1根胡萝卜。问：商人最多可卖出多少胡萝卜？(4分)2、一个多米诺骨牌是一个由两个正方体组成的长方体，每个正方体上用数字0，1，6标注，一套多米诺骨牌如下图所示。一个多米诺骨牌的两个正方体上可以有相同的数字，请说明一套多米诺骨牌可以放在一个回路里，并且相邻两张骨牌连接处数字相同。(4分)解： （1）R的集合表达式： R的关系图： R的关系矩阵: 2134 （2）R的自反闭包r(R)关系图： 对称闭包s(R)关系图： 2134 2134 传递闭包t(R)关系图：2134解：首先将各边的权重按小到大排序：1,2,3,4,5,6,7,8,9,10然后使用避圈法得到如下最小生成树，其总权重为1+2+4+6+8+10=31V1V2V3V4V5V612468V710华南农业大学期末考试参考答案（A卷）2012-2013学年第 一 学期 考试科目： 离散结构 得分一、选择题（本大题共 25 小题，每小题 2 分，共 50 分）1A2D3C4D5C6D7B8B9B10C11A12A13B14D15B16A17D18B19D20C21C22B23D24B25B得分1.5CM二、计算题：（本大题共 5 个小题，每题 5 分，共 25 分）1、解： （1）R的集合表达式： R的关系图： R的关系矩阵: 2134 （2）R的自反闭包r(R)关系图： 对称闭包s(R)关系图： 2134 2134 传递闭包t(R)关系图：21342、 解：(1)用Huffman算法求以频率(乘以100)为权的最优2元树. 将权按小到大顺序排列：wg=5,wf=5,w