1、 第 1次作业 一、填空题（本大题共 30 分，共 5 小题，每小题 6 分） 1. 设 f,g,h 是 N 到 N 上的函数（ N 为自然数集合）， f(n)=n+1; g(n)=2n; h(n)=0；则 (fog)oh= _ 。 2. 设全集 U=1,2,3,4,5,6,7的字集为 A=偶数 ， B=奇数 ， C=3 的倍数 ，则 AB= _ , BC= _ 3. 设 A=,2 ，则 A的幂集为 _ 。 4. 设 A=0,1,2,3， B=4,6,7， C=8,9,12,14， R1是由 A到 B的关系， R2是由 B到 C原关系，分别定义为R1=,;R2=,，则复合关系R1oR2为： _
2、 5. 设 A=1， 2， A 上的二元运算定义为 x*y=minx,y,则 *的运算表为 _ 。 二、判断题（本大题共 10 分，共 5 小题，每小题 2 分） 1. 集合 A上的等价关系确定了 A的一个划分。（ ） 2. 为矛盾式。（ ） 3. R是 A上的二元关系， R是自反的，当且仅当 r(R)=R。（ ） 4. 任何图中必有偶数个度数为奇数的结点。（ ） 5. 设 S=0,1,S是关于普通的加法和乘法运算，则 S上的加法与乘法运算满足封闭性、结合性。（ ） 三、单项选择题（本大题共 20分，共 10 小题，每小题 2 分） 1. 下列语句中不是命题的只有（）。 A. 鸡毛也能飞上天？
3、 B. 人的死或重于泰山，或轻于鸿毛。 C. 不经一事，不长一智。 D. 牙好，胃口就好。 2. 设 G是连通平面图， G中有 6个顶点 8 条边，则 G的面的数目是（） A. 2个面 B. 3个面 C. 4个面 D. 5个面 3. 下面 关于关系 R 的传递闭包 t(R)的描述最确切的是（ ）。 A. t(R)是包含 R的二元关系 B. t(R)是包含 R的最小传递关系 C. t(R)是包含 R的一个传递关系 D. t(R)是任何包含 R的传递关系 4. 下面哪一个图是树（ ）？ A. B. C. D. 5. 若集合 A的基数为，则其幂集的基数 |P(A)|是多少？（ ） A. 107 B.
4、 70 C. 27 D. 17 6. 若 R和 S是集合 A上的两个关系，则下述结论正确的是（ ） A. 若 R和 S是自反的，则 RoS是自反的。 B. 若 R和 S是对称的，则 RoS是对称的。 C. 若 R和 S是反自反对称的，则 RoS是反自反的。 D. 若 R和 S是传递的，则 RoS是传递的。 7. Z是整数集合，函数 f定义为： ZNETWORK SERVICEZ,f(x)=|x|-2x，则 f是（ ）。 A. 入射 B. 满射 C. 双射 D. 既不是入射也不是满射 8. 设某二叉树的高度为 k，则该树的最大结点数为（ ）。 A. 2k+1 B. 2k+1+1 C. 2k-1
5、D. 2k+1-1 9. 以下各代数系统中不含零元素的是（ ）。 A. Q是全体有理数集， *是 数的乘法运算。 B. Mn(R)四全体 n阶矩阵集合， *是矩阵乘法运算 C. Z是整数集， o定义为 xoy=xy, (x,yZ) D. Z是整数集， +是数的加法运算 10. 设有完全 m叉树，其树叶数为 t，分枝点数为 i，则下列成立的是 ( ) A. m=i+t B. t=i-1 C. :(m-1)i=t-1 D. (t-1)i=m-1 四、分析题（本大题共 8分，共 1 小题，每小题 8 分） 判定下式的性质（永真式、永假式，其它） 1） (pNETWORK SERVICEq)(p NE
6、TWORK SERVICEq) 2)(pq) NETWORK SERVICEq) NETWORK SERVICE (qNETWORK SERVICEr) NETWORK SERVICEq) 3) NETWORK SERVICE (qp) NETWORK SERVICE NETWORK SERVICEp) NETWORK SERVICE (pNETWORK SERVICEr) 4)( NETWORK SERVICEpNETWORK SERVICEq)r)(p NETWORK SERVICE NETWORK SERVICEq) NETWORK SERVICEr) 五、作图题（本大题共 8分，共 1
7、 小题，每小题 8 分） 求出权为 2， 5， 7， 11， 13的最优二元树。 六、计算题（本大题共 16 分，共 2 小题，每小题 8 分） 1. 设解释 I 如下： D=0,1,2,f(0)=1; f(1)=2; f(2)=0; F(0,0)=1; F(0,1)=1; F(1,0)=1;F(1,2)=0,F(1,1)=1;F(2,0)=1; F(0,2)=0; F(2,1)=1; F(2,2)=1，试求出下列公式在 I上的真值： 2. 分别 列出：广群、半群、独异点、群的概念 七、证明题（本大题共 8分，共 1 小题，每小题 8 分） 设 T是一棵完全二元树， n0表示树叶结点数，试证明
8、边数 m=2(n0-1)。 答案： 一、填空题（ 30 分，共 5 题，每小题 6 分） 1. 参考答案： 1 解题方案： 评分标准： 2. 参考答案： ； 3 解题方案： 评分标准： 3. 参考答案： 解题方案： 评分标准： 4. 参考答案： , 解题方案： 评分标准： 5. 参考答案： 解题方案： 评分标准： 二、判断题（ 10 分，共 5 题，每小题 2 分） 1. 2. 3. 4. 5. 三、单项选择题（ 20 分，共 10 题，每小题 2 分） 1. A 2. C 3. B 4. D 5. C 6. A 7. A 8. D 9. D 10. C 四、分析题（ 8分，共 1 题，每小题 8 分） 0. 参考答案： (1)非永真可满足 （ 2）永真 （ 3） 永假 （ 4）永真 解题方案： (1)非永真可满足 （ 2）永真 （ 3） 永假 （ 4）永真 评分标准： 10 五、作图题（ 8分，共 1 题，每小题 8 分） 0. 参考答案： 解题方案： 评分标准： 六、计算题（ 16 分，共 2 题，每小题 8 分） 1. 参考答案： 解题方案： 评分标准： 2. 参考答案： 略 解题方案： 略 评分标准： 七、证明题（ 8分，共 1 题，每小题 8 分） 0. 参考答案： 解题方案： 评分标准：
