答：9，3
（半群与群部分）
39、设〈G,*〉是一个群，则
(1) 若a,b,x∈G，a?x=b，则x=( )； (2) 若a,b,x∈G，a?x=a?b，则x=( )。
答： （1） a?1?b （2） b
40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。
答： 6,4
41、代数系统
答：单位元
42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。
答：5，10
43、群
答：单位元，1
44、素数阶群一定是( )群, 它的生成元是( )。
答：循环群，任一非单位元
45、设〈G,*〉是一个群，a,b,c∈G，则
(1) 若c?a=b，则c=( )；(2) 若c?a=b?a，则c=( )。
答：（1） b?a?1 (2) b
46、
答：
47、群＜A,*＞的等幂元有( )个，是( )，零元有( )个。
答：1，单位元，0
48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。
答：k
49、在自然数集N上，下列哪种运算是可结合的？（ ）
第 6 页 共 33 页
(1) a*b=a-b (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b|
答：(2)
50、任意一个具有2个或以上元的半群，它（ ）。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群
答：(1)
51、6阶有限群的任何子群一定不是（ ）。 (1) 2阶 (2) 3 阶 (3) 4 阶 (4) 6 阶
答：(3)
（格与布尔代数部分）
52、下列哪个偏序集构成有界格（ ） (1) （N,?） (2) （Z,?）
(3) （{2,3,4,6,12},|（整除关系）） (4) (P(A),?)
答：(4)
53、有限布尔代数的元素的个数一定等于（ ）。
(1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂
答：(4)
（图论部分）
54、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图
答：(4)
55、下面给出的集合中，哪一个是前缀码？( ) (1) {0，10，110，101111} (2) {01，001，000，1} (3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}
答：（2）
第 7 页 共 33 页
56、一个图的哈密尔顿路是一条通过图中( )的路。
答：所有结点一次且恰好一次
57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。
答：以v为起点的边的条数， 以v为终点的边的条数
58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定
答：1
59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。
答：
n(n?1), n-1 260、一棵无向树的顶点数n与边数m关系是( )。
答：m=n-1
61、一个图的欧拉回路是一条通过图中( )的回路。
答：所有边一次且恰好一次
62、有n个结点的树，其结点度数之和是( )。
答：2n-2
63、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011}
答：(1)
64、n个结点的有向完全图边数是( )，每个结点的度数是( )。
答：n(n-1),2n-2
65、一个无向图有生成树的充分必要条件是( )。
答：它是连通图
66、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。
答：（3）
第 8 页 共 33 页
67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。
答：2
68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。
答：1，树
69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:
(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。
答：（1）
70、设T是一棵树，则T是一个连通且( )图。
答：无简单回路
71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16
答：（4）
72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 12
答：(4)
73、设图G=
答：有向图
74、任一有向图中，度数为奇数的结点有( )个。
答：偶数
75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？
(1) 2 (2) 4 (3) 3 (4) 5
答：（3）
76、在有n个顶点的连通图中，其边数（ ）。
(1) 最多有n-1条 (2) 至少有n-1 条
第 9 页 共 33 页
(3) 最多有n条 (4) 至少有n 条
答：（2）
77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。
(1) 5 (2) 7 (3) 8 (4) 9
答：（4）
78、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。
(1) n (2) 2n (3) n-1 (4) 2
答：（1）
79、下列哪一种图不一定是树（ ）。
(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图
答：（3）
80、连通图G是一棵树当且仅当G中（ ）。 (1) 有些边是割边 (2) 每条边都是割边
(3) 所有边都不是割边 (4) 图中存在一条欧拉路径
答：（2）
（数理逻辑部分）
二、求下列各公式的主析取范式和主合取范式： 1、(P→Q)?R
解：(P→Q)?R?(?P?Q )?R
?(?P?R)?(Q?R) （析取范式）
?(?P?(Q??Q)?R)?((?P?P)?Q?R)
?(?P?Q?R)?(?P??Q?R)?(?P?Q?R)?(P?Q?R) ?(?P?Q?R)?(?P??Q?R)?(P?Q?R)（主析取范式）
?((P→Q)?R)?(?P??Q??R)?(?P?Q??R)?(P??Q?R)
第 10 页 共 33 页