离散数学(本)2016年10月份试题.doc

离散数学试题一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3,4}，则下列表述不正确的是 ( )． A．1(A B．{1,2,3}(A C．{1,2,3}(A D．( (A 2．设＝｛1, 2, 3｝，B={1, 2, 3, 4}，到B的关系＝｛〈x, y〉|x=y｝，则R为 ( ) ． A. {1, 2, 2, 3} B. {1, 1, 1, 2, 1, 3, 1, 4, 1, 5} C. {1, 1, 2, 1} D. {1, 1, 2, 2, 3, 3 } 3．无向图G的边数是10，则图G的结点度数之和为（ ）． A. 10 B. 20 C. 30 D. 5 4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e – r = – 4 D．v + e - r=2 5．设个体域D是整数集合，则命题(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}，则(B(C) – A等于　 ． 7．设A={23}，B={12}，C={34}，从A到B的函数f={2, 2, 3, 1}，从B到C的函数g={1，3, 2，4}，则Dom(g( f)等于 ． 8．若图G=V, E，其中V={ a, b, c, d }，E={ (a, b), (a, d), (b, c), (b, d)}，则该图中的割边为 ． 9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6，则在G -S中的连通分支数不超过 ． 10．设个体域D＝{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={12, 3}，R={xy|x(A，y(A且x+y=4}，S={xy|x(A，y(A且x=y}，试求R，S，R-1，r(S)． 16．图G=V, E，其中V={ a, b, c, d, e }，E={ (a, b), (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．试证明：P→Q ( P→（( ((P∨(Q)）． 离散数学试题 解答 一、单项选择题（每小题3分，本题共15分） 1．C 2．D 3．B 4．A 5．B 二、填空题（每小题3分，本题共15分） 6．{d} 7．{2，3} 8．(b, c) 9．6 10．真（或T，或1） 三、逻辑公式翻译（每小题6分，本题共12分） 11．设P：小明是学生， Q：小张是飞行员． （2分） 则命题公式为： P∧Q． （6分） 12．设P：大家都进入教室， Q：讨论会开始进行． （2分） 则命题公式为：P→Q． （6