发布时间 : 星期一 文章离散数学作业更新完毕开始阅读70480bca6bec0975f465e26f
2013春课件作业
第一部分 集合论
第一章 集合的基本概念和运算
1-1 设集合 A ={{1，2}，a，4，3}，下面命题为真是 [ C ]
A．2 ∈A； B．1 ∈ A； C．3 ∈A； D．{1，2} ? A。
1-2 A,B,C 为任意集合，则他们的共同子集是 [ D ]
A．C； B．A； C．B； D． ? 。
1-3 设 S = {N，Z，Q，R}，判断下列命题是否正确
（1） N ? Q，Q ∈S，则 N ? S，［ 错 ］
（2）-1 ∈Z，Z ∈S， 则 -1 ∈S 。［ 错 ］
1-4 设集合 B = {4，3} ∩ ? ， C = {4，3} ∩{ ? }，D ={ 3，4，? }，
E = {x│x ∈R 并且 x2 - 7x + 12 = 0}，F = { 4，? ，3，3}，
试问：集合 B 与那个集合之间可用等号表示 [ A ]
A. C; B. D; C. E; D. F.
1-5 用列元法表示下列集合：A = { x│x ∈N 且 3－x 〈 3 } [ D ]
A. N; B. Z; C. Q; D. Z+
1-6 为何说集合的确定具有任意性 ?
答：因为集合的元素也可以是集合，所以说它具有任意性。
第二章 二元关系
2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：
R = {R中所有 }
求：(1)domR =?; (2)ranR =?; (3)R 的性质。
答:由题可得R={〈2，3〉，〈1，2〉，〈1，3〉}U Ix；
(1)domR ={R中所有有序对的x}={3,2,1}
(2)ranR ={R中所有有序对的y}={3,2,1}
(3)R 的性质:自反；不对称；传递性质。
2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即
R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，
试给出 dom（R 。R）。 [ B ]
A. 3； B. {3}； C. 〈3，3〉； D.{〈3，3〉}。
2-3 判断下列映射 f 是否是 A 到 B 的函数； 以及函数的性质。最后指出 f：A→B 中的双射函数。[ B ]
（1）A = {1，2，3}，B = {4，5}， f = {〈1，4〉〈2，4〉〈3，5〉}。 （2）A = {1，2，3} = B， f = {〈1，1〉〈2，2〉〈3，3〉}。 （3）A = B = R， f = x 。 （4）A = B = N， f = x2 。 （5）A = B = N， f = x + 1 。
A.（1）和（2）； B.（2）和（3）； C.（3）和（4）； D.（4）和（5）
2-4 设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝ [ C ]
A．x+1； B．x-1； C．x； D．x2。
2-5 关系型数据库与《关系与函数》一章内容有何联系 ？
答：关系数据库，是建立在关系模型基础上的数据库，借助于集合代数和各种函数关系等数学概念和方法来处理数据库中的数据，现实世界中的各种实体以及实体之间的各种联系均用关系模型来表示。
第三章 结构代数(群论初步)
3-1 给出集合及二元运算，判断是否代数系统，何种代数系统 ？
(1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 * 是普通乘法。 [ A ]
A．不构成代数系统； B．只是代数系统。； C． 半群； D．群。
（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；
二元运算 。定义如下：对于所有 ai，aj ∈S2，都有 ai 。aj = ai 。 [ C ]
A．不构成代数系统； B．只是代数系统。； C． 半群； D．群。
（3）S3 = {0，1}，二元运算 * 是普通乘法。[ C ]
A．不能构成代数系统； B．半群； C．独异点； D．群。
3-2 在自然数集合上，下列那种运算是可结合的 。 ［ A ］
A．x*y = max(x,y) ； B．x*y = 2x+y ； C．x*y = x2+y2 ； D．x*y =︱x-y︱..
3-3 设 N 为自然数集合，在 N 上定义二元运算 。，对于所有 x，y ∈N 都有 x 。y = x - y
试问？在 N 上二元运算 。能否构成代数系统，何种代数系统？为什麽 ？
答：第一步，由题已知，此二元运算中，只有加法，在集合Z中必然满足封闭性；
第二步，二元运算满足结合律，以决定半群；
第三步，有幺元为4，为独异点，假设代数系统的幺元是集合中的元素e，则一个方程来
自于二元运算定义，即e。x=e+x-4,一个方程来自该特殊元素的定义的性质，即e。x=x.由此而来的两个方程联立结果就有：e+x=x成立.消去x,e=4的结果不是就有了吗？；
第四步，每个元素都有逆，求每个元素的逆元素，也要解方程，如同求幺元理：设y是x
的逆，则一个方程为y。x=y+x-4,另一个方程为y。x=4,联立结果得到y=8-x;
第五步，结论是：代数系统
第二部分 图论方法
第四章 图
4-1 10 个顶点的简单图G中有4个奇度顶点，问 G 的补图中有 r 个偶数度顶点。[ C ] A．r =10 ； B．r = 6； C．r = 4； D．r = 9。
4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2，共有 8 个顶点。[ 是 ]
4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 2
第五章 树
5-1 概述无向图与无向树的关系？ 答：连通而不含回路的无向图称谓无向树
5-2 握手定理的应用（指无向树）
（1）在一棵树中有 7 片树叶，3个3 度顶点，其余都是4 度顶点，共几个顶点 [ 11]
（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有几片叶 [ 9 ]
5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。
试问：T 的权 W（T）= ( 61 )；树高 ( 4 ) 层。
5-4 以下给出的符号串集合中，那些是前缀码
B1 = {0，10，110，1111}； [ 是] B2 = {1，01，001，000}； [ 是 ] B3 = {a，b，c，aa，ac，aba，abb，abc} [ 非 ] B4 = {1，11，101，001，0011} [ 非 ]
5-5 11 阶无向连通图 G 中有 17 条边，其任一棵生成树 T 中必有6条树枝 [ 非 ]
5-6 二元正则树有奇数个顶点。 [ 是 ]
5-7 通信中 a，b，c，d，e，f,g,h 出现的频率分别为 35%;20%;15%.10%,10%,5%,3%,2%; 求传输他们的最佳前缀码。
1、最优二元树 T； 2、二元树的权 W（T）= ； 3、每个字母的码字；
答：