（新编）课件作业题解分析与答案.doc

课件作业题解分析与答案第一部分 集合论第一章 集合的基本概念和运算 1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是 　　　　　 [ B ]A．2 ∈A； B．1 ∈ A； C．5 ∈A； D．{2} A题解与分析：A 是集合，2，5 不是他的元素所以，（A）,(C)无可争议的是错误然而，某集合若是另一集合子集，则子集也可以成为集合的元素，二者从而产生隶属关系,例如，本题的集合A与集合{2}而Ｄ说{2}是A的子集而不是元素,就是错误的了．所以，只有（B）为正确1-2 A,B　为任意集合，则他们的共同子集是　　 　 [ D ]A．A； B．B； C．A∩B； D． Ø 题解与分析： 1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？（1） N Q，Q ∈S，则 N S，　　　　　　　　　　　　　　　　　　［　错　］（2）-1 ∈Z，Z S， 则 -1 ∈S 。

　　　　　　　　　　　　　　　　　［　错　］题解与分析：S 实际上是实数集合 R ，自然数集合　Ｎ，有理数集合　Ｑ　的集合，诸如“N S”，“Q S”，“2 ∈S”，“-1 ∈S” 之类的命题都是错误的所以，(1）,(2)都错1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø ， C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，E = {x│x ∈R 并且 x 2 - 7x + 12 = 0}，F = { 4，Ø ，3，3}，试问哪两个集合之间可用等号表示 ？题解与分析：根据题意，A = E；B = C；D = F 1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x 2 ≤ 9 }（2）A = { x│x ∈N 且 3－x 〈 3 }题解与分析：本题以谓词给出集合的表达式要求把解析表达式所含的元素列出；当然，有的集合的元素需要通过计算才能得到所以结果为：（1）A = { 0，1，2，3 }； （2）A = { 1，2，3，4，……} = Z +；第二章 二元关系 2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：R = {〈x，y〉x，y ∈X 且 x ＜ y }求：(1)domR =?; (2)ranR =?; (3)R 的性质。

题解与分析：所谓谓词表达法，即是将集合中所有元素的共同性质用一个谓词概括起来，如本题几例所示有的书上称其为抽象原则反过来，列元法则是遵照元素的性质和要求，逐一将他们列出来，以备下用,结果如下：R = {，，}；DomR={R中所有有序对的x}={2,1,1}={2,1};RanR={R中所有有序对的y}={3,2,3}={3,2}；R 的性质:反自反,反对称,传递性质.2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，试求：（1）R 的列元表达式； （2）给出 dom（R 题解与分析：在求解关系的诸问题时，较好的办法是列出关系的每个有序对，以及解决其他问题根据方程式有：y=4-x/3，x 只能取 3，6,9 结果如下：（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；至于(2),望大家认真完成合成运算 R R={}.然后,给出 R R 的定义域,即（2）dom（R R）= {3}2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→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 = x 2 5）A = B = N， f = x + 1 分析与题解：判断映射的性质，要分三步考虑：第一，是否函数 ？第二，是否 A 到 B 的函数？第三，是否单射、满射结论如下：（1） 是 A 到 B 的函数，是满射而不是单射；（2） 是双射；（3）是双射；（4）是单射，而不是满射；（5）是单射而不是满射2-4 设 A ={1，2，3，4}，A 上的二元关系 R ={〈x，y〉︱（x-y）能被 3 整除} ，则自然映射 g：A→A/R 使 g(1) = [ C ]A． ｛1,2｝ ； B． ｛1,3｝ ； C． ｛1,4｝ ； D． ｛1｝ 。

