B．a?b?a?2a?b C．a?b?b
D．a?b?a?b
其中，+，·，︱ ︱分别为实数的加法、乘法和取绝对值运算.
（3）设集合A??1,2,3,4,?,10?，下面定义的哪种运算关于集合A不是封闭的
（ D ）
A. x?y?max{x,y} B． x?y?min{x,y}
C. x?y?GCD{x,y}，即x,y的最大公约数 D. x?y?LCM{x,y}，即x,y的最小公倍数
（4）下列哪个集关于减法运算是封闭的 （ B ） A. N（自然数集）； B．{2x|x?Z(整数集)}； C. {2x?1|x?Z}； D. {x|x是质数}.
（5）设Q是有理数集，在Q定义运算?为a?b?a?b?ab，则Q,?的单位元 为 （ D ） A. a； B．b； C. 1； D. 0
（6）设代数系统?A，·?，则下面结论成立的是. （ C ） A．如果?A，·?是群，则?A，·?是阿贝尔群 B．如果?A，·?是阿贝尔群，则?A，·?是循环群 C．如果?A，·?是循环群，则?A，·?是阿贝尔群 D．如果?A，·?是阿贝尔群，则?A，·?必不是循环群
（7）循环群Z,?的所有生成元为 （ D ） A. 1，0 B．-1，2 C. 1，2 D. 1，-1 三、填空题
AA1. 设A为非空有限集，代数系统?2,??中，2对运算?的单位元为 ，零元
为 .填?,A
2.代数系统?Z,??中（其中Z为整数集合，+为普通加法），对任意的x?I，其
x?1? .填?x
3.在整数集合Z上定义?运算为a?b?a?2?b，则?Z,??的单位元为 . 解 设单位元为e，a?e?a?2?e?a，所以e??2，
又a?(?2)?a?2?(?2)?a,(?2)?a?(?2)?2?a?a，所以单位元为e??2
6
4.在整数集合Z上定义?运算为a?b?a?b?ab，则?Z,??的单位元为 . 解设单位元为e，a?e?a?e?ae?a，(1?a)e?0，所以e?0
5.设G,?是群，对任意a,b,c?G，如果a?b?a?c,，则 .填b?c 6.设G,?是群，e为单位元，若G元素a满足a?a，则a? .填e 四、解答题
1.设?为实数集R上的二元运算，其定义为
2?:R2?R,a?b?a?b?2ab，对于任意a,b?R
求运算?的单位元和零元。
解：设单位元为e，则对任意a?R，有a?e?a?e?2ae?a， 即 e(1?2a)?0，由a的任意性知 e?0，
又对任意a?R，a?0?a?0?0?a；0?a?0?a?0?a
所以单位元为0 设零元为?，则对任意a?R，有a???a???2a???， 即 a(1?2?)?0，由a的任意性知 ???又对任意a?R，a?(?)?a?所以零元为 ?1 21211111?a??，(?)?a???a?a?? 222221 22. 设?为集合I5?{0,1,2,3,4}上的二元运算，其定义为
?:I5?I5,a?b?(ab)mod5，对于任意a,b?I5
（1） 写出运算?的运算表；
（2） 说明运算?是否满足交换律、结合律，是否有单位元和零元、如果有请指出； （3） 写出所有可逆元的逆元 解：（1）运算表为
2? 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1
（2）运算?满足交换律、结合律，有单位元，单位元为1，有零元，零元为0；
7
（3）1的逆元为1，2的逆元为3，3的逆元为2，4的逆元4，0没有逆元
五、证明题
1. 设 ?G,?? 是一个群，试证 G 是交换群 当且仅当对任意的a,b?G ,有 a2?b2?(a?b)2 . 证明：充分性
若在群?G,??中，对任意的a,b?G ,有a2?b2?(a?b)2 . 则 (a?a)?(b?b)?(a?b)?(a?b) a?(a?b)?b?a?(b?a)?b
a?b?b?a 从而 ?G,?? 是一个交换群。 必要性
若?G,?? 是一个交换群，对任意的a,b?G ,有a?b?b?a，则 a?(a?b)?b?a?(b?a)?b (a?a)?(b?b)?(a?b)?(a?b) 即a2?b2?(a?b)2.
2. 证明代数系统?Z,??是群，其中二元运算?定义如下：
?：Z2?Z，x?y?x?y?3 （这里，+，－分别是整数的加法与减法运算.） 证明 （1）运算满足交换律 对任意x,y,z?Z，由
(x?y)?z?(x?y?3)?z?x?y?z?6, x?(y?z)?x?(y?z?3)?x?y?z?6
得(x?y)?z?x?(y?z),即?满足结合律；
（2）有单位元 3是单位元； （3）任意元素有逆元 对任意x?Z，x?1?6?x.所以,?Z，??是群.
第三章 图论
一、判断题
（1）n阶完全图的任意两个不同结点的距离都为1. （ 对 （2）图G的两个不同结点vi,vj连接时一定邻接. （ 错 （3）图G中连接结点vi,vj的初级通路为vi,vj之间的短程. （ 错 （4）在有向图中，结点vi到结点vj的有向短程即为vj到vi的有向短程． （ 错 （5）强连通有向图一定是单向连通的． （ 对 （6）不论无向图或有向图，初级回路一定是简单回路． （ 对 8
） ） ） ） ）
） （7）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的．
（ 对 ） （8）设A是某个无向图的邻接矩阵，则A?A(A是A的转置矩阵)．
（ 对 ） （9）设有向图D的可达矩阵为
TT?1??0 P??0??0?110011101??1? ?1?1??则G是单向连通的． （ 对 ）
（10）有生成树的无向图是连通的． （对） （11）下图所示的图是欧拉图. （ 错 ）
（12）下图所示的图有哈密尔顿回路. （ 对 ）
二、单项选择题
（1）仅由孤立点组成的图称为 （ A ） A. 零图； B．平凡图； C. 完全图； D. 多重图.
（2）仅由一个孤立点组成的图称为 （ B ） A. 零图； B．平凡图； C.多重图； D. 子图.
（3）在任何图G中必有偶数个 （ B ） A. 度数为偶数的结点； B．度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.
（4）设G为有n个结点的无向完全图，则G的边数为 （ C ） A. n(n?1) B．n(n?1) C. n(n?1)2 D. (n?1)2
（5）在有n个结点的连通图G中，其边数 （ B ） A. 最多n?1条； B．至少n?1条； C. 最多n条； D. 至少n条.
（6）任何无向图G中结点间的连通关系是 （ B ） A. 偏序关系； B．等价关系；
9
C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.
（7）对于无向图，下列说法中正确的是. （ B ） A．不含平行边及环的图称为完全图
B．任何两个不同结点都有边相连且无平行边及环的图称为完全图 C．具有经过每条边一次且仅一次回路的图称为哈密尔顿图 D．具有经过每个结点一次且仅一次回路的图称为欧拉图
（8）设D是有向图，则D强连通的充分必要条件为. ( C ) A．略去D中各边方向后所得到的无向图是连通的
B．D是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图 C．D的任意两个不同的结点都可以相互到达 D．D是完全图
（9）对于无向图G，以下结论中不正确的是. （ A ） A．如果G的两个不同结点是连接的，则这两个结点之间有初级回路 B．如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程 C．如果G是树，则任何两个不同结点之间有且仅有一条初级通路 D．如果G是欧拉图，则G有欧拉回路
（10）设简单无向图G的邻接矩阵为A?(aij)n?n,记A?(aij)n?n(l?1,2,?），则正确的是. （ C ） A．当vi,vj是G的两个不同结点时,aij为vi,vj之间长度为l的初级通路条数 B．当vi,vj是G的两个不同结点时,aij为vi,vj之间长度为l的简单通路条数 C．当vi,vj是G的两个不同结点时,aij为vi,vj之间长度为l的的通路条数
(l)D．当vi是G的结点时,aii为通过vi的长度为l的初级回路条数
l(l)(l)(l)(l)（11） M?mij??n?m是无向图G??V,E?的关联矩阵，则（ A ） vi?V是G中的孤立点，
A. vi对应的一行元素全为0； B．vi对应的一行元素全为1；
C. vi对应的一列元素全为0； D. vi对应的一列元素全为1.
三、填空题
1. 设树T有两个2度结点，一个3度结点，三个4度结点，其余都是树叶，则T的树叶片数为________.
解 用握手定理和树的性质列出方程求解，设有x个树叶，
2?2?3?3?4?x?2(2?1?3?x?1)，x?9
2.设T??V,E?为树，T中有4度，3度，2度分支点各1个，问T中有 片树叶。 解 与上题解法相同，设有x片树叶，4?3?2?x?2(3?x?1)，x?5 3.n阶完全图的任意两个不同结点的距离都为 ．1 4.图G为n阶无向完全图，则G共有 条边。n(n?1)/2
10