3离散数学B卷.docVIP

总分 核分人 卷号：B 湖北工业大学 二OO四—二OO五学年第二学期期末考试 离散数学 试题 （03级信计 专业用） 题号 一 二 三 四 五 六 七 八 九 十 题分 得分 注意：学号、姓名和所在年级班级不写、不写全或写在密封线外者，试卷作废。 一、 填空题（每小题2分，共10小题，满分20分） 1、 已知p的真值为1， q， r的真值为0，则命题的真值为_______________。 2、谓词公式的前束范式为_______________　　　。 3、设，则用列举法表示集合。 4、设，则。 5、设，则。 6、设则。 7、设I是整数集，＋是普通加法运算，则对代数，元素的逆元是______________。 8、设是代数系统，*和是二元运算，如果和*和满足交换律、结合律和吸收律，则构成。 9、设T是一棵树，顶点数为n，边数为m，则=_____________。 10、若根树T的每个分支点至多有3个儿子，则称T为_______________。 二、（8分）求的主合取范式，并指出它的成假赋值。 三、（12分）形式证推得r; （2），推得 。 四、（6分）已知求。 五、（8分）设，在上定义二元关系A 1、 证明：R是上的等价关系； 2、 确定由R引起的对的划分。 六、（8分）设是整除关系 1、画出偏序集的哈斯图； 2、写出A的极大元极小元、最大元和最小元。 七、（6分）设有函数，试求。 八、（8分）设I为整数集合，在I上定义二元运算?，有 1、证明：* 满足交换律和结合律； 2、求I关于*的单位元、零元和可逆元素的逆元。 九、（6分）一棵树T有5片树叶，3个2度顶点，其余顶点都是3度顶点，问T有多少个顶点？ 十、（8分）用Huffman算法求带权为2，2，3，6，9的最优二叉树。 十一、（8分）设有算式 1、 将以上算式存入一棵二叉正则有序树T中； 2、 分别写出上式的波兰符号法和逆波兰符号法表达的形式。