分析与题解：大家明白，在本题条件下，只有 0和 3才能被 3整除，这样一来，在关系Ｒ中，必有,两个有序对出现，就是说，自然映射 g：A →A/R使 g(1) =［1 ］＝｛1,4｝．2-5 设 A ={1，2，3} ，则商集 A/IA = [ D ]A． ｛3｝ ； B． ｛2｝ ； C． ｛1｝ ； D． ｛｛1｝ ， ｛2｝ ， ｛3｝ ｝　分析与题解：记住商集的元素是等价类．而各元素的等价类分别为[1]＝{1}，[2]＝{2}，[3]＝{3}．所以有 A/IA＝Ｄ．2-6．设ｆ (x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ ｇ＝ [ C ]　　　　　　A．x+1； B．x-1； C．x； D．x 2分析与题解：函数的合成运算很简单．即将g(x)做为一个整体代入到f(x)的x处即可．本题为：f(g(x))=((x-1)+1)=x.第三章 结构代数(群论初步)3-1 给出集合及二元运算，判断是否代数系统，何种代数系统 ？（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 * 是普通乘法。

2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；二元运算 定义如下：对于所有 ai，aj ∈S2，都有 ai aj = ai 3）S3 = {0，1}，二元运算 * 是普通乘法分析与题解：一个代数系统，通常由三个条件构成第一，要有一个集合；第二，要有若干个 n 元运算；第三，n 元运算在集合内自我封闭所以，我们的结论应是：（1）二元运算*在S1上不封闭．所以，＂S1，*＂不能构成代数系统2）由二元运算的定义不难知道，在 S2 内是封闭的，所以，〈S2， 〉构成代数系统；然后看该代数系统的类型：该代数系统只是半群3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异点；而 0 为零元；结论：仅为独异点，而不是群3-2 在自然数集合上，下列那种运算是可结合的　 　　 　　　　　　　 ［ A ］A．x*y = max(x,y) ； B．x*y = 2x+y ；C．x*y = x2+y2 ； D．x*y =︱x-y︱..分析与题解：结合律的验证很简单．然而，没有窍门．只有在（x*y）*z=x*(y*z)时，才可以得出满足结合律的结论．3-3 设 Z 为整数集合，在 Z 上定义二元运算 。

对于所有 x，y ∈Z 都有x y = x + y ＋ 5，试问〈Z，〉能否构成群，为什麽 ？分析与题解：判别一个代数系统是否是群，当然要满足群的定义条件然而，判别过程要分步走因为题中以代数系统形式给出，第一步封闭性问题判断可省去.之所以说该步骤可以略去,是在题中已经告知代数系统成立的前提下.否则要进行讨论:此二元运算中,只有加减法,在集合 Z 中必然满足封闭性；第二步，二元运算满足结合律，以决定半群；第三步，有幺元为 －5，为独异点.必须记住,求特殊元素时,都要解联立方程.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e x = e + x ＋ 5，一个方程来自该特殊元素的定义的性质,即e x = x.由此而来的两个方程联立结果就有: e+x＋5=x 成立.削去 x,e=－5 的结果不是就有了吗!；第四步，每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理；第五步，结论是：代数系统〈 Z，〉构成群第二部分 图论方法第四章 图 4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个奇度顶点 ？题解分析：提到图的补图，必须首先想到完全图.因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。

这样一来，一个无向简单图 G 的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，Ｇ的补图中应有 10-4＝6 个奇数度顶点4-2 是非判断：无向图 G中有 10条边,4 个 3度顶点,其余顶点度数全是 2,共有 8 个顶点. [ 是]分析与题解：握手定理告诉我们：20＝4x3＋2ｘ，所以，ｘ＝4，即4个2度顶点，共8个顶点．4-3 填空补缺：1 条边的图 G 中，所有顶点的度数之和为　　　　　　　　　　 [ ２ ]分析与题解：握手定理是普适定理．任何无向图中，所有顶点的度数之和都是边的两倍．第五章 树5-1 握手定理的应用（指无向树）（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有几个？（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有几片？题解分析：对于图论中树的有关问题的解决，无非是利用握手定理以及利用树是连续而无回路的性质，即 Σd（Vi）= 2m 定理和利用 n—1= m 定理所以有如下结果：（1）有 1 个 4 度顶点； （2） 9 个 1 度顶点 5-2 一棵树中有 i 个顶点的度数为 i（=2，…k），其余顶点都是树叶，问树叶多少片？题解分析：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = Σi（i—2） i + 2，（i = 2，3，……k）。

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T试问：（1） T 的权 W（T）？ （2）树高几层 ？ 题解分析：用 Huffman 算法，以 1，2，3，5，7，8 为权，最优 2 元树 T ；然后，计算并回答所求问题：（1）T 的权 W（T）= 61；（2）树高几层：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}题解分析：根据前缀码的定义，判断 B1，B2 是前缀码，而 B3，B4 不是5-5 11 阶无向连通图 G 中有 17 条边，其任一棵生成树 T 中必有 6条树枝 [ 非 ]题解分析：ｎ阶无向连通图 G 的任一棵生成树 T 中必有ｎ－１条树枝，而与边数无关．Ｔ所对　　　应的基本回路数才与边数有关系．务必注意此点！！！ 5-6 二元正则树有奇数个顶点。