离散数学模拟题及答案.doc

（ 密 封 线 内 不 答 题 ） 教学中心： 专业层次： 姓名： 学号： 座号： 华南理工大学网络教育学院 教学中心： 专业层次： 姓名： 学号： 座号： 20142015学年度第一学期期末考试 离散数学 试卷（模拟题）教学中心： 专业层次： 学 号： 姓 名： 座号： 注意事项：1. 本试卷共 三 大题，满分100分，考试时间90分钟，闭卷；2. 考前请将以上各项信息填写清楚； 3. 所有答案直接做在试卷上,做在草稿纸上无效； （ 密 封 线 内 不 答 题 ） 4考试结束，试卷、草稿纸一并交回。 题 号一二三总分评分人得 分一、单项选择题（本大题30分，每小题6分）题 号12345答 案1. A1101110 B中国人民是伟大的。C全体起立！ D计算机机房有空位吗？在上面句子中，是命题的是( )2设Q（x）：x 是有理数，R（x）：x是实数。命题“某些实数是有理数”在谓词逻辑中的符号化公式是( )A（x）（Q（x） R（x） B（x）（Q（x）R（x）C（$x）（Q（x） R（x） D（$ x）（Q（x） R（x）3. 对于集合1, 2, 3，下列关系中不等价的是( )AR=，, BR=,CR=,DR=, ,4设A=1，2，3，4，5，B=a，b，c，d，e，以下哪个函数是从A到B的双射函数( )AF =，BF=，CF =， DF=，5下列判断不正确的是( )A 关于普通加法构成群 B 关于普通乘法构成独异点C所有实数对关于运算，其中构成群D实数集R关于运算构成半群，其中二、判断题（本大题20分，每小题4分）1、命题公式 p(pq) 是重言式。 （ ）2、 （x）A（x） B）（$x）（A（x） B）。 （ ）3、设A=a, b, c, R AA且R=, 则R是传递的。 （ ）4、n阶无向完全图Kn的每个顶点的度都是n。 （ ）5、根树中除一个结点外，其余结点的入度为1。 （ ）三、解答题（计算或者证明题：本大题50分，每小题10分）1设命题公式为 Q （P Q） P。 （1）求此命题公式的真值表；（2）求此命题公式的析取范式；（3）判断该命题公式的类型。2用直接证法证明：前提：（x）（C（x） W（x）R（x），（$x）（C（x）Q（x）结论：（$x）（Q（x）R（x）。3设R是集合A = 1, 2, 3, 4, 6, 12上的整除关系。(1) 给出关系R；（2） 给出COV A（3） 画出关系R的哈斯图；（4） 给出关系R的极大、极小元、最大、最小元。 4如图所示带权图，用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值。 5、设字母在通讯中出现的频率为：，。试给出传输这6个字母的最佳前缀码？问传输1000个字符需要多少位二进制位？参考答案：一、B D B B D，二、三、1、解 （1） 真值表如下PQQPQ Q （P Q） P Q （P Q） P0011111010101110100011101001（2） Q （P Q） P（ Q （P Q） P（ Q （P Q） P（P Q）（ Q P）1（析取范式）（PQ）（PQ）（PQ）（PQ）（主析取范式）（3）该公式为重言式2、证 (1)（$x）（C（x）Q（x） P (2)C（c）Q（c） ES (1)(3)（x）（C（x） W（x）R（x） P (4) C（c） W（c）R（c） US(3) (5) C（c） T(2)I(6)W（c）R（c） T(4,5)I (7)R（c） T(6)I (8)Q（c） T(2)I (9)Q（c）R（c） T(7,8)I (10) （$x）（Q（x）R（x） EG(9)3、解 R=,，,，,IACOV A=,，作哈斯图如右：极小元和最小元为1；极大元和最大元为124、解5、解 先求传输100个字符所需要的位数。是依照出现频率得出的个