离散试卷有答案1

1、如果您需要使用本文档，请点击下载按钮下载!一、单项选择题 1设a = a, a ，p(a)表示集合a的幂集，下列哪一个是错的？（ ） a b c d2设a=1 , 2 , 3 上的二元关系r = <1 , 1>, <1 , 2> , <1 , 3> , <3 , 3> , 则r具备性质（ ）a反对称的，传递的 b反对称的 c反对称的, 自反的 d传递的3集合a = x, y, z , b = 1, 2, 3，下列a到b的二元关系中，哪一个能构成函数？（ ）a<x, 1>, <x, 2>, <y, 1>, <

2、;z, 3> b<x, 1>, <y, 3> c<x, 1>, <y, 3>, <z, 1> d<x, 2>, <y, 3>, <y, 2>4下列命题中（ ）是正确的。a欧拉图的子图一定是欧拉图。 b哈密顿图的子图一定是哈密顿图 。 c平面图的子图一定是平面图 。 d树的子图一定是树。5设有向图d的邻接矩阵为，则d中长度为3的通路总数有( ) 条。 a9 b10 c11 d12二、填空题 1公式的主析取范式为 。2某班共有学生60人，其中有25人订杂志甲，26人订杂志乙，26人订杂志丙，11人

3、订杂志甲和乙，9人订杂志甲和丙，8人订杂志乙和丙，还有8人未订任何杂志，则三种杂志都订的学生有 人。3设a = 2，4，5，10，12，20，r为a上的整除关系，则a的子集b = 4，10，12的极大元为 ，极小元为 ，上界为 ，下界为 。4设 ，则函数f是 （单射，满射还是双射）。5设集合a= a , b , c , d , e上的的划分s =a，d，b，c，e，则由划分s所确定的a上的等价关系r = 2 / 10如果您需要使用本文档，请点击下载按钮下载! 。6用kruskal算法求得下图g的一棵最小生成树为 。v8图gv1v2v3v4v512961248105711v6v737设连通平面图

4、g有4个面，9条边，则g有 个结点。三、解答题 ( 4×8 = 32分 )1将下列语句翻译成命题逻辑公式或谓词逻辑公式。(1)（4分）只有天下大雨，小明才乘公共汽车上学。(2)（4分）不是所有整数都是奇数。2设a = 1, 2, 3 上的二元关系r = <1, 1>, <1, 3>, <2, 1>，求r的关系矩阵，关系图。3设是a到 a 的满射，且，证明 。这里 表示a 上的恒等映射。4画图:(1)一个既没有欧拉回路，又没有哈密尔顿回路的图； （2）一个具有欧拉回路和哈密尔顿回路的图，并具体指出这两个回路。 5.用哈夫曼算法求带权为2,3,6，8,

5、10,11的最优二元树并计算此最优树的权。6. 设一棵树t有7片树叶，3个度数为3的结点，其余结点的度数均为4，求t的结点总数。7.用二元有序完全树表示算术表达式2 / 10如果您需要使用本文档，请点击下载按钮下载!并分别用波兰符号法和逆波兰符号法表示上述算术表达式。四、证明题 1用演绎法证明下述论断的正确性。 2. 设r是集合a上的一个具有传递和自反性质的关系，t是a上的关系，使得 ，证明 t是a上的等价关系。3.试证明：树是一个偶图。4用演绎法证明。5 p335 27，28 这类题一 1 2 3 4 5 b a c c b二、12 3 3 10，12； 4，10； 没有； 24 单射 56

6、3 / 10如果您需要使用本文档，请点击下载按钮下载!7 7三、1解：（1）设p：天下大雨 q：小明乘公共汽车上学，则有 （2）设z（x）：x 是整数，e(x)：x是奇数 2解： 3略 4略 5解：4 / 10如果您需要使用本文档，请点击下载按钮下载! 权 （ 定义10.3.7 ） 注：哈夫曼算法见书本（p292）算法10.3.6以及例10.3.9 6解：设t有x个4度结点，则t的结点总数 ，边数 由握手定理 得 解得 所以结点总数 7 （1）×+dh÷gji÷fe×abc（2）算式的波兰符号表示式为 （书上p295：先根次序遍历算法6 / 10如果您需

7、要使用本文档，请点击下载按钮下载! 省去括号 ）（3）算式的逆波兰符号表示式为 （同上，用后根遍历，省去括号，规定 即为 ）四、1证明： 2证明：（1）对任意的，由r是自反的，得，所以，即t是自反的。 （2）对任意的，若，则 ，即有 从而，即t是对称的。 （3）对任意的，若，则 且6 / 10如果您需要使用本文档，请点击下载按钮下载!即 且 又因为r是传递的 ， 所以 从而 ，所以t是传递的。 由（1）、（2）、（3）知t是等价关系。 3试证明：树是一个偶图。（p334:18）证：设 g=<v, e> 是一棵树。任选 , 定义 v 的两个子集如下：， . 现证明v1 中任二结点之间

8、无边存在。若存在一条边 （u,v）, u,v, 由于树中任意两个结点之间仅存在唯一一条基本通路，故这条基本通路就是他们之间的短程线，设v0到u 的短程线为 ，则其长度为k+1,是偶数，因为（u,v），所以 ，v 是 到 v 的一条通路，且该通路的长度k+2 为奇数，从而它不是基本通路， 故v必与某个相同，从而 是g中的一条基本通路，这与g 是树矛盾。4用演绎法证明。证明： (1) p （2） es，(1) （3） p （4） us，（3） 7 / 10如果您需要使用本文档，请点击下载按钮下载!（5） t，（4） （6） t，（5）（2） （7） p （8） us，（7） （6分）（9） t，（8）（6） （7