2离散数学A卷.docVIP

湖北工学院二OO三 —二OO四学年第二学期期末考试 离散数学(A 卷) 试题 （02级信计 专业用） 一 二 三 四 五 六 七 八 九 十 十一 总分 注意：学号、姓名和所在年级班级不写、不写全或写在密封线外者，试卷作废。 一、 填空题（每小题2分，共10小题，满分20分） 1、 已知p,q的真值为1，r的真值为0，则命题的真值为_______________。 2、 设个体域，是谓词，则。 3、 设，则用列元素法表示集合。 4、 设，则。 5、 设，则R逆关系。 6、 设 则。 7、 设Q是有理数集，*是通常的乘法运算，则对代数，元素的逆元是______________。 8、 设是偏序集，如果都有最小上界和最大下界，则称S关于偏序作成______________ 。 9、 设T是一棵树，结点数为n，边数为m，则____________　　　　_。 10、 若根树T的每个分支点均恰好有r个儿子，则称T为_______________。 二、（8分）求的主析取范式，并指出它的成真赋值。 三、（12分）形式证明：推得， （2）前提：，结论：。 四、（6分）已知求。 五、（8分）自然数集N上的二元关系定义为 1、 证明：R是N上的等价关系； 2、 写出N关R导出的等价类。 六、（8分）设是整除关系 1、画出偏序集的哈斯图； 2、写出A的极大元、极小元、最大元和最小元。 七、（6分）设有函数， 证明：f是双射。 八、（10分）对有理数集Q，定义二元运算*为 1、证明：* 满足交换律和结合律； 2、求Q关于*的单位元、零元和可逆元素的逆元。 九、（6分）设无向树T有9片树叶，2个4度顶点，其余顶点的度数均为3，问T有几个顶点？ 十、（8分）用Huffman算法求带权为1，2，3，4，5的最优二叉树，并计算它的权。 十一、（8分）设有算式 1、 将以上算式存入一棵二叉正则有序树T中； 2、 分别写出上式的波兰符号法和逆波兰符号法表达的形式。