离散试卷有答案 (1).doc

《离散试卷有答案 (1).doc》由会员分享，可在线阅读，更多相关《离散试卷有答案 (1).doc（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流离散试卷有答案 (1)【精品文档】第 7 页一、单项选择题 1设A = a, a ，P(A)表示集合A的幂集，下列哪一个是错的？（ ） A B C D2设A=1 , 2 , 3 上的二元关系R = , , , , 则R具备性质（ ）A反对称的，传递的 B反对称的 C反对称的, 自反的 D传递的3集合A = x, y, z , B = 1, 2, 3，下列A到B的二元关系中，哪一个能构成函数？（ ）A, , , B, C, , D, , 4下列命题中（ ）是正确的。A欧拉图的子图一定是欧拉图。 B哈密顿图的子图一定是哈密顿图 。 C平面图的子图一定是平面图

2、 。 D树的子图一定是树。5设有向图D的邻接矩阵为，则D中长度为3的通路总数有( ) 条。 A9 B10 C11 D12二、填空题 1公式的主析取范式为 。2某班共有学生60人，其中有25人订杂志甲，26人订杂志乙，26人订杂志丙，11人订杂志甲和乙，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

3、，e，则由划分S所确定的A上的等价关系R = 。6用kruskal算法求得下图G的一棵最小生成树为 。v8图Gv1v2v3v4v512961248105711v6v737设连通平面图G有4个面，9条边，则G有 个结点。三、解答题 ( 48 = 32分 )1将下列语句翻译成命题逻辑公式或谓词逻辑公式。(1)（4分）只有天下大雨，小明才乘公共汽车上学。(2)（4分）不是所有整数都是奇数。2设A = 1, 2, 3 上的二元关系R = , , ，求R的关系矩阵，关系图。3设是A到 A 的满射，且，证明 。这里 表示A 上的恒等映射。4画图:(1)一个既没有欧拉回路，又没有哈密尔顿回路的图； （2）一

4、个具有欧拉回路和哈密尔顿回路的图，并具体指出这两个回路。5.用哈夫曼算法求带权为2,3,6，8,10,11的最优二元树并计算此最优树的权。6. 设一棵树T有7片树叶，3个度数为3的结点，其余结点的度数均为4，求T的结点总数。7.用二元有序完全树表示算术表达式并分别用波兰符号法和逆波兰符号法表示上述算术表达式。四、证明题 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；

5、 4，10； 没有； 24 单射 567 7三、1解：（1）设P：天下大雨 Q：小明乘公共汽车上学，则有 （2）设Z（x）：x 是整数，E(x)：X是奇数 2解： 3略 4略 5解：权 （ 定义10.3.7 ） 注：哈夫曼算法见书本（P292）算法10.3.6以及例10.3.9 6解：设T有x个4度结点，则T的结点总数 ，边数 由握手定理 得 解得 所以结点总数 7 （1）+dhgjifeabc（2）算式的波兰符号表示式为 （书上P295：先根次序遍历算法 省去括号 ）（3）算式的逆波兰符号表示式为 （同上，用后根遍历，省去括号，规定 即为 ）四、1证明： 2证明：（1）对任意的，由R是自反的

6、，得，所以，即T是自反的。 （2）对任意的，若，则 ，即有 从而，即T是对称的。 （3）对任意的，若，则 且即 且 又因为R是传递的 ， 所以 从而 ，所以T是传递的。 由（1）、（2）、（3）知T是等价关系。 3试证明：树是一个偶图。（P334:18）证：设 G= 是一棵树。任选 , 定义 V 的两个子集如下：， . 现证明V1 中任二结点之间无边存在。若存在一条边 （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） （5） T，（4） （6） T，（5）（2） （7） P （8） US，（7） （6分）（9） T，（8）（6） （7分）（10） EG，（9）5在简单平面图G中，至少有一个度数小于等于5的结点。（P335:27）或5 证明小于30条边的简单平面图G中至少有一个度数小于等于4的结点。（P335: 28 ）