《离散试卷有答案(1).docx》由会员分享，可在线阅读，更多相关《离散试卷有答案(1).docx（8页珍藏版）》请在三一文库上搜索。
1、、单项选择题1设A = a, a , PA表示集合A的幕集，以下哪一个是错的？C. a P(A) D. a P(A)R = , , , ,那么R具备性质A.反对称的，传递的BC .反对称的，自反的D3. 集合 A = x, y, z , B = 1,2, 3函数？B . , D . , , A. , , , C . , , 4 .以下命题中是正确的。A. 欧拉图的子图一定是欧拉图。B. 哈密顿图的子图一定是哈密顿图。C. 平面图的子图一定是平面图。D. 树的子图一定是树。5. 设有向图D的邻接矩阵为11100 A010那么D中长度为3的通路总数有条00010010A . 9B10C . 11D
2、. 12二、填空题1 .公式P Q Q R的主析取式为 。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 : N N N ,fn n ,n 1，贝U函数f是 单射，满射还是双射。5.设集合 A= a , b , c , d , e上的的划分 S =a，d，b，c，e，那么由划分S所确定的A上的等
3、价关系R = 。6. 用kruskal算法求得以下图G的一棵最小生成树为 vi 4 V47. 设连通平面图G有4个面，9条边，那么G有个结点。三、解答题(4 X 8 = 32分)1. 将以下语句翻译成命题逻辑公式或谓词逻辑公式。(1) (4分)只有天下大雨，小明才乘公共汽车上学。(2) (4分)不是所有整数都是奇数。2. 设 A = 1,2, 3 上的二元关系 R = , , ，求 R 的关 系矩阵，关系图。3 .设f是A到A的满射，且f f f，证明f I a。这里I a表示A上的 恒等映射。4. 画图:(1) 一个既没有欧拉回路，又没有哈密尔顿回路的图；(2) 一个具有欧拉回路和哈密尔顿回
4、路的图，并具体指出这两个回路。5. 用哈夫曼算法求带权为2,3,6，8,10,11的最优二元树并计算此最优树的权。6. 设一棵树T有7片树叶，3个度数为3的结点，其余结点的度数均为4,求T 的结点总数。7. 用二元有序完全树表示算术表达式(a b) c-d) (e f) g (h i j)并分别用波兰符号法和逆波兰符号法表示上述算术表达式。四、证明题1 用演绎法证明下述论断的正确性。PQ,PR,S T,SR, T Q.2. 设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得a,b Ta,bR且b,a R，证明T是A上的等价关系。3. 试证明：树是一个偶图。4 用演绎法证明x(M
5、(x) F(x), x(F(x) G(x), x G(x) x M(x)。5. P335 27, 28 这类题12345BACCB1. (PQ R)(PQR) (P Q R) ( P Q R)2.33.10, 12;4,10;没有；24.单射5.a,d ,d ,a7c,e ,e,cI a7.71解：(1)设P:天下大雨Q:小明乘公共汽车上学，那么有Q P(2)设Z (x): x是整数，E(x): X是奇数x(Z(x) E(x)1012. 解：Mr1000001 2P * 3S(R) 1,1 , 1,2, , 1,3 , 2,1 , 3,13. 略4. 略5. 解:22111140188 10权
6、 W(T)(2 3) 46 3 (8 10 11) 2 96(定义 10.3.7 )注：哈夫曼算法见书本(P292)算法1036以及例10396. 解：设T有x个4度结点，那么T的结点总数n 7 3 x 10 x，边数 m n 19 xn由握手定理d(Vi) 2m 得 7 1 3 3 4x 2(9 x)i 1解得 X 1所以结点总数n 7 3 1 117. (1)(2)算式的波兰符号表示式为abed ef g h ij(书上P295：先根次序遍历算法省去括号 )同上，用后( 3)算式的逆波兰符号表示式为 ab c d ef ghij根遍历，省去括号，规定 即为)四、1证明：(1) TP( 2)
7、 S TP(3) ST,(1)(2)(4) S RP(5) RT,(3)(4)(6) P RP(7) PT , (5)(6)(8) P QP(9) QT,(7)(8)2证明：(1)对任意的x A，由R是自反的，得x,x R x,x R ,所以 x, xT ，即 T 是自反的。( 2)对任意的 x, y A ，假设 x, y T ，那么x, y Ry, x R ，即有 y , x R x, y R从而 y, x T ，即 T 是对称的。( 3)对任意的 x, y, z A ，假设 x, y T , y, z T ，那么x, y R ,y,x R 且, y,z R z,y R即 x, yR , y
8、, z 且 , z, y R y, x R又因为 R 是传递的 ， 所以 x,z R , z,x R从而 x,z T,所以T是传递的。由(1)、(2)、(3)知T是等价关系。3试证明：树是一个偶图。( P334:18)证：设 G= 是一棵树。 任选 v0 V, 定义 V 的两个子集如下：Vi v|d(v,v)为偶数 , V V - Vi .现证明Vi中任二结点之间无边 存在。假设存在一条边(u,v)E, u,v V1 , 由于树中任意两个结点之间仅存在唯一一条根本通路， 故这条根本通路就是他们之间的短程 线，设Vo到U的短程线为v0,v1,v2,.,vk,u，那么其长度为k+1,是偶数， 因为
9、(u,v) E，所以v,vi,v2,.,vk,u，v是vo到v的一条通路，且 该通路的长度 k+2 为奇数，从而它不是根本通路， 故 v 必与某个 vi(i 0,1,2,.k)相同，从而 v,vi i,vi 2,-,vk,u,v 是 G 中的一条根本通路， 这与 G 是树矛盾。4用演绎法证明x(M(x) F(x), x(F(x) G(x), x G(x) x M(x)。证明：(i)x( G(x)P(2)G(c)ES， (i)(3)x(F(x) G(x)P(4)F(c) G(c)US，(3)(5)G(c) F(c)T，(4)7) x(M (x)F(x)P8) M (c) F(c)US ， 7 6 分9) M (c)T，8 67分10) x( M (x)EG，95.在简单平面图G中，至少有一个度数小于等于5的结点。P335:27或5 证明小于30条边的简单平面图G中至少有一个度数小于等于4的结点。P335: 28