《离散数学(本)2016年10月份试题汇编》由会员分享，可在线阅读，更多相关《离散数学(本)2016年10月份试题汇编（45页珍藏版）》请在金锄头文库上搜索。
1、离散数学（本）2016年10月份试题一、单项选择题（每小题3分，本题共15分）1若集合A1,2,3,4，则下列表述不正确的是 ( ) A1A B1,2,3AC1,2,3A D A2设A1, 2, 3，B=1, 2, 3, 4，A到B的关系Rx, y|x=y，则R为 ( ) A. , B. , , , , C. , D. , , 3无向图G的边数是10，则图G的结点度数之和为（ ） A. 10 B. 20 C. 30 D. 54设连通平面图G有v个结点，e条边，r个面，则（ ）Ar + v - e =2 Bv + e - r=4 Cv + e r = 4 Dv + e - r=25设个体域D是整
2、数集合，则命题x$y (x = y+2)的真值是（ ）A. 不确定 B. T C. 由y的取值确定 D. F 二、填空题（每小题3分，本题共15分）6设集合A=a, b, c，B=b, c, d ，C=c, d, e，则(BC) A等于 7设A=2, 3，B=1, 2，C=3, 4，从A到B的函数f=, ，从B到C的函数g=, ，则Dom(g f)等于 8若图G=，其中V= a, b, c, d ，E= (a, b), (a, d), (b, c), (b, d)，则该图中的割边为 9设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6，则在G -S中的连通分支数不超过 10设个体域D
3、1,2, 3, 4，A(x)为“x小于10”，则谓词公式(x)A(x)的真值为 三、逻辑公式翻译（每小题6分，本题共12分）11将语句“小明是学生，小张是飞行员”翻译成命题公式 12将语句“当大家都进入教室，则讨论会开始进行”翻译成命题公式 四、判断说明题（判断各题正误，并说明理由每小题7分，本题共14分）13空集的幂集是空集14(x)(P(x)Q(y)R(z)中的约束变元有x与y五计算题（每小题12分，本题共36分）15设A=1, 2, 3，R=|xA，yA且x+y=4，S=|xA，yA且x=y，试求R，S，R-1，r(S)16图G=，其中V= a, b, c, d, e ，E= (a, b
4、), (a, c) , (a, d), (b, c) , (b, d) , (c, d) , (c, e) , (d, e)，对应边的权值依次为2、3、4、5、6、7，6及2，试（1）画出G的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值17试画一棵带权为1, 2, 4, 5, 6的最优二叉树,并计算该最优二叉树的权 六、证明题（本题共8分）18试证明：PQ P（ (PQ)）离散数学（本）2016年10月份试题参考解答一、单项选择题（每小题3分，本题共15分）1C 2D 3B 4A 5B二、填空题（每小题3分，本题共15分）6d72，38(b, c)9610真（或T，或1）
5、三、逻辑公式翻译（每小题6分，本题共12分）11设P：小明是学生， Q：小张是飞行员 （2分） 则命题公式为： PQ （6分）12设P：大家都进入教室， Q：讨论会开始进行 （2分）则命题公式为：PQ （6分）四、判断说明题（每小题7分，本题共14分）13错误 （3分）空集的幂集不为空，为 （7分）14错误 （3分）约束变元仅有x （7分）五计算题（每小题12分，本题共36分）15解：R=, （3分）S=, （6分） R-1=, （9分）r(S)= , （12分）说明：对于每一个求解项，如果基本求出了解，可以给对应1分16解：（1）G的图形表示为： （3分）（2）邻接矩阵： （6分）（3）粗线
6、表示的图是最小生成树， （10分）权值为11 （12分）ooooooooo1256347111817解： （10分）权为13+23+42+52+62=39 （12分）六、证明题（本题共8分）18证明：（1）PQ P （1分）（2）P P（附加前提） （3分）（3）Q T（1）（2）I （5分）（4）PQ T（2）（3）I （6分）（5） (PQ) T（4）E （7分）（6）P (PQ) CP规则 （8分）另证：设P（ (PQ)）为F， （1分）则P为T， (PQ)为F， （3分）即PQ为F （4分）所以P为T，Q为F ， （5分）从而PQ也为F （6分）所以PQP( (PQ) （8分）说明：1
7、、因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分。另，可以用真值表验证。离散数学（本）2016年7月份试题一、单项选择题（每小题3分，本题共15分）1若集合A1,2,3,4，B1,3,5，则下列表述正确的是 ( ) AAB BB ACB A DB A2设A1,2,3，B=2,4,6，A到B的关系Rx, y| 2x=y，则R= ( )A. , B. ,C. , D. , 3无向图G是棵树，边数是10，则G的结点度数之和是（ ） A. 20 B. 9 C. 10 D. 114下面的推理正确的是（ ）A(1) （x）F（x）G
8、（x） 前提引入 (2) F（y）G（y） US（1） B(1) （$x）F（x）G（x） 前提引入(2) F（y）G（y） US（1） C(1) （$x）(F（x）G（x） 前提引入 (2) F（y）G（x） ES（1）D(1) （x）（F（x）G（x） 前提引入 (2) F（y） G（y） US（1）5设个体域为整数集，则公式x$y(x+y=2)的解释可为 ( )A. 任一整数x，对任意整数y满足x+y=2 B. 对任一整数x，存在整数y满足x+y=2C. 存在一整数x，对任意整数y满足x+y=2 D. 存在一整数x，有整数y满足x+y=2二、填空题（每小题3分，本题共15分）6设集合A=1, 2, 3，
